QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#720060 | #9459. Tree Equation | Purslane | AC ✓ | 156ms | 27864kb | C++14 | 1.8kb | 2024-11-07 10:28:00 | 2024-11-07 10:28:00 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int T,a,b,n,tp[MAXN];
ull ha[MAXN],hb[MAXN],h[MAXN];
ull mask;
mt19937 myrand(time(NULL));
ull shift(ull x) {return x^=mask,x^=x<<13,x^=x>>7,x^=x<<17,x^=mask,x;}
struct Tree {
vector<int> G[MAXN];
int dep[MAXN],sze[MAXN];
ull h[MAXN];
void dfs(int u) {
sze[u]=1,h[u]=1;
for(auto v:G[u]) dep[v]=dep[u]+1,dfs(v),sze[u]+=sze[v],h[u]+=shift(h[v]);
return ;
}
ull calc(int u,ull x) {
ull ans=x;
for(auto v:G[u]) ans+=shift(calc(v,x));
return ans;
}
void init(int n) {
ffor(i,1,n) G[i].clear();
ffor(i,1,n) {int f;cin>>f,G[f].push_back(i);}
dfs(1);
return ;
}
void output(int u,int fa,int &tot) {
int id=++tot;
cout<<fa<<' ';
for(auto v:G[u]) output(v,id,tot);
return ;
}
}A,B,C;
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>T;
while(T--) {
mask=myrand()*myrand();
cin>>a>>b>>n;
A.init(a),B.init(b),C.init(n);
int mxa=0,mxb=0;
ffor(i,1,a) mxa=max(mxa,A.dep[i]);
ffor(i,1,b) mxb=max(mxb,B.dep[i]);
map<ull,int> mpa,mpb,usa,usb;
ffor(i,1,n) if(C.dep[i]==mxa) {
if(a<=n/C.sze[i]&&!usa[C.h[i]]) {
usa[C.h[i]]=1;
mpa[A.calc(1,C.h[i])]=i;
}
}
ffor(i,1,n) if(C.dep[i]==mxb) {
if(b<=n/C.sze[i]&&!usb[C.h[i]]) {
usb[C.h[i]]=1;
mpb[B.calc(1,C.h[i])]=i;
}
}
int flg=0;
for(auto pr:mpa) {
ull val=pr.first,x=C.h[1]+1-val;
if(mpb[x]) {
int id1=pr.second,id2=mpb[x];
cout<<C.sze[id1]<<' '<<C.sze[id2]<<'\n';
int tot1=0,tot2=0;
C.output(id1,0,tot1),cout<<'\n',C.output(id2,0,tot2);
flg=1;break ;
}
//val+x=hsh[1]+1
}
if(!flg) cout<<"Impossible\n";
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16316kb
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: 156ms
memory: 27864kb
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 0 1 4 0 0 1 1 1 1 4 ...
result:
ok 11122 cases passed
Test #3:
score: 0
Accepted
time: 0ms
memory: 16124kb
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