AtCoder Beginner Contest 155 F問題 - Perils in Parallel

Source

AtCoder Beginner Contest 155
問題文

問題概要

省略

解法

省略

cLay（version 20200217-1）のコード

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日03時26分51秒
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)