結果
問題 | No.1600 Many Shortest Path Problems |
ユーザー | 👑 Nachia |
提出日時 | 2021-07-22 22:46:45 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 512 ms / 4,000 ms |
コード長 | 5,172 bytes |
コンパイル時間 | 1,598 ms |
コンパイル使用メモリ | 107,596 KB |
実行使用メモリ | 41,136 KB |
最終ジャッジ日時 | 2024-07-17 19:11:38 |
合計ジャッジ時間 | 17,157 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 500 ms
38,244 KB |
testcase_05 | AC | 491 ms
38,356 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 115 ms
9,700 KB |
testcase_11 | AC | 142 ms
10,808 KB |
testcase_12 | AC | 221 ms
17,760 KB |
testcase_13 | AC | 381 ms
29,700 KB |
testcase_14 | AC | 502 ms
38,364 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 296 ms
23,728 KB |
testcase_18 | AC | 493 ms
38,184 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 274 ms
23,592 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 512 ms
38,300 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 169 ms
23,464 KB |
testcase_30 | AC | 182 ms
24,120 KB |
testcase_31 | AC | 221 ms
23,512 KB |
testcase_32 | AC | 223 ms
23,804 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 275 ms
39,300 KB |
testcase_36 | AC | 194 ms
41,136 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 176 ms
24,112 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 186 ms
24,248 KB |
testcase_41 | AC | 156 ms
23,468 KB |
testcase_42 | AC | 164 ms
24,240 KB |
testcase_43 | AC | 172 ms
24,248 KB |
testcase_44 | AC | 197 ms
24,372 KB |
testcase_45 | AC | 170 ms
23,468 KB |
testcase_46 | AC | 176 ms
24,116 KB |
testcase_47 | AC | 189 ms
24,244 KB |
testcase_48 | AC | 204 ms
24,232 KB |
testcase_49 | AC | 2 ms
5,376 KB |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | AC | 2 ms
5,376 KB |
testcase_52 | AC | 2 ms
5,376 KB |
testcase_53 | AC | 2 ms
5,376 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 HLD{ int N; vector<int> P; vector<int> PP; vector<int> PD; vector<int> D; vector<int> rangeL; vector<int> rangeR; HLD(const vector<vector<int>>& E = {{}}){ N = E.size(); P.assign(N, -1); vector<int> I = {0}; rep(i,I.size()){ int p = I[i]; for(int e : E[p]) if(P[p] != e){ I.push_back(e); P[e] = p; } } vector<int> Z(N, 1); for(int i=N-1; i>=1; i--) Z[P[I[i]]] += Z[I[i]]; PP.resize(N); for(int i=0; i<N; i++) PP[i] = i; vector<int> nx(N, -1); for(int p : I) if(p != 0){ if(nx[P[p]] == -1) nx[P[p]] = p; if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p; } rep(i,N) if(nx[i] != -1) PP[nx[i]] = i; for(int p : I) if(p != 0) PP[p] = PP[PP[p]]; PD.assign(N,N); PD[0] = 0; for(int p : I) if(p != 0) PD[p] = min(PD[PP[p]], PD[P[p]]+1); D.assign(N,0); for(int p : I) D[p] = ((PP[p] == p) ? 0 : D[P[p]]+1); rangeL.assign(N,-1); rangeR.assign(N,-1); vector<int> dfs; int ir = 0; dfs.push_back(0); while(dfs.size()){ int p = dfs.back(); dfs.pop_back(); if(p < 0){ rangeR[-1-p] = ir; continue; } dfs.push_back(-1-p); for(int e : E[p]) if(P[p] != e) if(e != nx[p]) dfs.push_back(e); if(nx[p] != -1) dfs.push_back(nx[p]); rangeL[p] = ir++; } } int lca(int u, int v){ if(PD[u] < PD[v]) swap(u, v); while(PD[u] > PD[v]) u = P[PP[u]]; while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; } return (D[u] > D[v]) ? v : u; } vector<pair<int,int>> getpath(int r, int c){ vector<pair<int,int>> res; while(PD[r] < PD[c]){ res.push_back({ rangeL[PP[c]], rangeL[c]+1 }); c = P[PP[c]]; } if(PP[r] != PP[c]) return {}; if(D[r] > D[c]) return {}; res.push_back({ rangeL[r], rangeL[c]+1 }); reverse(res.begin(), res.end()); return move(res); } }; 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; HLD hld; vector<int> Eidx; vector<int> depi; vector<mll> dep; vector<int> iEidx; vector<int> flowIdx; void read_graph(){ cin >> N >> M; vector<vector<int>> E2(N); 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}); E2[u].push_back(v); E2[v].push_back(u); } } hld = HLD(E2); } 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); } } } int LCA(int u,int v){ return hld.lca(u,v); } 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]; 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;