QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722874 | #9459. Tree Equation | djh0314 | AC ✓ | 135ms | 33100kb | C++14 | 2.6kb | 2024-11-07 20:28:59 | 2024-11-07 20:28:59 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int N = 1e5+5;
const ull P = 131;
inline int read() {
int x=0,f=1;
char c=0;
while(!isdigit(c=getchar())) if(c=='-') f=-f;
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*f;
}
int n, m,na,nb;
int siz[N],dfn;
ull f[N];
vector<int> lj_a[N],lj_b[N],lj[N];
unordered_map<ull,vector<int> > id;
unordered_map<ull,ull> mark,vis,cnt;
inline bool cmp(int u,int v) {
return siz[u]<siz[v];
}
inline ull Hsh(ull x) {
x=x*x;
return ((x>>3)^(x<<5))*P+((x<<7)^(x>>4))+P;
}
inline void dfs(int now) {
siz[now]=1,f[now]=0;
for(auto to:lj[now]) dfs(to),siz[now]+=siz[to];
sort(lj[now].begin(),lj[now].end(),cmp);
++cnt[0];
for(auto to:lj[now]) f[now]+=Hsh(f[to]),cnt[f[now]]++;
id[f[now]].push_back(now);
}
inline ull dfs_a(int now,int x) {
ull res=x;
for(auto to:lj_a[now]) res+=Hsh(dfs_a(to,x));
return res;
}
inline ull dfs_b(int now,int x) {
ull res=x;
for(auto to:lj_b[now]) res+=Hsh(dfs_b(to,x));
return res;
}
inline void print(int now,int fath) {
cout<<fath<<" ";
int id=++dfn;
for(auto to:lj[now]) print(to,id);
}
inline void clear() {
id.clear(),mark.clear(),vis.clear(),cnt.clear();
for(int i=1; i<=na; ++i) lj_a[i].clear();
for(int i=1; i<=nb; ++i) lj_b[i].clear();
for(int i=1; i<=n; ++i) lj[i].clear();
}
inline void solve() {
// cout<<"-------------------------------------------\n";
clear();
na=read(),nb=read(),n=read();
for(int i=1; i<=na; ++i) lj_a[read()].push_back(i);
for(int i=1; i<=nb; ++i) lj_b[read()].push_back(i);
for(int i=1; i<=n; ++i) lj[read()].push_back(i);
dfs(1);
for(auto it:cnt) {
int x=it.first,Cnt=it.second+1;
if(Cnt>=na) mark[dfs_a(1,x)]=x;
if(Cnt>=nb) vis[dfs_b(1,x)]=x;
}
// cout<<"--------------------------------------\n";
// for(auto it:cnt) cout<<it.first<<" "<<it.second<<"\n";
// cout<<"--------------------------------------\n";
// for(auto it:mark) cout<<it.first<<" "<<it.second<<"\n";
// cout<<"--------------------------------------\n";
// for(auto it:vis) cout<<it.first<<" "<<it.second<<"\n";
// cout<<"--------------------------------------\n";
for(auto it:mark) {
ull rx=f[1]-it.first;
if(vis.count(f[1]-it.first)) {
int u=id[it.second][0],v=id[vis[rx]][0];
// int u=it.second,v=vis[f[1]-it.first];
// u=id[u][0],v=id[v][0];
cout<<siz[u]<<" "<<siz[v]<<"\n";
dfn=0,print(u,0),puts("");
dfn=0,print(v,0),puts("");
return ;
}
}
puts("Impossible");
}
signed main() {
int T=read();
while(T--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 11244kb
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: 135ms
memory: 33100kb
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: 0ms
memory: 11100kb
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