QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#748805 | #9459. Tree Equation | eastcloud | AC ✓ | 126ms | 57136kb | C++17 | 2.4kb | 2024-11-14 21:30:28 | 2024-11-14 21:30:33 |
Judging History
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