リジャッジがなければ、もう少し早くミスに気づけたのに…。
https://csacademy.com/contest/round-83/task/firestarter/
問題
ロープとその結び目がそれぞれ辺・頂点として連結無向グラフを成している。
結び目の間にロープがある場合、それぞれその長さが与えられている。
以下のクエリがQ個与えられる。
指定されたロープのある位置から、時刻Tに火をつける。
ロープに火をつけると、そこから両方向に時速1で火が広がる。
結び目まで火が到達すると、以降はその結び目の先にあるロープにも火が及ぶ。
全てのロープに火が到達するまでの時間を求めよ。
解法
着火点を頂点として挿入しよう。
あとはダイクストラの要領で各頂点の着火時刻を求める。
最後に各ロープ両端の結び目の着火時刻から、ロープが燃え尽きる時刻を求める。
int N,M,Q; ll A[202020],B[202020],L[202020]; map<pair<int,int>,int> R; vector<pair<int,int>> V[201010]; ll QT[202020],QA[202020],QB[202020],X[202020]; ll tim[404040]; vector<pair<int,int>> E[404040]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>Q; FOR(i,M) { cin>>A[i]>>B[i]>>L[i]; L[i]*=2; A[i]--,B[i]--; R[{A[i],B[i]}]=i; R[{B[i],A[i]}]=i+M; V[i].push_back({0,A[i]}); V[i].push_back({L[i],B[i]}); } FOR(i,N) tim[i]=1LL<<60; FOR(i,Q) { cin>>tim[N+i]>>x>>y>>X[i]; X[i]*=2; tim[N+i]*=2; int cur=R[{x-1,y-1}]; if(cur<M) { V[cur].push_back({X[i],N+i}); } else { cur-=M; V[cur].push_back({L[cur]-X[i],N+i}); } } FOR(i,M) { sort(ALL(V[i])); FOR(j,V[i].size()-1) { E[V[i][j].second].push_back({V[i][j+1].first-V[i][j].first,V[i][j+1].second}); E[V[i][j+1].second].push_back({V[i][j+1].first-V[i][j].first,V[i][j].second}); } } priority_queue<pair<ll,int>> PQ; FOR(i,N+Q) PQ.push({-tim[i],i}); while(PQ.size()) { ll co=-PQ.top().first; int cur=PQ.top().second; PQ.pop(); if(tim[cur]!=co) continue; FORR(e,E[cur]) { if(tim[e.second]>co+e.first) { tim[e.second]=co+e.first; PQ.push({-tim[e.second],e.second}); } } } ll ma=0; FOR(i,N+Q) FORR(e,E[i]) { ll X=tim[i]; ll Y=tim[e.second]; ll L=e.first; ma=max(ma,Y+(L-abs(Y-X))/2); } cout<<ma/2; if(ma%2) cout<<".5"; cout<<endl; }
まとめ
まぁ上位陣がみな通ってない時点でリジャッジを疑うよね。