QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#636842 | #9459. Tree Equation | ucup-team191# | AC ✓ | 382ms | 14224kb | C++23 | 5.6kb | 2024-10-13 03:21:40 | 2024-10-13 18:43:02 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
#define all(a) begin(a),end(a)
#define pb push_back
const int N=300010,MOD=1e9+7,MOD2=998244353;
const char en='\n';
const ll LLINF=1ll<<60;
inline int add(int A, int B, int M) {
if(A + B >= M) return A + B - M;
return A + B;
}
inline int mul(int A, int B, int M) {
return (long long)A * B % M;
}
inline pii add(pii A, pii B)
{
return {add(A.x,B.x,MOD),add(A.y,B.y,MOD2)};
}
inline pii mul(pii A, int B)
{
return {mul(A.x,B,MOD),mul(A.y,B,MOD2)};
}
inline pii mul(pii A, pii B)
{
return {mul(A.x,B.x,MOD),mul(A.y,B.y,MOD2)};
}
pii tree_hash(int x, vector < vi > &t, vector < bool > &zab, vector < pii > &gdje) {
vector < pii > hsh_djece;
for(int y : t[x]) if(!zab[y]) {
hsh_djece.pb(tree_hash(y, t, zab, gdje));
}
int baza = 1e6 + 17 - (int)hsh_djece.size();
sort(hsh_djece.begin(), hsh_djece.end());
pii ret = {baza,baza};
pii sad = {baza,baza};
for(pii x : hsh_djece) {
ret = add(ret, mul(x, sad));
sad = mul(sad, baza);
}
return gdje[x] = ret;
}
int t,na,nb,nc;
vi getPars(const vector<vi>&x)
{
int a=x.size();
vi pars(a);
pars[0]=-1;
for (int i=0;i<a;++i) for (auto b: x[i]) pars[b]=i;
return pars;
}
vector<vi> getMul(const vector<vi>&a,const vector<vi>&b)
{
vi ap=getPars(a),bp=getPars(b);
int as=a.size(),bs=b.size();
assert(as*1ll*bs<=nc);
vector<vi> nov(as*bs);
for (int va=0;va<as;++va) for (int vb=0;vb<bs;++vb)
{
int x=va*bs+vb;
if (x)
{
int p;
if (vb==0) p=ap[va]*bs;
else p=va*bs+bp[vb];
nov[p].pb(x);
}
}
return nov;
}
int ss[N];
void dfs1(int i,const vector<vi>&v)
{
ss[i]=1;
for (auto x: v[i])
{
dfs1(x,v);
ss[i]+=ss[x];
}
}
vi ord;
int ind[N];
void getSub(int i,const vector<vi>&v)
{
ind[i]=ord.size();
ord.pb(i);
for (auto x: v[i]) getSub(x,v);
}
vector<vi> extractSub(int i,vector<vi>&v)
{
ord.clear();
getSub(i,v);
int os=ord.size();
vector<vi> re(os);
for (auto x: ord) for (auto y: v[x])
{
//cout<<"extracting "<<x<<"->"<<y<<": "<<ind[x]<<"->"<<ind[y]<<endl;
re[ind[x]].pb(ind[y]);
}
return re;
}
bool solve(vector<vi>&cha,vector<vi>&chb,vector<vi>&chc,int maxc,int kak,bool flip)
{
vector<bool> zab(nc);
vector<pii> gdje(nc);
tree_hash(0,chc,zab,gdje);
for (int vx=1;vx<=maxc;++vx) if (maxc%vx==0)
{
if (vx*1ll*na>=nc) continue;
if ((nc+1-vx*1ll*na)%nb) continue;
ord.clear();
getSub(kak,chc);
int cd=0;
vi koj;
for (auto x: ord) if (ss[x]%vx==0) ++cd,koj.pb(x);
if (cd!=maxc/vx) continue;
if (ss[koj.back()]!=vx) continue;
vector<vi> xst=extractSub(koj.back(),chc);
//cout<<"extracted size "<<vx<<endl;
for (auto s: cha[0])
{
vector<vi> vca=extractSub(s,cha);
//cout<<"extracted "<<vca.size()<<"("<<s<<" from a)"<<endl;
/*cout<<"vca="<<en;
for (auto x: vca)
{
for (auto y: x) cout<<y<<' ';
cout<<en;
}
cout<<"xst="<<en;
for (auto x: xst)
{
for (auto y: x) cout<<y<<' ';
cout<<en;
}
cout<<endl;*/
vector<vi> mnozi=getMul(vca,xst);
//cout<<"mnozio"<<endl;
vector<pii> ng(mnozi.size());
vector<bool> nz(mnozi.size());
//cout<<"mnozio "<<vca.size()<<' '<<xst.size()<<endl;
if (gdje[kak]!=tree_hash(0,mnozi,nz,ng)) continue;
//cout<<"uspjeh!"<<endl;
multiset<pii> zamaknut;
for (auto s1: cha[0])
{
vca=extractSub(s1,cha);
mnozi=getMul(vca,xst);
ng=vector<pii>(mnozi.size());
nz=vector<bool>(mnozi.size());
zamaknut.insert(tree_hash(0,mnozi,nz,ng));
}
for (auto x: xst[0])
{
vector<vi> sta=extractSub(x,xst);
ng=vector<pii>(sta.size());
nz=vector<bool>(sta.size());
zamaknut.insert(tree_hash(0,sta,nz,ng));
}
ng=vector<pii>(nc);
nz=vector<bool>(nc);
int ns=nc;
for (auto x: chc[0]) if (zamaknut.find(gdje[x])!=zamaknut.end())
{
zamaknut.erase(zamaknut.find(gdje[x]));
nz[x]=1;
ns-=ss[x];
}
if (zamaknut.size()) break;
if (ns%nb) break;
//cout<<"vx="<<vx<<endl;
int vy=ns/nb;
int zad=-1;
for (int i=0;i<nc;++i)
{
if (nz[i]) for (auto x: chc[i]) nz[x]=1;
else
{
if (ss[i]%vy==0) zad=i;
}
}
if (zad==-1 || ss[zad]!=vy) break;
vector<vi> yst=extractSub(zad,chc);
vector<vi> mnoz2=getMul(chb,yst);
auto h1=tree_hash(0,chc,nz,ng);
vector<bool> nnz(mnoz2.size());
vector<pii> nng(mnoz2.size());
auto h2=tree_hash(0,mnoz2,nnz,nng);
if (h1!=h2) break;
vi parsx=getPars(xst),parsy=getPars(yst);
if (flip) swap(parsx,parsy);
int sx=parsx.size(),sy=parsy.size();
cout<<sx<<' '<<sy<<endl;
for (int i=0;i<sx-1;++i) cout<<parsx[i]+1<<' ';
cout<<parsx.back()+1<<endl;
for (int i=0;i<sy-1;++i) cout<<parsy[i]+1<<' ';
cout<<parsy.back()+1<<endl;
return 1;
}
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while (t--)
{
cin>>na>>nb>>nc;
vector<vi> cha(na),chb(nb),chc(nc);
for (int i=0;i<na;++i)
{
int x;
cin>>x;
if (i) cha[x-1].pb(i);
}
for (int i=0;i<nb;++i)
{
int x;
cin>>x;
if (i) chb[x-1].pb(i);
}
for (int i=0;i<nc;++i)
{
int x;
cin>>x;
if (i) chc[x-1].pb(i);
}
dfs1(0,chc);
int maxc=-1,kak=-1;
for (auto x: chc[0]) if (ss[x]>maxc)
{
maxc=ss[x];
kak=x;
}
if (solve(cha,chb,chc,maxc,kak,0)) continue;
swap(na,nb);
swap(cha,chb);
if (solve(cha,chb,chc,maxc,kak,1)) continue;
cout<<"Impossible"<<en;
//cout<<"done"<<endl;
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
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: 382ms
memory: 14224kb
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: 0ms
memory: 3656kb
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