Codeforces Round #610 DIV2 E問題 - The Cake Is a Lie

Source

Codeforces Round #610 DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20191227-1)のコード

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

//no-unlocked
int N;
int A[1d5][3];

unionFind uf;
deque<int> g[1d5];
set<int> tri[1d5];
int st[1d5], sts;

int res1[1d5];
int res2[1d5], ress;

void merge(int i, int j){
  int ii, jj, x, y, z, d, v;
  x = ii = uf(i);
  y = jj = uf(j);
  uf(i,j);
  z = uf(i);
  d = (z^x^y);

  if(g[z].front() == i || g[z].front() == j){
    if(g[d].front() == i || g[d].front() == j){
      while(g[d].size()) g[z].push_front(g[d].front()), g[d].pop_front();
    } else {
      while(g[d].size()) g[z].push_front(g[d].back()), g[d].pop_back();
    }
  } else {
    if(g[d].front() == i || g[d].front() == j){
      while(g[d].size()) g[z].push_back(g[d].front()), g[d].pop_front();
    } else {
      while(g[d].size()) g[z].push_back(g[d].back()), g[d].pop_back();
    }
  }

}

{
  int i, j, k, t, a;

  uf.malloc(1d5);
  REP(rd_int()){
    rd(N);
    rep(i,N-2) rd((A[i]--)(3));

    uf.init(N);
    rep(i,N){
      g[i].clear();
      g[i].push_back(i);
    }

    sts = 0;
    rep(i,N) tri[i].clear();
    rep(i,N-2) rep(j,3) tri[A[i][j]].insert(i);
    rep(i,N) if(tri[i].size()==1) st[sts++] = i;

    ress = 0;
    while(sts){
      i = st[--sts];
      if(tri[i].size() == 0) continue;
      t = *(tri[i].begin());
      res2[ress++] = t;

      j = k = -1;
      rep(a,3){
        if(A[t][a]==i) continue;
        if(j==-1) j = A[t][a], continue;
        k = A[t][a];
      }
      tri[i].erase(t);
      tri[j].erase(t); if(tri[j].size()==1) st[sts++] = j;
      tri[k].erase(t); if(tri[k].size()==1) st[sts++] = k;

      if(uf(i) != uf(j)) merge(i, j);
      if(uf(i) != uf(k)) merge(i, k);
    }

    i = uf(0);
    k = 0;
    for(int x : g[i]) res1[k++] = x;
    wt(res1(N)+1);
    wt(res2(ress)+1);
  }
}

Current time: 2024年03月28日21時36分19秒
Last modified: 2019年12月27日20時47分51秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF610 CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: