結果
問題 | No.1600 Many Shortest Path Problems |
ユーザー |
![]() |
提出日時 | 2021-07-09 22:57:17 |
言語 | C++17 (gcc 11.2.0 + boost 1.78.0) |
結果 |
AC
|
実行時間 | 673 ms / 4,000 ms |
コード長 | 3,766 Byte |
コンパイル時間 | 1,299 ms |
使用メモリ | 41,420 KB |
最終ジャッジ日時 | 2022-07-19 15:08:01 |
合計ジャッジ時間 | 18,985 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,948 KB |
testcase_01 | AC | 1 ms
6,948 KB |
testcase_02 | AC | 2 ms
4,900 KB |
testcase_03 | AC | 2 ms
4,900 KB |
testcase_04 | AC | 649 ms
40,308 KB |
testcase_05 | AC | 673 ms
40,364 KB |
testcase_06 | AC | 2 ms
4,904 KB |
testcase_07 | AC | 2 ms
4,904 KB |
testcase_08 | AC | 1 ms
4,900 KB |
testcase_09 | AC | 2 ms
4,900 KB |
testcase_10 | AC | 145 ms
9,332 KB |
testcase_11 | AC | 206 ms
10,800 KB |
testcase_12 | AC | 390 ms
18,832 KB |
testcase_13 | AC | 586 ms
30,940 KB |
testcase_14 | AC | 669 ms
40,380 KB |
testcase_15 | AC | 2 ms
4,904 KB |
testcase_16 | AC | 1 ms
4,900 KB |
testcase_17 | AC | 498 ms
25,568 KB |
testcase_18 | AC | 645 ms
40,328 KB |
testcase_19 | AC | 2 ms
4,904 KB |
testcase_20 | AC | 2 ms
4,900 KB |
testcase_21 | AC | 474 ms
25,432 KB |
testcase_22 | AC | 1 ms
4,904 KB |
testcase_23 | AC | 2 ms
6,948 KB |
testcase_24 | AC | 664 ms
40,260 KB |
testcase_25 | AC | 2 ms
4,904 KB |
testcase_26 | AC | 1 ms
4,904 KB |
testcase_27 | AC | 1 ms
4,904 KB |
testcase_28 | AC | 1 ms
4,900 KB |
testcase_29 | AC | 512 ms
25,208 KB |
testcase_30 | AC | 514 ms
25,540 KB |
testcase_31 | AC | 444 ms
25,384 KB |
testcase_32 | AC | 402 ms
25,460 KB |
testcase_33 | AC | 1 ms
6,948 KB |
testcase_34 | AC | 1 ms
6,952 KB |
testcase_35 | AC | 392 ms
41,420 KB |
testcase_36 | AC | 351 ms
40,760 KB |
testcase_37 | AC | 1 ms
4,904 KB |
testcase_38 | AC | 458 ms
25,308 KB |
testcase_39 | AC | 1 ms
4,900 KB |
testcase_40 | AC | 495 ms
25,608 KB |
testcase_41 | AC | 208 ms
25,000 KB |
testcase_42 | AC | 229 ms
25,696 KB |
testcase_43 | AC | 212 ms
25,228 KB |
testcase_44 | AC | 240 ms
25,632 KB |
testcase_45 | AC | 517 ms
24,840 KB |
testcase_46 | AC | 430 ms
25,488 KB |
testcase_47 | AC | 558 ms
25,496 KB |
testcase_48 | AC | 435 ms
25,540 KB |
testcase_49 | AC | 1 ms
4,904 KB |
testcase_50 | AC | 1 ms
4,904 KB |
testcase_51 | AC | 2 ms
5,156 KB |
testcase_52 | AC | 2 ms
5,156 KB |
testcase_53 | AC | 2 ms
5,256 KB |
ソースコード
#include <atcoder/modint> #include <iostream> #include <vector> #include <algorithm> #include <set> using namespace atcoder; using namespace std; using ll = long long; using ull = unsigned long long; const ull MOD = 1000000007; using mll = static_modint<1000000007>; #define rep(i,n) for(int i=0; i<(n); i++) struct DSU{ vector<int> V; DSU(int n){ V.resize(n); rep(i,n) V[i] = i; } int leader(int a){ if(V[a] == a) return a; return V[a] = leader(V[a]); } void merge(int r,int c){ V[leader(c)] = leader(r); } }; struct Edge{ int u,v,i; }; int N, M; vector<Edge> J; vector<vector<Edge>> E; vector<Edge> flows; vector<mll> cost; vector<int> P; vector<vector<int>> P2; vector<int> Eidx; vector<int> depi; vector<mll> dep; vector<int> iEidx; vector<int> flowIdx; void read_graph(){ cin >> N >> M; E.resize(N); cost.resize(M); cost[0] = 2; for(int i=1; i<M; i++) cost[i] = cost[i-1] * 2; DSU G1(N); rep(i,M){ int u,v; cin >> u >> v; u--; v--; J.push_back({u,v,i}); if(G1.leader(u) == G1.leader(v)){ flows.push_back({u,v,i}); } else{ G1.merge(u,v); E[u].push_back({u,v,i}); E[v].push_back({v,u,i}); } } } void initLCA(){ vector<int> I; P.assign(N,-1); I.push_back(0); depi.assign(N,0); dep.assign(N,0); Eidx.assign(N,-1); rep(i,I.size()){ int p = I[i]; for(Edge e : E[p]) if(P[p] != e.v){ P[e.v] = p; dep[e.v] = dep[p] + cost[e.i]; depi[e.v] = depi[p] + 1; Eidx[e.v] = e.i; I.push_back(e.v); } } P2.assign(20,vector<int>(N)); rep(i,N) P2[0][i] = P[i]; P2[0][0] = 0; rep(d,19) rep(i,N) P2[d+1][i] = P2[d][P2[d][i]]; } int LCA(int u,int v){ if(depi[u] < depi[v]) swap(u,v); for(int i=19; i>=0; i--) if(depi[u]-depi[v] >= (1<<i)) u = P2[i][u]; if(u == v) return u; for(int i=19; i>=0; i--) if(P2[i][u] != P2[i][v]){ u = P2[i][u]; v = P2[i][v]; } return P2[0][u]; } int dist0(int u,int v){ int g = LCA(u,v); return depi[u] + depi[v] - depi[g] * 2; } mll dist1(int u,int v){ int g = LCA(u,v); return dep[u] + dep[v] - dep[g] * 2; } void build_flows(){ iEidx.assign(M,-1); rep(i,N) if(Eidx[i] != -1) iEidx[Eidx[i]] = i; flowIdx.assign(N,-1); DSU G2(N); for(Edge e : flows){ int g = G2.leader(LCA(e.u,e.v)); for(int s : {e.u,e.v}){ int p = G2.leader(s); while(p != g){ flowIdx[p] = e.i; G2.merge(P[p],p); p = G2.leader(p); } } } } int path_includes(int u,int v,int z){ if(iEidx[z] == -1) return -1; if((LCA(u,v)^LCA(u,J[z].u)^LCA(v,J[z].u)) != J[z].u) return -1; if((LCA(u,v)^LCA(u,J[z].v)^LCA(v,J[z].v)) != J[z].v) return -1; int res = flowIdx[iEidx[z]]; if(res == -1) return -2; return res; } mll shortest_using(int u,int v,int z){ mll ans = cost[z]; //cout << "u = " << u << ", v = " << v << ", z = " << z << endl; //cout << "e = " << J[z].u << ", " << J[z].v << endl; //cout << "d1 = " << (dist0(u,J[z].u) + dist0(v,J[z].v)) << ", d2 = " << (dist0(u,J[z].v) + dist0(v,J[z].u)) << endl; if(dist0(u,J[z].u) + dist0(v,J[z].v) < dist0(u,J[z].v) + dist0(v,J[z].u)) ans += dist1(u,J[z].u) + dist1(v,J[z].v); else ans += dist1(u,J[z].v) + dist1(v,J[z].u); return ans; } int main(){ read_graph(); initLCA(); build_flows(); int Q; cin >> Q; rep(q,Q){ int u,v,z; cin >> u >> v >> z; u--; v--; z--; int inc = path_includes(u,v,z); if(inc == -2){ cout << "-1\n"; continue; } if(inc == -1){ cout << dist1(u,v).val() << "\n"; continue; } auto e = J[inc]; mll ans = shortest_using(u,v,e.i); cout << ans.val() << "\n"; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_inst;