QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722910 | #9459. Tree Equation | Chendaqian | AC ✓ | 442ms | 23496kb | C++14 | 2.3kb | 2024-11-07 20:34:24 | 2024-11-07 20:34:25 |
Judging History
answer
// dadaaa QwQ
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e5+10;
ull seed=rnd();
ull geths(ull x) {
return x*x*x*x+x*x*x*seed+x*x*seed*seed+x*seed*seed*seed+seed*seed*seed*seed;
}
int T,n[3],f[3][N];
vector<int> e[3][N];
int sum[N];
unordered_map<ull,int> mp;
unordered_map<ull,ull> vis[2];
unordered_map<ull,int> pid;
ull hs[N];
void dfs(int x) {
sum[x]=1;
for(int v:e[2][x]) {
dfs(v);
sum[x]+=sum[v];
}
sort(e[2][x].begin(),e[2][x].end(),[&](int a,int b) {
return sum[a]<sum[b];
});
hs[x]=0;
mp[hs[x]]++;
for(int v:e[2][x]) {
hs[x]+=geths(hs[v]);
mp[hs[x]]++;
}
pid[hs[x]]=x;
}
ull dfscalc(int Trr,int x,ull w) {
ull res=w;
for(int v:e[Trr][x]) {
res+=geths(dfscalc(Trr,v,w));
}
return res;
}
vector<int> ans[2];
void print(int Trr,int x,int Fa) {
ans[Trr].push_back(Fa);
int Id=ans[Trr].size();
for(int v:e[2][x]) print(Trr,v,Id);
}
int main() {
// cerr<<seed<<"\n";
cin>>T;
for(int Test=1;Test<=T;Test++) {
// cerr<<"Start\n";
cin>>n[0]>>n[1]>>n[2];
for(int Trr=0;Trr<3;Trr++) {
for(int i=1;i<=n[Trr];i++) {
cin>>f[Trr][i];
e[Trr][f[Trr][i]].push_back(i);
}
}
dfs(1);
// for(int i=1;i<=n[2];i++) cerr<<hs[i]<<' ';
// cerr<<'\n';
for(auto i:mp) {
if(i.second>=n[0]-1) {
vis[0][dfscalc(0,1,i.first)]=i.first;
// cerr<<0<<' '<<pid[i.first]<<'\n';
}
if(i.second>=n[1]-1) {
vis[1][dfscalc(1,1,i.first)]=i.first;
// cerr<<1<<' '<<pid[i.first]<<'\n';
}
}
bool fl=0;
for(auto i:vis[0]) {
if(vis[1].find(hs[1]-i.first)!=vis[1].end()) {
int rt[2]={pid[i.second],pid[vis[1][hs[1]-i.first]]};
// cerr<<rt[0]<<' '<<rt[1]<<'\n';
ans[0].clear(),ans[1].clear();
print(0,rt[0],0),print(1,rt[1],0);
cout<<ans[0].size()<<' '<<ans[1].size()<<'\n';
for(int p:ans[0]) cout<<p<<' ';
cout<<'\n';
for(int p:ans[1]) cout<<p<<' ';
cout<<'\n';
fl=1;
break;
}
}
if(!fl) cout<<"Impossible\n";
for(int Trr=0;Trr<3;Trr++) {
for(int i=0;i<=n[Trr];i++) e[Trr][i].clear();
}
mp.clear();
vis[0].clear(),vis[1].clear();
pid.clear();
}
return 0;
}
/*
cd QOJ9459
g++ code.cpp -o code -std=c++14 -Wall -O2
./code
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10696kb
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: 442ms
memory: 23496kb
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