Codeforces Round #610 DIV2 E問題 (2500pt)
Problem description
省略
省略
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年04月27日16時09分48秒
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)