QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #638990 | #9459. Tree Equation | ucup-team3282 | AC ✓ | 428ms | 47484kb | C++20 | 4.5kb | 2024-10-13 17:32:14 | 2024-10-13 18:43:07 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<vector>
using namespace std;
long long mod=1e9+7;
long long prim[1000050];
long long pow(long long r,long long b=mod-2){
if(b==1)return r;
long long ret=pow(r,mod>>1);
if(b&1)return ret*ret%mod*r%mod;
else ret*ret%mod;
}
struct node{
vector<int>lk;
long long hash=1;
int dep,sz;
}pt[500050];int tp=0;
void hsh(int p){
if(pt[p].sz==0){
pt[p].sz=1;pt[p].dep=1;
for(auto x:pt[p].lk){
hsh(x);
pt[p].dep=max(pt[p].dep,pt[x].dep+1);
pt[p].sz+=pt[x].sz;
pt[p].hash=(pt[p].hash*pt[x].hash)%mod;
}
pt[p].hash=pt[p].hash* prim[ pt[p].sz ]%mod;
}
return;
}
int a[500050],b[500050],c[500050];
int fd(int rt,int dep){
dep=pt[dep].dep;
int p=rt;
for(int i=1;i<dep;i++){
if(pt[p].lk.size()==0)return -1;
int r=pt[p].lk[0];
for(auto x:pt[p].lk){
if(pt[x].dep>pt[r].dep)r=x;
}
p=r;
}
return p;
}
long long multiply(int rt1,int rt2){
long long ret=1;
for(auto x:pt[rt2].lk){
ret=ret*pt[x].hash%mod;
}
for(auto x:pt[rt1].lk){
ret=ret*multiply(x,rt2)%mod;
}
ret=ret*prim[pt[rt1].sz*pt[rt2].sz]%mod;
return ret;
}
long long newroot(int rt,int rt1,int rt2){
int nrt=++tp;
unordered_map<int,int>mp;
for(auto x:pt[rt2].lk)mp[pt[x].hash]++;
for(auto x:pt[rt1].lk)mp[multiply(x,rt2)]++;
for(auto x:pt[rt].lk){
if(mp[pt[x].hash]>0){
mp[pt[x].hash]--;
}else{
pt[nrt].lk.push_back(x);
}
}
for(auto x:mp){
if(x.second!=0){
return -1;
}
}
hsh(nrt);
return nrt;
}
int cnt=0;
void otp(int p,int fa){
cout<<fa<<" ";
int id=++cnt;
for(auto x:pt[p].lk){
otp(x,id);
}
}
int main(){
for(int i=0;i<=1000005;i++){
prim[i]=(114514+i*19260817)%mod;
}
int t;cin>>t;while(t--){
while(tp>0){
pt[tp].lk.clear();
pt[tp].hash=1;
pt[tp].dep=pt[tp].sz=0;
tp--;
}
int na,nb,nc;
cin>>na>>nb>>nc;
for(int i=1;i<=na;i++){
a[i]=++tp;
int f;cin>>f;
if(f!=0){
pt[a[f]].lk.push_back(a[i]);
}
}
for(int i=1;i<=nb;i++){
b[i]=++tp;
int f;cin>>f;
if(f!=0){
pt[b[f]].lk.push_back(b[i]);
}
}
for(int i=1;i<=nc;i++){
c[i]=++tp;
int f;cin>>f;
if(f!=0){
pt[c[f]].lk.push_back(c[i]);
}
}
hsh(a[1]);
hsh(b[1]);
hsh(c[1]);
//a->b
// for(int i=1;i<=17;i++){
// cout<<i<<endl<<"->";
// for(auto x:pt[i].lk){
// cout<<x<<" ";
// }cout<<endl;
// }
// cout<<pt[a[1]].dep<<endl;
bool flag=false;
int fd1=fd(c[1],a[1]);
if(fd1!=-1){
// cout<<"A";
// cout<<fd1<<"->";
int nrt=newroot(c[1],a[1],fd1);
int fd2=fd(nrt,b[1]);
// cout<<fd2<<"->";
if(fd2!=-1){
if(pt[nrt].hash==multiply(b[1],fd2)){
//win！！！！！！！！！！！！！！！！！！！！！！！
cout<<pt[fd1].sz<<" "<<pt[fd2].sz<<endl;
cnt=0;otp(fd1,0);cout<<endl;
cnt=0;otp(fd2,0);cout<<endl;
flag=true;
}
}
}
if(flag)continue;
//b->a
fd1=fd(c[1],b[1]);
if(fd1!=-1){
// cout<<"B";
// cout<<fd1<<"->";
int nrt=newroot(c[1],b[1],fd1);
int fd2=fd(nrt,a[1]);
// cout<<fd2<<"->";
if(fd2!=-1){
if(pt[nrt].hash==multiply(a[1],fd2)){
//win！！！！！！！！！！！！！！！！！！！！！！！
cout<<pt[fd2].sz<<" "<<pt[fd1].sz<<endl;
cnt=0;otp(fd2,0);cout<<endl;
cnt=0;otp(fd1,0);cout<<endl;
flag=true;
}
}
}
if(flag)continue;
cout<<"Impossible"<<endl;
}
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 35008kb
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: 428ms
memory: 47484kb
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: 3ms
memory: 35000kb
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