QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#748805#9459. Tree EquationeastcloudAC ✓126ms57136kbC++172.4kb2024-11-14 21:30:282024-11-14 21:30:33

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 21:30:33]
  • 评测
  • 测评结果:AC
  • 用时:126ms
  • 内存:57136kb
  • [2024-11-14 21:30:28]
  • 提交

answer


#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline
#define ull unsigned long long

using namespace std;

#define N 500005

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

vi R[3][N];
int num[3];

ull f(ull x){return x*x*x*17ull+x*x*7ull+x*3ull+1141ull;}
ull h(ull x){return f((x>>31))+f(x&((1ll<<31)-1));}

ull H[N];
int siz[N],tot;
map<ull,ull> t,A,B;

void dfs1(int x,int fa){
    siz[x]=1;H[x]=0;
    for(auto v:R[2][x])dfs1(v,x),siz[x]+=siz[v];
    sort(all(R[2][x]),[](int x,int y){return siz[x]<siz[y];});
    t[H[x]]++;
    for(auto v:R[2][x])H[x]+=h(H[v]),t[H[x]]++;
}

ull tmp[N];
ull dfs2(int ty,int x,ull w){
    ull res=w;
    for(auto v:R[ty][x])res+=h(dfs2(ty,v,w));
    return res;
}
void dfs3(int x,int fa){
    write(fa);putchar(' ');int id=++tot;
    for(auto v:R[2][x])dfs3(v,id);
}

void solve(){
    t.clear();A.clear();B.clear();
    for(int i=0;i<3;i++){
        num[i]=read();
        for(int j=0;j<=num[i];j++)R[i][j].clear();
    }
    for(int i=0;i<3;i++){
        for(int j=1;j<=num[i];j++){int x=read();R[i][x].pb(j);}
    }
    dfs1(R[2][0][0],0);
    for(auto [w,cnt]:t){
        if(cnt>=num[0]-1)A[dfs2(0,R[0][0][0],w)]=w;
        if(cnt>=num[1]-1)B[dfs2(1,R[1][0][0],w)]=w;
    }
    for(auto [w,X]:A){
        ull alt=H[R[2][0][0]]-w;
        if(B.count(alt)){
            ull Y=B[alt];
            int xrt=0,yrt=0;
            for(int i=1;i<=num[2];i++){
                if(H[i]==X)xrt=i;
                if(H[i]==Y)yrt=i;
            }
            write(siz[xrt]);putchar(' ');write(siz[yrt]);putchar('\n');
            tot=0;dfs3(xrt,0);putchar('\n');tot=0;dfs3(yrt,0);putchar('\n');
            return;
        }
    }
    printf("Impossible\n");
}

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #endif

    int T=read();while(T--)solve();
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 43552kb

input:

2
2 3 10
0 1
0 1 2
0 1 1 3 4 3 6 3 1 9
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9

output:

Impossible
2 1
0 1 
0 

result:

ok 2 cases passed

Test #2:

score: 0
Accepted
time: 126ms
memory: 57136kb

input:

11122
3 3 11
0 1 1
0 1 1
0 1 1 1 4 4 1 1 8 8 1
7 2 10
0 1 2 2 2 1 1
0 1
0 1 2 1 1 5 5 5 1 1
7 8 14
0 1 2 1 1 1 1
0 1 2 1 1 1 1 1
0 1 1 3 1 1 1 1 1 1 1 11 1 1
4 8 11
0 1 1 1
0 1 1 1 1 1 6 6
0 1 1 1 1 1 6 6 1 1 1
3 4 13
0 1 1
0 1 1 1
0 1 1 3 1 5 1 1 8 1 10 1 12
11 2 14
0 1 2 1 4 4 4 1 1 1 1
0 1
0 1 1 ...

output:

1 3
0 
0 1 1 
1 2
0 
0 1 
1 1
0 
0 
1 1
0 
0 
2 2
0 1 
0 1 
1 2
0 
0 1 
1 5
0 
0 1 1 1 4 
1 1
0 
0 
2 8
0 1 
0 1 1 1 1 5 5 5 
1 1
0 
0 
4 1
0 1 1 1 
0 
3 1
0 1 1 
0 
5 1
0 1 1 1 4 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
2 1
0 1 
0 
1 5
0 
0 1 1 1 1 
1 1
0 
0 
1 3
0 
0 1 1 
1 2
0 
0 1 
3 1
0 1 1 ...

result:

ok 11122 cases passed

Test #3:

score: 0
Accepted
time: 3ms
memory: 44340kb

input:

1
5 5 49
0 1 1 3 1
0 1 2 1 2
0 1 2 3 4 1 6 7 8 9 1 11 12 13 14 11 16 17 18 19 1 21 22 23 24 1 26 26 1 1 30 31 31 30 30 35 36 36 35 30 40 41 41 40 1 45 46 46 45

output:

5 5
0 1 2 3 4 
0 1 1 3 3 

result:

ok 1 cases passed

Extra Test:

score: 0
Extra Test Passed