QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#720138 | #9459. Tree Equation | Sai_tqwq | AC ✓ | 178ms | 35284kb | C++14 | 1.8kb | 2024-11-07 10:50:07 | 2024-11-07 10:50:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define double long double
#define endl '\n'
const int B=131;
int rnd(int x){return x*x*x*x+x*x*x*B+x*x*B*B+x*B*B*B+B*B*B*B;}
int na,nb,nc,fa[100009],fb[100009],fc[100009],szc[100009],hc[100009],dfnc;
vector<int> ga[100009],gb[100009],gc[100009];
unordered_map<int,vector<int> > cf;
unordered_map<int,int> cx,cy,cnt;
void dfs(int u){
szc[u]=1;hc[u]=0;
for(int v:gc[u])dfs(v),szc[u]+=szc[v];
sort(gc[u].begin(),gc[u].end(),[&](int x,int y){return szc[x]<szc[y];});
cnt[0]++;
for(int v:gc[u])cnt[hc[u]+=rnd(hc[v])]++;
cf[hc[u]].push_back(u);
}
int mula(int u,int x){int res=x;for(int v:ga[u])res+=rnd(mula(v,x));return res;}
int mulb(int u,int x){int res=x;for(int v:gb[u])res+=rnd(mulb(v,x));return res;}
void print(int u,int f){cout<<f<<' ';int p=++dfnc;for(int v:gc[u])print(v,p);}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int cas;cin>>cas;
while(cas--){
cin>>na>>nb>>nc;
cf.clear();cx.clear();cy.clear();cnt.clear();
for(int i=1;i<=na;i++)ga[i].clear(),cin>>fa[i];
for(int i=1;i<=nb;i++)gb[i].clear(),cin>>fb[i];
for(int i=1;i<=nc;i++)gc[i].clear(),cin>>fc[i];
for(int i=1;i<=na;i++)ga[fa[i]].push_back(i);
for(int i=1;i<=nb;i++)gb[fb[i]].push_back(i);
for(int i=1;i<=nc;i++)gc[fc[i]].push_back(i);
dfs(1);
for(auto p:cnt){
if(p.second>=na-1)cx[mula(1,p.first)]=p.first;
if(p.second>=nb-1)cy[mulb(1,p.first)]=p.first;
}
bool fl=0;
for(auto p:cx){
int rx=hc[1]-p.first;
if(cy.count(rx)){
int x=cf[p.second][0],y=cf[cy[rx]][0];
cout<<szc[x]<<' '<<szc[y]<<endl;
dfnc=0;print(x,0);cout<<endl;
dfnc=0;print(y,0);cout<<endl;
fl=1;break;
}
}
if(!fl)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: 12820kb
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: 178ms
memory: 35284kb
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: 13244kb
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