Codeforces Round #600 DIV2 F問題 (2750pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, M, K, Q, A[3d5], B[3d5], X, Y; ll C[3d5];
int ss[1d5];
int mmm, aaa[3d5], bbb[3d5]; ll ccc[3d5];
int mm, aa[1d5], bb[1d5]; ll cc[1d5];
ll arr[1d5];
{
int i, j, k;
wgraph<ll> g;
unionFind uf;
HLD hld;
HLD_segtree<ll> t;
LHeap<ll> hp;
ll tmp;
rd(N,M,K,Q,(A--,B--,C)(M));
g.setEdge(N,M,A,B,C);
hp.malloc(N);
hp.init(N);
rep(i,K) hp.change(i,0);
rep(i,K,N) hp.change(i,ll_inf);
rep(i,K) ss[i] = i;
while(hp.size){
i = hp.pop();
rep(j,g.es[i]){
k = g.edge[i][j];
if(hp.val[k] > hp.val[i] + g.cost[i][j]){
hp.change(k, hp.val[i] + g.cost[i][j]);
ss[k] = ss[i];
}
}
}
uf.malloc(N);
uf.init(N);
rep(i,M) if(ss[A[i]] != ss[B[i]]) arrInsert(mmm, mmm, aaa, ss[A[i]], bbb, ss[B[i]], ccc, hp.val[A[i]] + hp.val[B[i]] + C[i]);
sortA(mmm,ccc,aaa,bbb);
rep(i,mmm) if(uf(aaa[i],bbb[i])) arrInsert(mm, mm, aa, aaa[i], bb, bbb[i], cc, ccc[i]);
g.setEdge(K, mm, aa, bb, cc);
hld.init(g.g);
rep(i,mm){
j = hld.depth(aa[i]);
k = hld.depth(bb[i]);
if(j > k) arr[aa[i]] = -cc[i];
else arr[bb[i]] = -cc[i];
}
t.init(&hld, arr);
rep(Q){
rd(X--,Y--);
k = hld.lca(X, Y);
t.change(k,k,1);
wt(-t.getMinVal(X,Y));
t.change(k,k,arr[k]);
}
}
Current time: 2024年03月29日01時59分45秒
Last modified: 2019年11月25日23時07分17秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF600 CF_Div2_F
トップページに戻る
Logged in as: unknown user (not login)