QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#634570 | #9459. Tree Equation | ucup-team052# | AC ✓ | 212ms | 23324kb | C++14 | 4.2kb | 2024-10-12 17:38:16 | 2024-10-12 17:38:17 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int T,na,nb,nc;
int fa[3][100005];
namespace solver{
int n,m,sz,_out;
vector <int> son[100005];
int fa[4][100005],label[2][100005];
ull h(ull x){
return x * x * 127 + x * 114 + 514;
}
ull f(ull x){
return h(x >> 30) + h(x & ((1u << 30) - 1));
}
int dep[100005],siz[100005],tag[100005];
ull A[2][100005];
__gnu_pbds::gp_hash_table <ull,int> buc;
void dfs(int u){
label[0][u] = ++sz;
fa[2][sz] = label[0][fa[1][u]];
for(int v:son[u]){
if(tag[v]) continue;
dfs(v);
}
}
void dfs2(int u,int f){
label[1][u] = ++_out;
fa[3][_out] = label[1][f];
for(int v:son[u]) dfs2(v,u);
}
int solve(){
rep(u,1,m) son[u].clear();
rep(u,2,m) son[fa[1][u]].eb(u);
/* printf("try solve n=%d m=%d\n",n,m);
rep(u,1,n) printf("%d ",fa[0][u]);
printf("\n");
rep(u,1,m) printf("%d ",fa[1][u]);
printf("\n");*/
int p = 1,d1 = 0,d2 = 0;
rep(u,2,m){
dep[u] = dep[fa[1][u]] + 1;
if(dep[u] > dep[p]) p = u;
}
d1 = dep[p];
fill(siz,siz + m + 1,1);
fill(A[0],A[0] + m + 1,1);
per(u,m,2){
siz[fa[1][u]] += siz[u];
A[0][fa[1][u]] += f(A[0][u]);
}
rep(u,2,n){
dep[u] = dep[fa[0][u]] + 1;
chkmax(d2,dep[u]);
}
d1 -= d2;
if(d1 < 0) return 0;
while(d1){
p = fa[1][p];
d1--;
}
// printf("p=%d\n",p);
if(!p || 1ll * siz[p] * n > m) return 0;
fill(A[1],A[1] + n + 1,A[0][p]);
per(u,n,2) A[1][fa[0][u]] += f(A[1][u]);
__gnu_pbds::gp_hash_table <ull,int> ovo;
buc.swap(ovo);
rep(u,2,n) if(fa[0][u] == 1) buc[A[1][u]]++;
rep(u,1,m) if(fa[1][u] == p) buc[A[0][u]]++;
fill(tag,tag + m + 1,0);
rep(u,2,m){
if(fa[1][u] == 1 && buc[A[0][u]]){
tag[u] = 1;
// printf("del %d\n",u);
buc[A[0][u]]--;
}
}
for(pair <ull,int> I:buc) if(I.second) return 0;
sz = _out = 0;
dfs(1);
dfs2(p,0);
/* printf("succ!\n");
printf("sz=%d\n",sz);
rep(u,1,sz) printf("%d ",fa[2][u]);
printf("\n_out=%d\n",_out);
rep(u,1,_out) printf("%d ",fa[3][u]);
printf("\n");*/
return 1;
}
}
int sz;
int temp[100005];
int check(int tp){
solver::n = na;solver::m = nc;
rep(u,1,na) solver::fa[0][u] = fa[0][u];
rep(u,1,nc) solver::fa[1][u] = fa[2][u];
if(!solver::solve()) return 0;
solver::n = nb;solver::m = solver::sz;
rep(u,1,nb) solver::fa[0][u] = fa[1][u];
rep(u,1,solver::m) solver::fa[1][u] = solver::fa[2][u];
sz = solver::_out;
rep(u,1,sz) temp[u] = solver::fa[3][u];
if(!solver::solve()) return 0;
if(solver::sz != 1) return 0;
// printf("[output]\n");
if(!tp){
printf("%d %d\n",sz,solver::_out);
rep(u,1,sz) printf("%d%c",temp[u]," \n"[u == sz]);
rep(u,1,solver::_out) printf("%d%c",solver::fa[3][u]," \n"[u == solver::_out]);
}else{
printf("%d %d\n",solver::_out,sz);
rep(u,1,solver::_out) printf("%d%c",solver::fa[3][u]," \n"[u == solver::_out]);
rep(u,1,sz) printf("%d%c",temp[u]," \n"[u == sz]);
}
return 1;
}
void solve(){
scanf("%d%d%d",&na,&nb,&nc);
rep(u,1,na) scanf("%d",&fa[0][u]);
rep(u,1,nb) scanf("%d",&fa[1][u]);
rep(u,1,nc) scanf("%d",&fa[2][u]);
if(check(0)) return;
swap(na,nb);
rep(u,1,max(na,nb)) swap(fa[0][u],fa[1][u]);
if(check(1)) return;
printf("Impossible\n");
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8404kb
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: 212ms
memory: 23324kb
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 0 1 4 0 0 1 1 1 1 4 0 0 1 1 1 1 2 0 0 1 1 3 ...
result:
ok 11122 cases passed
Test #3:
score: 0
Accepted
time: 3ms
memory: 12012kb
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