結果
| 問題 | No.1600 Many Shortest Path Problems |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2021-08-20 00:10:30 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,280 bytes |
| コンパイル時間 | 6,300 ms |
| コンパイル使用メモリ | 144,796 KB |
| 最終ジャッジ日時 | 2025-01-23 23:02:04 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 2 |
| other | AC * 5 WA * 46 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/string:50,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/locale_classes.h:40,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/ios_base.h:41,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ios:42,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ostream:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/iostream:39,
from main.cpp:2:
In static member function 'static constexpr _Up* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(_Tp*, _Tp*, _Up*) [with _Tp = const int; _Up = int; bool _IsMove = false]',
inlined from 'constexpr _OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:501:30,
inlined from 'constexpr _OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:528:42,
inlined from 'constexpr _OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:535:31,
inlined from 'constexpr _OI std::copy(_II, _II, _OI) [with _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:626:7,
inlined from 'static _ForwardIterator std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const int*; _ForwardIterator = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_uninitialized.h:147:27,
inlined from '_Fo
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;struct heavy_light_decomposition{private:int N;vector<int> P;vector<int> PP;vector<int> PD;vector<int> D;vector<int> I;vector<int> rangeL;vector<int> rangeR;public:heavy_light_decomposition(const vector<vector<int>>& E = {{}}){N = E.size();P.assign(N, -1);I = {0};I.reserve(N);for(int i=0; i<I.size(); i++){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);vector<int> nx(N, -1);PP.resize(N);for(int i=0; i<N; i++) PP[i] = i;for(int i=N-1; i>=1; i--){int p = I[i];Z[P[p]] += Z[p];if(nx[P[p]] == -1) nx[P[p]] = p;if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p;}for(int p : I) if(nx[p] != -1) PP[nx[p]] = p;PD.assign(N,N);PD[0] = 0;D.assign(N,0);for(int p : I) if(p != 0){PP[p] = PP[PP[p]];PD[p] = min(PD[PP[p]], PD[P[p]]+1);D[p] = D[P[p]]+1;}rangeL.assign(N,0);rangeR.assign(N,0);vector<int> dfs;dfs.push_back(0);while(dfs.size()){int p = dfs.back();rangeR[p] = rangeL[p] + Z[p];int ir = rangeR[p];dfs.pop_back();for(int e : E[p]) if(P[p] != e) if(e != nx[p]){rangeL[e] = (ir -= Z[e]);dfs.push_back(e);}if(nx[p] != -1){rangeL[nx[p]] = rangeL[p] + 1;dfs.push_back(nx[p]);}}I.resize(N);for(int i=0; i<N; i++) I[rangeL[i]] = i;}int depth(int p) const {return D[p];}int lca(int u, int v) const {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;}int dist(int u, int v) const {return depth(u) + depth(v) - depth(lca(u,v)) * 2;}vector<pair<int,int>> path(int r, int c, bool include_root = true, bool reverse_path = false) const {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 });if(!include_root){res.back().first++;if(res.back().first == res.back().second) res.pop_back();}if(!reverse_path) reverse(res.begin(),res.end());return move(res);}const vector<int>& idxs() const {return rangeL;}int meet(int x, int y, int z) const {//return lca(x,y) ^ lca(y,z) ^ lca(x,z);if(PD[x] > PD[y]) swap(x,y);if(PD[y] > PD[z]) swap(y,z);if(PD[x] > PD[y]) swap(x,y);while(PD[z] > PD[y]) z = P[PP[z]];while(PD[y] > PD[x]){if(PP[y] == PP[z]) return (D[y] > D[z]) ? z : y;y = P[PP[y]];z = P[PP[z]];}while(true){if(PP[x] == PP[y]) return (D[x] > D[y]) ? y : x;if(PP[x] == PP[z]) return (D[x] > D[z]) ? z : x;if(PP[y] == PP[z]) return (D[y] > D[z]) ? z : y;x = P[PP[x]];y = P[PP[y]];z = P[PP[z]];}return -1;}int jump(int from, int to, int d) const {int g = lca(from,to);int dist0 = D[from] - D[g] * 2 + D[to];if(dist0 > d) return -1;int p = from;if(D[from] - D[g] > d){ p = to; d = dist0 - d; }while(D[p] - D[PP[p]] > d){d -= D[p] - D[PP[p]] + 1;p = P[PP[p]];}return I[rangeL[p] - d];}};#include <iostream>#include <vector>#include <algorithm>#include <set>using namespace std;using ll = long long;using ull = unsigned long long;const ull MOD = 1000000007;#define rep(i,n) for(int i=0; i<(n); i++)struct mll{using u32 = uint32_t;using u64 = uint64_t;u32 v;mll(u32 x = 0) : v(x) {}u32 val() const { return v; }mll& operator+=(const mll& r){ v += r.val(); if(v >= MOD) v -= MOD; return *this; }mll& operator-=(const mll& r){ v += MOD - r.val(); if(v >= MOD) v -= MOD; return *this; }mll& operator*=(const mll& r) { v = (u64)v * r.val() % MOD; return *this; }mll operator+(const mll& r) const { mll res = *this; res += r; return res; }mll operator-(const mll& r) const { mll res = *this; res -= r; return res; }mll operator*(const mll& r) const { mll res = *this; res *= r; return res; }mll operator-() const { return v ? mll(MOD-v) : mll(0); }};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<int> Eidx;vector<mll> dep;vector<int> iEidx;vector<int> flowIdx;heavy_light_decomposition hld;void read_graph(){cin >> N >> M;E.resize(N);vector<vector<int>> idE(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});idE[u].push_back(v);idE[v].push_back(u);}}hld = heavy_light_decomposition(idE);}void initLCA(){vector<int> I;P.assign(N,-1);I.push_back(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];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){return hld.dist(u,v);}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(hld.meet(u,v,J[z].u) != J[z].u) return -1;if(hld.meet(u,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);elseans += 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;