#396770 (C++14) No.922 東北きりきざむたん

提出ソース

結果

問題	No.922 東北きりきざむたん
ユーザー	log_K
提出日時	2019-11-08 22:55:30
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	7,418 bytes
コンパイル時間	3,359 ms
コンパイル使用メモリ	225,912 KB
実行使用メモリ	33,400 KB
最終ジャッジ日時	2024-09-15 02:04:23
合計ジャッジ時間	10,349 ms
ジャッジサーバーID （参考情報）	judge6 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,756 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	TLE	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	82 ms 32,308 KB
testcase_16	TLE	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(cnt); ++(var))
#define REP(var,init,cnt) for(int (var)=(init); (var)<=(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) (flag)?1:0
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const pair<T1,T2> &p){
  os<<"P("<<p.first<<", "<<p.second<<") ";
  return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ================================================
template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename G >
struct CentroidDecomposition {
  const G &g;
  vector< int > sub;
  vector< vector< int > > belong;
  vector< bool > v;

  CentroidDecomposition()=default;
  CentroidDecomposition(const G &g) : g(g), sub(g.size()), v(g.size()), belong(g.size()) {}

  inline int build_dfs(int idx, int par) {
    sub[idx] = 1;
    for(auto &to : g[idx]) {
      if(to == par || v[to]) continue;
      sub[idx] += build_dfs(to, idx);
    }
    return sub[idx];
  }

  inline int search_centroid(int idx, int par, const int mid) {
    for(auto &to : g[idx]) {
      if(to == par || v[to]) continue;
      if(sub[to] > mid) return search_centroid(to, idx, mid);
    }
    return idx;
  }

  inline void belong_dfs(int idx, int par, int centroid) {
    belong[idx].emplace_back(centroid);
    for(auto &to : g[idx]) {
      if(to == par || v[to]) continue;
      belong_dfs(to, idx, centroid);
    }
  }

  inline int build(UnWeightedGraph &t, int idx) {
    int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2);
    v[centroid] = true;
    belong_dfs(centroid, -1, centroid);
    for(auto &to : g[centroid]) {
      if(!v[to]) t[centroid].emplace_back(build(t, to));
    }
    v[centroid] = false;
    return centroid;
  }

  inline int build(UnWeightedGraph &t) {
    t.resize(g.size());
    return build(t, 0);
  }
};

struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

vector< int > dijkstra(UnWeightedGraph &g, int s) {
  const auto INF = numeric_limits< int >::max();
  vector< int > dist(g.size(), INF);

  using Pi = pair< int, int >;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()) {
    int cost;
    int idx;
    tie(cost, idx) = que.top();
    que.pop();
    if(dist[idx] < cost) continue;
    for(auto &e : g[idx]) {
      auto next_cost = cost + 1;
      if(dist[e] <= next_cost) continue;
      dist[e] = next_cost;
      que.emplace(dist[e], e);
    }
  }
  return dist;
}

// Template End ======================================================

constexpr int MOD=1e9+7;
constexpr int INF=INT_MAX;

int main(void){
  int N,M,Q; cin>>N>>M>>Q;
  vec<pi> ed(M);
  UnionFind U(N);
  rep(i,M){
    int u,v; cin>>u>>v; --u,--v;
    ed[i]=pi(u,v);
    U.unite(u,v);
  }
  unordered_map<int,map<int,int>> mp;
  rep(i,N){
    mp[U.find(i)][i]=0;
  }
  unordered_map<int,UnWeightedGraph> G;
  ran(i,mp){
    G[i.first].resize(i.second.size());
    int k=0;
    ran(j,i.second){
      j.second=k++;
    }
  }
  rep(i,M){
    int u,v; tie(u,v)=ed[i];
    G[U.find(u)][mp[U.find(u)][u]].emplace_back(mp[U.find(u)][v]);
    G[U.find(u)][mp[U.find(u)][v]].emplace_back(mp[U.find(u)][u]);
  }
//  unordered_map<int,CentroidDecomposition<UnWeightedGraph>> CG;
  unordered_map<int,int> CT;
  unordered_map<int,vec<int>> CD;
  ran(i,G){
    UnWeightedGraph Tree;
    CT[i.first]=CentroidDecomposition<UnWeightedGraph>(i.second).build(Tree);
    CD[i.first]=dijkstra(i.second,CT[i.first]);
  }
  
  val<int> ans(Q);
  unordered_map<int,int> AIR;
  int idx=0;
  vec<pi> task;
  rep(i,Q){
    int a,b; cin>>a>>b; --a,--b;
    if(U.find(a)==U.find(b)){
      vec<int> dist=dijkstra(G[U.find(a)],mp[U.find(a)][a]);
      ans[idx]=dist[mp[U.find(a)][b]];
      //cout<<a+1<<" "<<b+1<<" (Same) : "<<ans[idx]<<endl;
      ++idx;
    }
    else{
      task.emplace_back(a,b);
      ++AIR[U.find(a)],++AIR[U.find(b)];
      //ans[i]=CD[U.find(a)][mp[U.find(a)][a]]+CD[U.find(b)][mp[U.find(b)][b]];
      //cout<<a+1<<" "<<b+1<<" (Diff) : "<<CD[U.find(a)][mp[U.find(a)][a]]<<" + "<<CD[U.find(b)][mp[U.find(b)][b]]<<endl;
    }
  }
  rep(i,task.size()){
    int a,b; tie(a,b)=task[i];
    if(AIR[U.find(a)]==1&&AIR[U.find(b)]==1){
      ans[idx]=0;
      //cout<<a+1<<" "<<b+1<<" (Diff) : "<<0<<endl;
    }
    else if(AIR[U.find(a)]==1){
      ans[idx]=CD[U.find(b)][mp[U.find(b)][b]];
      //cout<<a+1<<" "<<b+1<<" (Diff) : "<<CD[U.find(b)][mp[U.find(b)][b]]<<endl;
    }
    else if(AIR[U.find(b)]==1){
      ans[idx]=CD[U.find(a)][mp[U.find(a)][a]];
      //cout<<a+1<<" "<<b+1<<" (Diff) : "<<CD[U.find(a)][mp[U.find(a)][a]]<<endl;
    }
    else{
      ans[idx]=CD[U.find(a)][mp[U.find(a)][a]]+CD[U.find(b)][mp[U.find(b)][b]];
      //cout<<a+1<<" "<<b+1<<" (Diff) : "<<CD[U.find(a)][mp[U.find(a)][a]]<<" + "<<CD[U.find(b)][mp[U.find(b)][b]]<<endl;
    }
    ++idx;
  }/*
  ran(i,CT){cout<<i<<endl;}
  ran(i,CD){
    cout<<i.first+1<<" : ";
    ran(j,i.second){
      cout<<j<<" ";
    }
    cout<<endl;
  }*/
  cout<<ans.sum()<<endl;
}

yukicoder

結果

テストケース

ソースコード