QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#720522 | #9459. Tree Equation | Hollow_knight_ | AC ✓ | 59ms | 40124kb | C++14 | 2.4kb | 2024-11-07 13:07:56 | 2024-11-07 13:07:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=2e6+15;
inline ll read(){
ll x=0;char f=1,c=getchar();
while(c<48||c>57){if(c=='-')f=0;c=getchar();}
while(c>=48&&c<=57){x=(x<<1)+(x<<3)+ll(c)-48;c=getchar();}
return f==1?x:-x;
}
ll seed=19780823;
ll get(ll x){
x^=x<<13,x^=x>>7,x^=x<<17;
return x;
}
struct tree{
int n,f[N];
ll mxd,hf[N],dep[N],siz[N];
void input(){for(int i=1;i<=n;++i){f[i]=read();}}
void hsh(ll x){
mxd=0;
for(int i=1;i<=n;++i){hf[i]=x,siz[i]=1,dep[i]=dep[f[i]]+1,mxd=max(mxd,dep[i]);}
for(int i=n;i>=2;--i){hf[f[i]]+=get(hf[i]),siz[f[i]]+=siz[i];}
}
ll val(){return hf[1];}
};
tree a,b,c;
int cnta,cntb,scnt,np[N],visp[N],ans[N];
void sol(int u){
for(int i=1;i<=c.n;++i){np[i]=visp[i]=ans[i]=0;}
scnt=0,np[u]=++scnt,ans[scnt]=0,visp[u]=1;
for(int i=2;i<=c.n;++i){
if(visp[c.f[i]]){
np[i]=++scnt,ans[scnt]=np[c.f[i]],visp[i]=1;
}
}
for(int i=1;i<=scnt;++i){printf("%d ",ans[i]);}
}
unordered_map<ll,bool>vwa,vwb;
struct Node{
ll siz;
int x;
friend bool operator <(Node a,Node b){
return a.siz<b.siz;
}
}pa[N],pb[N];
int solve(){
vwa.clear(),vwb.clear();
cnta=0,cntb=0;
a.n=read(),b.n=read(),c.n=read();
a.input(),b.input(),c.input();
a.hsh(seed),b.hsh(seed),c.hsh(seed);
for(int i=1;i<=c.n;++i){
if(c.dep[i]==a.mxd&&!vwa.count(c.hf[i])){pa[++cnta]=Node{c.siz[i],i},vwa[c.hf[i]]=1;}
if(c.dep[i]==b.mxd&&!vwb.count(c.hf[i])){pb[++cntb]=Node{c.siz[i],i},vwb[c.hf[i]]=1;}
}
sort(pa+1,pa+cnta+1),sort(pb+1,pb+cntb+1);
for(int j,u,v,i=1;i<=cnta;++i){
if(a.n*pa[i].siz>c.siz[1]){break;}
for(j=1;j<=cntb;++j){
if(a.n*pa[i].siz+b.n*pb[j].siz-1<c.siz[1]){continue;}
if(a.n*pa[i].siz+b.n*pb[j].siz-1>c.siz[1]){break;}
u=pa[i].x,v=pb[j].x;
a.hsh(c.hf[u]),b.hsh(c.hf[v]);
if(a.val()+b.val()-seed==c.val()){
printf("%lld %lld\n",c.siz[u],c.siz[v]);
sol(u),putchar('\n'),sol(v);
return 0;
}
}
}
printf("Impossible");
return 0;
}
/*
4
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
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
*/
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=read();
while(T--){
solve();
if(T!=0)printf("\n");
}
fclose(stdin),fclose(stdout);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30368kb
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: 59ms
memory: 40124kb
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 2 1 1 1 1 0 0 2 8 0 1 0 1 1 3 3 3 1 1 1 1 0 0 4 1 0 1 1 1 0 3 1 0 1 1 0 5 1 0 1 2 1 1 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: 0ms
memory: 30664kb
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 2 2 1
result:
ok 1 cases passed
Extra Test:
score: 0
Extra Test Passed