AtCoder Beginner Contest 155
問題文
省略
省略
C++に変換後のコードはこちら
int N, A[1d5], B[1d5+1], M, L[2d5], R[2d5], ind[2d5];
wgraph<int> g;
int vis[1d5+1];
int ress, res[2d5];
void solve(int n, int b = -1){
int i, j;
vis[n] = 1;
rep(i,g.es[n]){
j = g.edge[n][i];
if(j == b) continue;
solve(j, n);
if(B[j]) (B[n], B[j]) ^= 1, res[ress++] = g.cost[n][i];
}
}
{
int i, j, k, e;
unionFind uf;
rd(N,M,(A,B)(N),(L,R++)(M));
sortA(N,A,B);
rep(i,M){
L[i] = lower_bound(A, A+N, L[i]) - A;
R[i] = lower_bound(A, A+N, R[i]) - A;
ind[i] = i;
}
uf.malloc(N+1);
uf.init(N+1);
k = 0;
rep(i,M) if(uf(L[i],R[i])) arrInsert(k, k, L, L[i], R, R[i], ind, ind[i]);
M = k;
g.setEdge(N+1, M, L, R, ind);
rrep(i,1,N+1) B[i] = if[B[i]!=B[i-1], 1, 0];
rep(i,N+1) if(!vis[i]) solve(i);
rep(i,N+1) if(B[i]) wt(-1), return 0;
sortA(ress,res);
wt(ress);
wt(res(ress)+1);
}
Current time: 2024年04月27日05時52分55秒
Last modified: 2020年02月23日02時18分35秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC155 ABC_F
トップページに戻る
Logged in as: unknown user (not login)