保存されている過去のバージョンの一覧

キーエンス プログラミング コンテスト 2020 E問題 - Bichromization

Source

キーエンス プログラミング コンテスト 2020
問題文

問題概要

省略

解法

省略

cLay（version 20200119-1）のコード

C++に変換後のコードはこちら

int N, M, D[1d5], A[2d5], B[2d5], ind[2d5];
char S[1d5+2];
int C[2d5];
int fg[1d5];
char rev[256];
{
  int i, j, k, x;
  wgraph<int> g;
  LHeap<int> hp;

  rev['W'] = 'B';
  rev['B'] = 'W';

  rd(N,M,(D(N)),(A--,B--)(M));
  rep(i,M) ind[i] = i;
  g.setEdge(N,M,A,B,ind);

  hp.walloc(M);
  hp.init(M);
  rep(i,M) hp.change(i, int_inf);
  rep(i,M) if(D[A[i]] == D[B[i]]) hp.change(i, D[A[i]]);

  while(hp.size){
    k = hp.pop();
    if(hp.val[k]==int_inf) wt(-1), return 0;

    if(S[A[k]] == 0 && S[B[k]] == 0) S[A[k]] = 'W';
    if(S[A[k]] == 0) S[A[k]] = rev[S[B[k]]];
    if(S[B[k]] == 0) S[B[k]] = rev[S[A[k]]];
    C[k] = hp.val[k];

    rep(loop,2){
      i = if[loop==0, A[k], B[k]];
      if(fg[i]++) continue;
      rep(j,g.es[i]){
        x = g.edge[i][j];
        if(S[x]==0 && D[x] >= D[i]) hp.change(g.cost[i][j], D[x]);
      }
    }
  }
  wtLn(S,C(M));
}

Current time: 2024年04月25日21時15分04秒
Last modified: 2020年01月19日04時39分26秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)