QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #390644 | #6507. Recover the String | OccDreamer | RE | 7ms | 72932kb | C++14 | 8.4kb | 2024-04-15 19:07:46 | 2024-04-15 19:07:47 |
Judging History
answer
//code by Emissary
#include<bits/stdc++.h>
#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)
#define NO puts("No")
#define YES puts("Yes")
//#define OccDreamer
//#define int long long
using namespace std;
namespace IO{
inline int read(){
int X=0, W=0; char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(int x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(int x){write(x), putchar(32);}
inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 1e6+5;
int n, m, len[MAXN], which[MAXN], maxlen;
int lc[MAXN], rc[MAXN], inl[MAXN], inr[MAXN];
char ans[MAXN], cur[MAXN], to[MAXN], tmp[MAXN];
//which=1, 全相同，which=2 XY 交替，which=3 正常节点
bool vis[MAXN];
pair<int,int> type[MAXN][2][2];
// [i] 节点 i [0/1] S 和 rev S [0/1] L,R 在哪边
char str[MAXN], st[MAXN][2][2], A[MAXN], B[MAXN];
vc<int> F[MAXN], G[MAXN];
inline void dfs(int x, int L){
vis[x]=1; len[x]=L; maxlen=max(maxlen,L);
for(auto i:G[x]){
if(!vis[i]) dfs(i,L+1);
}
return ;
}
inline void get(int x){
//cerr << "GET:" << x << endl;
if(which[x]==1){
type[x][0][0]=type[x][0][1]=type[x][1][0]=type[x][1][1]=mk(0,0); //inl
st[x][0][0]=st[x][0][1]=st[x][1][0]=st[x][1][1]=str[x]=str[inl[x]];
}
if(which[x]==2){
if(len[x]==2){
type[x][0][0]=mk(0,0), type[x][0][1]=mk(1,0);
type[x][1][0]=mk(1,0), type[x][1][1]=mk(0,0);
st[x][0][0]=st[x][1][1]=str[inr[x]];
st[x][0][1]=st[x][1][0]=str[inl[x]];
A[x]=str[inl[x]], B[x]=str[inr[x]];
}
else{
A[x]=A[inl[x]], B[x]=B[inl[x]];
//cerr << "x=" << x << ' ' << A[x] << ' ' << B[x] << endl;
int o;
if(A[inr[x]]==A[x]) o=1;
else o=0;
type[x][0][0]=mk(0,0), type[x][0][1]=mk(1,o);
type[x][1][0]=mk(0,1), type[x][1][1]=mk(1,o^1);
if(len[x]&1){
st[x][0][0]=A[x]; st[x][0][1]=A[x];
st[x][1][0]=B[x]; st[x][1][1]=B[x];
}
else{
st[x][0][0]=B[x]; st[x][0][1]=A[x];
st[x][1][0]=A[x]; st[x][1][1]=B[x];
}
}
}
if(which[x]==3){
if(which[inl[x]]!=2 && which[inr[x]]!=2){
int com;
int a=inl[x], b=inr[x];
if(inl[a]==inl[b] || inl[a]==inr[b]) com=inl[a];
else com=inr[a]; char c='.', d='.'; int posc, posd;
for(int j=0;j<2;++j){
if(type[a][0][j].fi==(com==inr[a])){
if(j==0) c=st[a][0][j], posd=j;
else c=st[a][0][j], posc=j;
}
if(type[b][0][j].fi==(com==inr[b])){
if(j==0) d=st[b][0][j], posd=j;
else d=st[b][0][j], posd=j;
}
}
//cerr << "pos:" << posc << ' ' << posd << endl;
if(posc!=posd){
if(posc==0) type[x][0][1]=mk(0,0), type[x][0][0]=mk(1,0);
else type[x][0][1]=mk(1,0), type[x][0][0]=mk(0,0);
}
else{
int ox=0, oy=0; oy^=1; posd^=1; d=st[b][1][posd];
if(posc==0) type[x][0][1]=mk(0,ox), type[x][0][0]=mk(1,oy);
else type[x][0][1]=mk(1,oy), type[x][0][0]=mk(0,ox);
}
st[x][0][0]=d; st[x][0][1]=c;
//cerr << "c=" << c << ' ' << "d=" << d << endl;
type[x][1][1]=type[x][0][0];
type[x][1][1].se^=1;
type[x][1][0]=type[x][0][1];
type[x][1][0].se^=1;
st[x][1][1]=st[x][0][0];
st[x][1][0]=st[x][0][1];
}
else{
if(which[inl[x]]==2) swap(inl[x],inr[x]);
int a=inl[x], b=inr[x];
int com=-1;
if(inl[a]==inl[b] || inl[a]==inr[b]) com=inl[a];
else if(inr[a]==inl[b] || inr[a]==inr[b]) com=inr[a];
if((inl[a]==inl[b] || inl[a]==inr[b]) && (inr[a]==inl[b] || inr[a]==inr[b])){
A[x]=A[a]; B[x]=B[a];
type[x][0][0]=mk(0,0);
st[x][0][0]=A[x]; int o=0;
if(A[b]==B[x]) o=0;
else o=1;
type[x][0][1]=mk(1,o);
st[x][0][1]=A[x];
type[x][1][1]=type[x][0][0];
type[x][1][0]=type[x][0][1];
st[x][1][1]=B[x];
st[x][1][0]=B[x];
return ;
}
int u=A[b], v=B[b]; bool flag=0;
for(int i=0;i<2 && !flag;++i){
for(int j=0;j<2 && !flag;++j){
//cerr << a << ' ' << i << ' ' << j << ' ' << type[a][i][j].fi << ' ' << type[a][i][j].se << endl;
if(type[a][i][j].se==0 && type[a][i][j].fi==(com==inr[a])){
if(j==0){
type[x][0][1]=mk(0,i);
int w=st[a][i][j^1];
st[x][0][1]=u+v-w;
st[x][0][0]=st[a][i][j];
int o;
if(u+v-w==u) o=0;
else o=1;
type[x][0][0]=mk(1,o);
flag=1;
}
else{
type[x][0][0]=mk(0,i);
int w=st[a][i][j^1];
st[x][0][1]=st[a][i][j];
st[x][0][0]=u+v-w;
int o;
if(u+v-w==u) o=0;
else o=1;
type[x][0][1]=mk(1,o^1);
flag=1;
}
}
}
}
if(len[x]&1){
type[x][1][1]=type[x][0][0];
type[x][1][1].se^=1;
type[x][1][0]=type[x][0][1];
type[x][1][0].se^=1;
st[x][1][1]=st[x][0][0];
st[x][1][0]=st[x][0][1];
}
else{
type[x][1][1]=type[x][0][0];
if(type[x][1][1].fi!=1) type[x][1][1].se^=1;
type[x][1][0]=type[x][0][1];
if(type[x][1][0].fi!=1) type[x][1][0].se^=1;
st[x][1][1]=st[x][0][0];
st[x][1][0]=st[x][0][1];
}
}
}
/*
cerr << "info:" << x << ' ' << str[x] << ' ' << A[x] << ' ' << B[x] << endl;
cerr << "0:" << inl[x] << ' ' << inr[x] << endl;
for(int i=0;i<2;++i){
if(i==0) cerr << "L:" << endl;
else cerr << "R:" << endl;
if(type[x][0][i].fi==0) cerr << inl[x] << ' ';
else cout << inr[x] << ' ';
if(type[x][0][i].se==0) cerr << "S:" << ' ' << st[x][0][i] << endl;
else cerr << "F(S):" << ' ' << st[x][0][i] << endl;
}
cerr << "inforev:" << x << ' ' << str[x] << ' ' << B[x] << ' ' << A[x] << endl;
cerr << "0:" << inl[x] << ' ' << inr[x] << endl;
for(int i=0;i<2;++i){
if(i==0) cerr << "L:" << endl;
else cerr << "R:" << endl;
if(type[x][1][i].fi==0) cerr << inl[x] << ' ';
else cout << inr[x] << ' ';
if(type[x][1][i].se==0) cerr << "S:" << ' ' << st[x][1][i] << endl;
else cerr << "F(S):" << ' ' << st[x][1][i] << endl;
}*/
return ;
}
bool mark[124];
inline void chkmin(){
char now='a';
memset(mark,0,sizeof mark);
for(int i=1;i<=maxlen;++i){
if(mark[cur[i]]) tmp[i]=to[cur[i]];
else mark[cur[i]]=1, to[cur[i]]=now, now++, tmp[i]=to[cur[i]];
}
for(int i=1;i<=maxlen;++i){
if(ans[i]<tmp[i]) return ;
if(ans[i]>tmp[i]) break;
}
for(int i=1;i<=maxlen;++i) ans[i]=tmp[i];
return ;
}
inline void calc(int x){
int now=x, w=0;
while(len[now]>1){
cur[len[now]]=st[now][w][0];
int X=type[now][w][0].fi, Y=type[now][w][0].se;
now=X?inr[now]:inl[now], w=Y;
}
cur[1]=str[now]; chkmin();
if(which[x]==3) reverse(cur+1,cur+1+len[x]);
else for(int i=1;i<=now;++i) cur[i]=(i%2==1?B[x]:A[1]);
chkmin();
}
inline void solve(){
n=read(), m=read(); int p[20];
for(int i=1;i<=n;++i) p[i]=i; //srand(7);
// random_shuffle(p+1,p+1+n);
// for(int i=1;i<=n;++i) cout << p[i] << ' '; cout << endl;
for(int i=1;i<=n;++i) ans[i]='z', G[i].clear(); maxlen=0;
for(int i=1;i<=n;++i) inl[i]=inr[i]=vis[i]=0, which[i]=3;
for(int i=1;i<=m;++i){
int x, y;
x=read(), y=read();
// x=p[x], y=p[y];
if(inl[y]) inr[y]=x;
else inl[y]=x;
G[x].pb(y);
}
for(int i=1;i<=n;++i) vis[i]=0;
char now='a';
for(int i=1;i<=n;++i)
if(inl[i]==0) dfs(i,1), str[i]=now, now++;
for(int i=1;i<=n;++i) if(inl[i]<inr[i]) swap(inl[i],inr[i]);
for(int i=1;i<=n;++i){
if(inl[i] && inl[i] && len[i]!=1){
int o=inl[inl[i]], p=inr[inl[i]];
if(inl[inr[i]]==o && inr[inr[i]]==p && o && p) which[i]=which[inl[i]]=which[inr[i]]=which[o]=which[p]=2;
}
if(len[i]==2 && inl[i] && inr[i]) which[i]=2;
}
for(int i=1;i<=n;++i) F[i].clear();
for(int i=1;i<=n;++i){
if(len[i]==1 || !inr[i]) which[i]=1;
F[len[i]].pb(i);
}
int las=1;
for(int i=2;i<=n;++i){
for(auto j:F[i]){
get(j);
las=j;
}
}
calc(las);
for(int i=1;i<=maxlen;++i) putchar(ans[i]); putchar(10);
}
signed main(){
int t=read();
while(t--) solve();
return 0;
}
/*
1
11 16
1 3
1 4
1 5
2 4
2 5
3 6
3 7
4 7
4 8
5 8
6 9
7 9
7 10
8 10
9 11
10 11
aaaba
*/
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 72932kb
input:
3 1 0 5 6 2 4 2 5 5 3 4 3 1 5 1 4 8 11 1 2 1 4 1 6 2 5 3 4 3 6 4 5 4 7 5 8 6 7 7 8
output:
a aba aaba
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
26837 1 0 2 1 2 1 3 2 1 3 2 3 3 2 3 1 1 2 5 5 4 3 5 1 1 2 3 2 5 3 5 6 2 4 2 5 5 3 4 3 1 5 1 4 5 5 1 5 2 1 2 4 4 5 3 4 6 6 1 4 5 3 2 4 4 6 3 6 2 3 4 3 1 3 3 4 2 1 7 8 2 5 1 3 7 1 3 5 7 6 1 2 4 6 6 3 8 11 2 6 2 7 3 7 8 1 6 4 4 5 7 4 7 1 3 8 2 8 1 5 8 10 8 1 4 5 7 8 3 5 3 1 7 3 1 2 5 2 6 4 6 3 9 11 5 2...
output:
a aa ab aaa aab aba aab abc aaaa aaab aaba abba abca aaba abab abac abba aaab abbc aabc abac abbc abcd aaaaa aaaab aabaa aaabb abbbc aabaa aabab aabac aabba aaabb abbca aabca abcba abbca aabcd aaaab abaab abaac ababa aaaba aabcb aabac abbca abbca abcad aabba aabab abbac aaabb aaaba aaabc abbca abaac...