QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721103 | #9459. Tree Equation | konyakest | AC ✓ | 210ms | 22704kb | C++17 | 2.9kb | 2024-11-07 15:15:29 | 2024-11-07 15:15:29 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i,j,k) for(auto i=j;i<=(decltype(i))k;i++)
#define x first
#define y second
#define exec(...) [&](){__VA_ARGS__}()
#define endl '\n'
#define os ostream
#define pb push_back
#define view(x) begin(x),end(x)
#define lambda [&]
using namespace std;
using ll=long long;
template<typename T>void ckmin(T& x,T y){x=min(x,y);}
template<typename T>void ckmax(T& x,T y){x=max(x,y);}
#ifdef DEBUG
template<typename T1,typename T2>os& operator<<(os&,pair<T1,T2>);
template<typename T,typename=decltype(T().begin()),typename=enable_if_t<!is_same_v<decay_t<T>,string>>>os& operator<<(os& out,T x){auto n=0u;out<<"{";for(auto i:x) out<<i<<(++n==x.size()?"":",");return out<<"}";}
template<typename ...T>os& operator<<(os& out,tuple<T...> x){return apply(lambda(T... x){auto n=0u;out<<"{";((out<<x<<(++n==sizeof...(T)?"":",")),...);},x),out<<"}";}
template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x){return out<<tuple(x);}
#define debug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = "<<std::make_tuple(__VA_ARGS__)<<endl
#else
#define debug(...) (void)0
#endif
const int maxn=1e5+5;
vector<int> A[maxn],B[maxn],C[maxn];
int na,nb,nc,x,rta,rtb,rtc;
size_t gethsh(size_t x){return hash<bitset<64>>()(x);}
size_t get_hsh_sum(int u,size_t extra,vector<int> (&v)[maxn]){
size_t ans=extra;
for(auto i:v[u]) ans+=gethsh(get_hsh_sum(i,extra,v));
return ans;
}
int siz[maxn];
size_t hsh[maxn];
map<size_t,int> cnt;
map<size_t,pair<int,int>> fn;
void init(int u){
siz[u]=1;
for(auto i:C[u]) init(i),siz[u]+=siz[i];
sort(view(C[u]),lambda(int x,int y){return siz[x]<siz[y];});
int tot=0;
hsh[u]=0;
cnt[0]++,fn[0]={u,-1};
for(auto i:C[u]){
hsh[u]+=gethsh(hsh[i]),cnt[hsh[u]]++;
fn[hsh[u]]={u,tot++};
}
}
void dfs(int u,int f,vector<int>& fn){
fn.pb(f);
int cur=fn.size();
for(auto i:C[u]) dfs(i,cur,fn);
}
vector<int> getfn(size_t hsh){
int u,i;
tie(u,i)=fn[hsh];
vector<int> fn={0};
F(j,0,i) dfs(C[u][j],1,fn);
return fn;
}
void solve(){
init(rtc);
map<size_t,size_t> all[2];
for(auto i:cnt){
if(i.y>=na-1) all[0][get_hsh_sum(rta,i.x,A)]=i.x;
if(i.y>=nb-1) all[1][get_hsh_sum(rtb,i.x,B)]=i.x;
}
for(auto i:all[0]) if(all[1].count(hsh[rtc]-i.x)){
debug(i.y,all[1][hsh[rtc]-i.x]);
auto f1=getfn(i.y),f2=getfn(all[1][hsh[rtc]-i.x]);
cout<<f1.size()<<" "<<f2.size()<<endl;
for(auto i:f1) cout<<i<<" ";
cout<<endl;
for(auto i:f2) cout<<i<<" ";
return;
}
cout<<"Impossible"<<endl;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
F(i,1,na) A[i].clear();
F(i,1,nb) B[i].clear();
F(i,1,nc) C[i].clear();
cnt.clear(),fn.clear();
cin>>na>>nb>>nc;
F(i,1,na) cin>>x,A[x].pb(i),(x==0)&&(rta=i);
F(i,1,nb) cin>>x,B[x].pb(i),(x==0)&&(rtb=i);
F(i,1,nc) cin>>x,C[x].pb(i),(x==0)&&(rtc=i);
solve();
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11312kb
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: 210ms
memory: 22704kb
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 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 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 0 1 4 0 0 1 1 1 1 4 ...
result:
ok 11122 cases passed
Test #3:
score: 0
Accepted
time: 2ms
memory: 10640kb
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