CSAcademy Round #83 : E. Firestarter

リジャッジがなければ、もう少し早くミスに気づけたのに…。
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;
	
}

まとめ

まぁ上位陣がみな通ってない時点でリジャッジを疑うよね。