QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721807 | #9459. Tree Equation | chrhaa | AC ✓ | 211ms | 25936kb | C++14 | 3.2kb | 2024-11-07 16:54:41 | 2024-11-07 16:54:41 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int N=100005;
inline int read(){
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
#define ull unsigned long long
const ull B=233;
inline ull shift(ull x){
x^=B;
x^=x<<13;
x^=x>>7;
x^=x<<17;
return x^B;
}
struct tree{
int sz;
ull h;
inline tree operator+=(const tree x){
sz+=x.sz;
h+=shift(x.h);
return *this;
}
inline bool operator<(const tree x)const{
return sz==x.sz?h<x.h:sz<x.sz;
}
inline bool operator==(const tree x)const{
return sz==x.sz&&h==x.h;
}
};
#define vint vector<int>
int T,n,p,cnt,id[N],d[N];
bool vis[N];
tree t[N];
vint a,b,c,X,Y,ea[N],eb[N],ec[N];
vector<tree> h;
map<tree,int> m;
void dfs(int x,vint *e){
if(d[x]>d[p]) p=x;
for(int v:e[x]){
d[v]=d[x]+1;
dfs(v,e);
}
}
void dfsX(int x){
id[x]=++cnt;
if(x!=p) X.push_back(id[c[x-1]]);
else X.push_back(0);
for(int v:ec[x]) dfsX(v);
}
void dfsY(int x){
id[x]=++cnt;
if(x!=p) Y.push_back(id[c[x-1]]);
else Y.push_back(0);
for(int v:ec[x]) dfsY(v);
}
tree calc1(int x,vint *e){
vector<tree> f;
tree res={1,1};
for(int v:e[x]) f.push_back(calc1(v,e));
sort(f.begin(),f.end());
for(tree v:f) res+=v;
return res;
}
tree calc2(int x,vint *e){
vector<tree> f;
tree res={1,1};
for(int v:e[x]) f.push_back(calc2(v,e));
for(tree v:h) f.push_back(v);
sort(f.begin(),f.end());
for(tree v:f) res+=v;
return res;
}
bool solve(){
int i,l;
n=c.size();
for(i=0;i<=n;i++){
vis[i]=false;
ea[i].clear();
eb[i].clear();
ec[i].clear();
}
for(i=1;i<a.size();i++) ea[a[i]].push_back(i+1);
for(i=1;i<b.size();i++) eb[b[i]].push_back(i+1);
for(i=1;i<c.size();i++) ec[c[i]].push_back(i+1);
p=d[1]=0;
dfs(1,ea);
l=d[p];
p=d[1]=0;
dfs(1,ec);
l=d[p]-l;
if(l<0) return false;
for(;l;l--) p=c[p-1];
cnt=0;
X.clear();
dfsX(p);
h.clear();
for(int v:ec[p]) h.push_back(calc1(v,ec));
m.clear();
for(int v:ea[1]) m[calc2(v,ea)]++;
for(tree v:h) m[v]++;
vint tmp=ec[1];
ec[1].clear();
for(int v:tmp){
tree w=calc1(v,ec);
if(m[w]){
m[w]--;
vis[v]=true;
}else ec[1].push_back(v);
}
for(auto _:m) if(_.second) return false;
p=d[1]=0;
dfs(1,eb);
l=d[p];
p=d[1]=0;
dfs(1,ec);
l=d[p]-l;
if(l<0) return false;
for(;l;l--) p=c[p-1];
cnt=0;
Y.clear();
dfsY(p);
h.clear();
for(int v:ec[p]) h.push_back(calc1(v,ec));
return calc2(1,eb)==calc1(1,ec);
}
void print(vint x,vint y){
printf("%d %d\n",x.size(),y.size());
for(int i=0;i<x.size();i++) printf("%d ",x[i]);
puts("");
for(int i=0;i<y.size();i++) printf("%d ",y[i]);
puts("");
}
signed main(){
for(int T=read(),i;T;T--){
a.resize(read());
b.resize(read());
c.resize(read());
for(i=0;i<a.size();i++) a[i]=read();
for(i=0;i<b.size();i++) b[i]=read();
for(i=0;i<c.size();i++) c[i]=read();
if(solve()) print(X,Y);
else{
swap(a,b);
if(solve()) print(Y,X);
else puts("Impossible");
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11280kb
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: 211ms
memory: 25936kb
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:
3 1 0 1 1 0 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 2 1 1 1 1 0 0 8 2 0 1 1 3 3 3 1 1 0 1 1 1 0 0 4 1 0 1 1 1 0 3 1 0 1 1 0 5 1 0 1 2 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 2 1 0 1 0 5 1 0 1 1 1 1 0 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: 11400kb
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 2 2 1
result:
ok 1 cases passed
Extra Test:
score: 0
Extra Test Passed