QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#735581 | #9459. Tree Equation | zero-range | AC ✓ | 161ms | 19732kb | C++23 | 1.6kb | 2024-11-11 20:48:56 | 2024-11-11 20:48:56 |
Judging History
answer
#include<stdio.h>
#include<algorithm>
#include<random>
#include<map>
#include<time.h>
#define M 100005
using namespace std;
typedef unsigned long long ull;
inline ull trans(ull x){
x^=(x>>29)&0x5555555555555555ULL,
x^=(x<<17)&0x71D67FFFEDA60000ULL,
x^=(x<<37)&0xFFF7EEE000000000ULL,
x^=(x>>43);
return x;
}
struct Tree{
int n,f[M],sz[M],dep[M],mxd;
ull H[M];
inline void read(){
for(int i=1;i<=n;++i) scanf("%d",f+i),sz[i]=0;
for(int i=n;i;--i) ++sz[i],sz[f[i]]+=sz[i];
mxd=0;
for(int i=1;i<=n;++i) dep[i]=dep[f[i]]+1,mxd=max(mxd,dep[i]);
}
inline void work(ull w){
for(int i=1;i<=n;++i) H[i]=w;
for(int i=n;i;--i) H[f[i]]+=trans(H[i]);
}
} A,B,C;
vector<int> G[M];
map<ull,bool> sX,sY;
map<ull,int> mX,mY;
mt19937_64 rnd(time(0));
int tot;
void out(int x,int fa){
printf("%d ",fa);
int c=++tot;
for(int p:G[x]) out(p,c);
}
inline void solve(){
scanf("%d%d%d",&A.n,&B.n,&C.n);
A.read(),B.read(),C.read();
ull w=rnd();
A.work(w),B.work(w),C.work(w),sX.clear(),sY.clear(),mX.clear(),mY.clear();
for(int i=1;i<=C.n;++i){
G[i].clear();
if(C.dep[i]==A.mxd&&!sX[C.H[i]]){
sX[C.H[i]]=1,A.work(C.H[i]);
mX[A.H[1]]=i;
}
if(C.dep[i]==B.mxd&&!sY[C.H[i]]){
sY[C.H[i]]=1,B.work(C.H[i]);
mY[B.H[1]]=i;
}
G[C.f[i]].push_back(i);
}
for(auto [Hx,x]:mX){
ull Hy=C.H[1]+w-Hx;
auto it=mY.find(Hy);
if(it==mY.end()) continue;
int y=it->second;
printf("%d %d\n",C.sz[x],C.sz[y]);
tot=0,out(x,0),putchar('\n'),
tot=0,out(y,0),putchar('\n');
return;
}
puts("Impossible");
}
int main(){
// freopen("in.txt","r",stdin);
int T;scanf("%d",&T);
while(T--) solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10112kb
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: 161ms
memory: 19732kb
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: 2ms
memory: 10168kb
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