省略
省略
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: 2024年03月29日17時07分57秒
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)