QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714909 | #9459. Tree Equation | DaiRuiChen007 | AC ✓ | 215ms | 23592kb | C++17 | 1.8kb | 2024-11-06 09:08:40 | 2024-11-06 09:08:41 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1e5+5;
ull H(ull x) {
auto _=[&](ull z) { return z*z*z+z*z*5+9*z+8; };
return _(x>>32)+_(x&(-1u));
}
int na,nb,nc,fa[MAXN],fb[MAXN],fc[MAXN];
vector <int> A[MAXN],B[MAXN],C[MAXN];
int siz[MAXN];
ull f[MAXN];
map <ull,int> cnt;
void dfs1(int u) {
siz[u]=1,f[u]=0;
for(int v:C[u]) dfs1(v),siz[u]+=siz[v];
sort(C[u].begin(),C[u].end(),[&](int x,int y){ return siz[x]<siz[y]; });
++cnt[f[u]];
for(int v:C[u]) f[u]+=H(f[v]),++cnt[f[u]];
}
ull dfs2(int u,ull w) {
ull z=w;
for(int v:A[u]) z+=H(dfs2(v,w));
return z;
}
ull dfs3(int u,ull w) {
ull z=w;
for(int v:B[u]) z+=H(dfs3(v,w));
return z;
}
void dfs4(int u,int fz,int &idx) {
int x=++idx; cout<<fz<<" ";
for(int v:C[u]) dfs4(v,x,idx);
}
void solve() {
cin>>na>>nb>>nc,cnt.clear();
for(int i=0;i<=na;++i) A[i].clear();
for(int i=0;i<=nb;++i) B[i].clear();
for(int i=0;i<=nc;++i) C[i].clear();
for(int i=1;i<=na;++i) cin>>fa[i],A[fa[i]].push_back(i);
for(int i=1;i<=nb;++i) cin>>fb[i],B[fb[i]].push_back(i);
for(int i=1;i<=nc;++i) cin>>fc[i],C[fc[i]].push_back(i);
dfs1(C[0][0]);
map <ull,ull> ha,hb;
for(auto it:cnt) {
ull hv=it.first; int w=it.second;
if(w>=na-1) ha[dfs2(A[0][0],hv)]=hv;
if(w>=nb-1) hb[dfs3(B[0][0],hv)]=hv;
}
for(auto it:ha) {
ull rem=f[C[0][0]]-it.first,tx=it.second;
if(hb.count(rem)) {
ull ty=hb[rem];
int x=0,y=0;
for(int i=1;i<=nc;++i) {
if(f[i]==tx) x=i;
if(f[i]==ty) y=i;
}
cout<<siz[x]<<" "<<siz[y]<<"\n";
int cx=0,cy=0;
dfs4(x,0,cx),cout<<"\n";
dfs4(y,0,cy),cout<<"\n";
return ;
}
}
cout<<"Impossible\n";
return ;
}
signed main() {
ios::sync_with_stdio(false);
int T; cin>>T;
while(T--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 10668kb
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: 215ms
memory: 23592kb
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: 11804kb
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