QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721270 | #9459. Tree Equation | SpadeA261 | AC ✓ | 173ms | 22404kb | C++17 | 2.4kb | 2024-11-07 15:43:44 | 2024-11-07 15:43:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<class T1,class T2> bool cmax(T1& a,const T2& b){return a<b?a=b,1:0;}
template<class T1,class T2> bool cmin(T1& a,const T2& b){return b<a?a=b,1:0;}
#define fir(i,x,y,...) for(int i(x),##__VA_ARGS__;i<=(y);i++)
#define firr(i,x,y,...) for(int i(x),##__VA_ARGS__;i>=(y);i--)
#define fird(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i<=(y);i+=(d))
#define firrd(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i>=(y);i-=(d))
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define ll long long
#define ull unsigned long long
int T;
bool _mul=1;
ll gcd(ll x,ll y){if(!y) return x;return gcd(y,x%y);}
ll power(ll b,ll p,ll mod){ll res=1;while(p){if(p&1) res=res*b%mod;b=b*b%mod;p>>=1;}return res;}
const int N=1e5+5,B=131;
int na,nb,nc;
vector<int> ea[N],eb[N],ec[N];
int siz[N],tot;
ull h[N];
unordered_map<ull,ull> mp,a,b,c;
ull hsh(ull x){return x*x*x*x+x*x*x*B+x*x*B*B+x*B*B*B+B*B*B*B;}
ull dfsa(int u,ull x)
{
ull res=x;
for(int v:ea[u]) res+=hsh(dfsa(v,x));
return res;
}
ull dfsb(int u,ull x)
{
ull res=x;
for(int v:eb[u]) res+=hsh(dfsb(v,x));
return res;
}
void dfsc(int u)
{
siz[u]=1;
for(int v:ec[u]) dfsc(v),siz[u]+=siz[v];
sort(ec[u].begin(),ec[u].end(),[](int x,int y){return siz[x]<siz[y];});
mp[0]++;
for(int v:ec[u]) h[u]+=hsh(h[v]),mp[h[u]]++;
c[h[u]]=u;
}
void print(int u,int fa=0)
{
int res=++tot;
cout<<fa<<" ";
for(int v:ec[u]) print(v,res);
}
void solve()
{
cin>>na>>nb>>nc;
fir(i,1,na,x) cin>>x,ea[x].push_back(i);
fir(i,1,nb,x) cin>>x,eb[x].push_back(i);
fir(i,1,nc,x) cin>>x,ec[x].push_back(i);
dfsc(1);
for(auto [x,cnt]:mp)
{
if(cnt>=na-1) a[dfsa(1,x)]=x;
if(cnt>=nb-1) b[dfsb(1,x)]=x;
}
bool flag=0;
for(auto [x,y]:a) if(b.count(h[1]-x))
{
int ansx=c[y],ansy=c[b[h[1]-x]];
cout<<siz[ansx]<<" "<<siz[ansy]<<endl;
tot=0,print(ansx),cout<<endl;
tot=0,print(ansy),cout<<endl;
flag=1;
break;
}
if(!flag) cout<<"Impossible"<<endl;
fir(i,0,na) ea[i].clear();
fir(i,0,nb) eb[i].clear();
fir(i,0,nc) ec[i].clear(),h[i]=0;
mp.clear(),a.clear(),b.clear(),c.clear();
return;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin.tie(nullptr)->sync_with_stdio(false);
if(_mul) cin>>T;
else T=1;
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: 10880kb
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: 173ms
memory: 22404kb
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: 2ms
memory: 10644kb
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