QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#717075 | #9459. Tree Equation | byron10000 | AC ✓ | 175ms | 33912kb | C++14 | 3.5kb | 2024-11-06 16:48:34 | 2024-11-06 16:48:34 |
Judging History
answer
#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define _UN using namespace
using namespace std;
const int MAXN=1e5+10;
typedef uint64_t Hash;
int _curcas;
Hash hash_(Hash x){ return _Hash_bytes(&x,sizeof(x),0xc70f6907ul); }
struct Tree{
int n,mxdep; vector<int> G[MAXN];
void clear(){
RNG(u,1,n) G[u].clear();
mxdep=0;
}
void dfs2(int u,int d){
mxdep=max(mxdep,d);
for(int v:G[u]) dfs2(v,d+1);
}
void init(){
clear();
RNG(u,1,n){
int fa; cin>>fa;
if(fa) G[fa].push_back(u);
}
dfs2(1,0);
}
Hash H[MAXN];
void calc(int u,Hash a){
H[u]=1+a;
for(int v:G[u]) calc(v,a),H[u]+=hash_(H[v]);
}
int dfs1(const Tree& o,int ou){
int u=++n;
G[u]=o.G[ou];
for(int& v:G[u]) v=dfs1(o,v);
return u;
}
void copy(const Tree& o,int u){
clear(); n=0;
dfs1(o,u);
}
void dbg(){
RNG(u,1,n){
for(int v:G[u]) cerr<<u<<" "<<v<<"\n";
}
cerr<<"\n";
}
void print(){
static int fa[MAXN];
RNG(u,1,n){
for(int v:G[u]) fa[v]=u;
}
RNG(u,1,n) cout<<fa[u]<<" ";
cout<<"\n";
}
} A,B,C,C1,X,Y;
void swap(Tree& a,Tree& b){
swap(a.n,b.n),swap(a.mxdep,b.mxdep);
RNG(i,1,max(a.n,b.n)) swap(a.G[i],b.G[i]);
}
int tp[MAXN];
void dfs1(int u,int d,int& mxd,int td,pair<int,int>& a){
int mxd1=d;
for(int v:C.G[u]){
if(!tp[v]) dfs1(v,d+1,mxd1,td,a);
}
mxd=max(mxd,mxd1);
if(d==td) a=max(a,pair<int,int>{mxd1,u});
}
bool solve(){
fill_n(tp+1,C.n,0);
C.calc(1,0);
pair<int,int> a{0,0};
{ int _; dfs1(1,0,_,A.mxdep,a); }
if(!a.second) return 0;
X.copy(C,a.second);
X.calc(1,0);
A.calc(1,X.H[1]-1);
auto match_edge=[](const Tree& T,int t)->bool{
int c=0;
unordered_map<Hash,int> mp;
for(int u:T.G[1]) mp[T.H[u]]++,c++;
for(int u:C.G[1]){
if(!tp[u]){
auto it=mp.find(C.H[u]);
if(it!=mp.end()&&it->second>0) it->second--,c--,tp[u]=t;
}
}
return !c;
};
bool flag=1;
flag&=match_edge(X,1);
flag&=match_edge(A,2);
if(!flag) return 0;
pair<int,int> b{0,0};
{ int _; dfs1(1,0,_,B.mxdep,b); }
if(!b.second) return 0;
Y.copy(C,b.second);
Y.calc(1,0);
B.calc(1,Y.H[1]-1);
flag&=match_edge(Y,3);
flag&=match_edge(B,4);
if(!flag) return 0;
for(int v:C.G[1]) flag&=!!tp[v];
return flag;
}
void case_main(){
cin>>A.n>>B.n>>C.n;
A.init(),B.init(),C.init();
// A.dbg(),B.dbg(),C.dbg();
if(!solve()){
swap(A,B);
if(!solve()){ cout<<"Impossible\n"; return; }
swap(X,Y);
}
cout<<X.n<<" "<<Y.n<<"\n";
X.print(),Y.print();
}
int main(){
#if defined(_LOCAL_)
freopen("in","r",stdin);
// freopen("out","w",stdout);
// freopen("/dev/null","w",stderr);
#else
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
#endif
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int cas; cin>>cas;
RNG(_,1,cas) _curcas=_,case_main();
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 21600kb
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: 175ms
memory: 33912kb
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 1 1 4 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: 22416kb
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