AtCoder Grand Contest 041 E問題 - Balancing Network

Source

AtCoder Grand Contest 041
問題文

問題概要

省略

解法

省略

cLayversion 20191227-1)のコード

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

int N, M, T, X[1d5], Y[1d5];
char res[100002];


bitset<50000> bs[50000];
void solve1(){
  unionFind uf;

  rep(i,N) bs[i].set(i);
  rep(i,M) bs[X[i]] = bs[Y[i]] = (bs[X[i]] | bs[Y[i]]);

  rep(k,N) if(bs[k].count() == N){
    uf.malloc(N);
    uf.init(N);
    rep(i,M) res[i] = '^';

    rrep(i,M){
      if(uf(X[i]) == uf(Y[i])) continue;
      if(uf(X[i]) != uf(k) && uf(Y[i]) != uf(k)) continue;
      res[i] = if[uf(X[i]) == uf(k), '^', 'v'];
      uf(X[i], Y[i]);
    }

    wt(res);
    return;
  }

  wt(-1);
}

int flow[1d5], cnv[1d5], sz;
set<int> s[3];
void solve2(){
  int st, a[3], k;
  int xx, yy, xi, yi;

  if(N==2) wt(-1), return;

  sz = N;
  rep(i,N) flow[i] = 1;
  rep(i,M) res[i] = '^';

  rep(i,M){
    if(sz > 3){
      if(flow[X[i]] == flow[Y[i]] == 0) continue;
      if(flow[X[i]] == flow[Y[i]] == 1) flow[Y[i]] = 0, sz--, continue;
      flow[X[i]] = 1;
      flow[Y[i]] = 0;
      continue;
    }
    st = i; break;
  }

  if(i==M) wt(res), return;

  k = 0;
  rep(i,N) if(flow[i]) a[k++] = i;
  rep(i,3) cnv[a[i]] = i;
  rep(i,st,M) if(flow[X[i]]==0 && flow[Y[i]]==1){
    res[i] = 'v';
  }
  rep(i,st,M) if(flow[X[i]] && flow[Y[i]]){
    xx = cnv[X[i]];
    yy = cnv[Y[i]];
    s[xx].insert(i);
    s[yy].insert(i);
  }
  rep(i,3) s[i].insert(int_inf);
  rep(i,st,M) if(flow[X[i]] && flow[Y[i]]){
    xx = cnv[X[i]];
    yy = cnv[Y[i]];
    popFirst(s[xx]);
    popFirst(s[yy]);
    xi = getFirst(s[xx]);
    yi = getFirst(s[yy]);
    res[i] = if[xi >= yi, '^', 'v'];
  }
  wt(res);
}

{
  rd(N,M,T,(X--,Y--)(M));
  if(T==1) solve1();
  else     solve2();
}

Current time: 2021年09月28日22時27分53秒
Last modified: 2019年12月29日00時05分59秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC041 AGC_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: