QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#671145 | #9459. Tree Equation | EnofTaiPeople | AC ✓ | 196ms | 173880kb | C++14 | 7.5kb | 2024-10-24 11:14:48 | 2024-10-24 11:14:49 |
Judging History
answer
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,fast-math",3)
#define cln cerr<<"Line: "<<__LINE__<<" "
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define mkp make_pair
#define MST(x) memset(x,0,sizeof(x))
#define all(x) x.begin(),x.end()
using namespace std;
constexpr int N=(1<<21)+100,_g=3,M1=1e9+7,M2=1e9+9,M=998244353;
namespace fast_io{
char buf[N+10],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2))?EOF:*p1++
template<typename _Tp>
void read(_Tp &x){
int f=0;for(c=gc;c<48;c=gc)f^=c=='-';
for(x=0;c>47;x=(x<<1)+(x<<3)+(48^c),c=gc);
if(f)x=-x;
}
template<typename _Tp,typename..._tps>
void read(_Tp &x,_tps&...y){read(x),read(y...);}
char ob[N+100],stk[505];int tp,ot;
void fls(){fwrite(ob,1,ot,stdout),ot=0;}
int cntt;
template<typename _Tp>
static inline void write(_Tp x,char c){
if(!cntt)atexit(fls),cntt=1;
while(x>9)stk[++tp]=48^(x%10),x/=10;
for(ob[ot++]=48^x;tp;ob[ot++]=stk[tp--]);
ob[ot++]=c;if(ot>N)fls();
}
}using fast_io::read;
using fast_io::write;
using ll=long long;
#define pli pair<ll,int>
#define pii pair<int,int>
using ul=unsigned long long;
using ld=double;
mt19937_64 rg(random_device{}());
const ll INF=3e18;
template<typename tp1,typename tp2>
void ckmx(tp1 &x,const tp2 &y){if(x<y)x=y;}
template<typename tp1,typename tp2>
void ckmn(tp1 &x,const tp2 &y){if(x>y)x=y;}
void add(int &x,int y){if((x+=y)>=M)x-=M;}
void del(int &x,int y){if((x-=y)<0)x+=M;}
void add(int &x,ul y,int z){x=(y*z+x)%M;}
void del(int &x,ul y,int z){if((x-=y*z%M)<0)x+=M;}
int qp(ll a,ll x=M-2){
int res=1;for(;x;x>>=1,a=a*a%M)
(x&1)&&(res=a*res%M);return res;
}
struct NTP{};
namespace MATH{
vector<int>jc,nv;
int dv2(int x){return x&1?x+M>>1:x>>1;}
int C(int n,int m){
assert(m<=n);
return 1ll*jc[n]*nv[m]%M*nv[n-m]%M;
}
int P(int n,int m){
return 1ll*jc[n]*nv[n-m]%M;
}
int D(int n,int m){
if(n<0||m<0)return 0;
if(!n)return 1;
if(!m)return 0;
return C(n+m-1,m-1);
}
void init(int n,int tp=1){
int x;
jc.resize(n+2),nv.resize(n+2);
jc[0]=nv[0]=jc[1]=nv[1]=1;
for(x=2;x<=n;++x){
jc[x]=1ll*x*jc[x-1]%M;
nv[x]=ll(M-M/x)*nv[M%x]%M;
}
if(tp)for(x=1;x<=n;++x)nv[x]=1ll*nv[x-1]*nv[x]%M;
}
}
struct DET{
int a[3005][3005],n;
int run(){
if(!n)return 1;
int x,y,z,k,res=1;
for(x=1;x<=n;++x){
for(y=x;y<=n&&!a[y][x];++y);
if(y>n)return 0;
if(y>x){
for(k=1;k<=n;++k)swap(a[x][k],a[y][k]);
res&&(res=M-res);
}
k=qp(a[x][x]);
res=1ll*res*a[x][x]%M;
for(z=1;z<=n;++z)
a[x][z]=1ll*a[x][z]*k%M;
for(y=1;y<=n;++y)
if(x!=y){
k=a[y][x];
for(z=1;z<=n;++z)
del(a[y][z],a[x][z],k);
}
}
for(x=1;x<=n;++x)
res=1ll*res*a[x][x]%M;
return res;
}
}det;
ll Gcd(ll x,ll y){
if(!x||!y)return x|y;
int k=min(ctz(x),ctz(y));
ll d;y>>=ctz(y);
while(x){
x>>=ctz(x),d=x-y;
if(x<y)y=x;
if(d<0)x=-d;
else x=d;
}return y<<k;
}
using ll=long long;
using ul=unsigned long long;
constexpr int bceil(int n){return 1<<(std::__lg(n-1)+1);}
template<int mod>struct NTT{
constexpr int dil(int x){return x>>31?x+mod:x;}
constexpr int mul(ul x,int y){return x*y%mod;}
constexpr int qpow(int a,int b,int r=1){for(;b;a=mul(a,a),b>>=1){r=b&1?mul(r,a):r;}return r;}
int w[N>>1],wI[N>>1];
void init(int n){
int l=bceil(n)>>1;w[0]=wI[0]=1;
for(int i=1;i<l;i<<=1){w[i]=qpow(_g,((mod-1)>>2)/i),wI[i]=qpow(_g,mod-1-((mod-1)>>2)/i);}
for(int i=1;i<l;++i){w[i]=mul(w[i&(i-1)],w[i&-i]),wI[i]=mul(wI[i&(i-1)],wI[i&-i]);}
}
void dif(int *f,int lim){
for(int l=lim>>1,r=lim;l;l>>=1,r>>=1)
for(int*j=f,*o=w;j!=f+lim;j+=r,++o)
for(int*k=j,x,y;k!=j+l;++k)
(x=*k)>=mod&&(x-=mod),y=mul(k[l],*o),*k=x+y,k[l]=x-y+mod;
}
void dit(int *f,int lim){
for(int l=1,r=2;l<lim;l<<=1,r<<=1)
for(int*j=f,*o=wI;j!=f+lim;j+=r,++o)
for(int*k=j,x,y;k!=j+l;++k)
x=*k,y=mod-k[l],(*k=x-y)<0&&(*k+=mod),k[l]=mul(x+y,*o);
for(int i=0,p=mod-(mod-1)/lim;i<lim;++i)f[i]=1ll*f[i]*p%mod;
}
void mul(int *f,int *g,int n){
dif(f,n),dif(g,n);
for(int i=0;i<n;++i)f[i]=1ll*f[i]*g[i]%M;
dit(f,n);
}
void mul(int *f,int n){
dif(f,n);int i;
for(i=0;i<n;++i)f[i]=1ll*f[i]*f[i]%M;
dit(f,n);
}
};
struct Htb{
static constexpr int M=1e7+19;
int hd[M+3],to[N],ct;ll ed[N];
static int hc(ul v){
v^=v<<13,v^=v>>7;
return (v^(v<<17))%M;
}
int operator[](ll x){
int &p=hd[hc(x)];
for(int i=p;i;i=to[i])
if(ed[i]==x)return i;
ed[++ct]=x,to[ct]=p;
return p=ct;
}
void clear(){while(ct)hd[hc(ed[ct--])]=0;}
}ht;
// NTT<M>ntt;
// using namespace MATH;
using LL=__int128_t;
using UL=__uint128_t;
using vt=vector<int>;
int T,n,m;
ul fuc(ul v){
v^=v<<13,v^=v>>7;
return v^(v<<17);
}
vt v1,v2;
struct TREE{
int n,de[N],sz[N];ul sm[N];
vt lk[N];
int init(int _n){
n=_n;
int i,j,k,l,r,x,y,z,t;
for(x=1,cin>>k;x<=n;++x)lk[x].clear();
for(x=2;x<=n;++x)
cin>>k,de[x]=de[k]+1,lk[k].push_back(x);
for(x=n;x;--x){
sz[x]=1;
for(int y:lk[x])sz[x]+=sz[y];
}
return *max_element(de+1,de+n+1);
}
void dp(ul v){
for(int x=n;x;--x){
sm[x]=v;
for(int y:lk[x])sm[x]+=fuc(sm[y]);
}
}
void sol(vt &at,int x){
int cnt=1;
function<void(int)>dfs=[&](int x){
int r=cnt;
for(int y:lk[x]){
at.push_back(r),++cnt;
dfs(y);
}
};dfs(x);
}
}A,B,C;
struct dat{
ul v;int x;
bool operator<(const dat &z)const{
return v<z.v;
}
}b1[N],b2[N];
int t1,t2;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int i,j,k,l,r,x,y,z,t;
for(cin>>T;T--;){
cin>>x>>y>>z;
int _a=A.init(x),_b=B.init(y);
C.init(z),C.dp(41719),t1=t2=0;
set<pair<ul,int>>st;
for(x=1;x<=C.n;++x){
if(!st.insert(mkp(C.sm[x],C.de[x])).second)continue;
if(C.de[x]==_a&&1ll*C.sz[x]*A.n<=C.n)
A.dp(C.sm[x]),b1[++t1]={A.sm[1]-41719,x};
if(C.de[x]==_b&&1ll*C.sz[x]*B.n<=C.n)
B.dp(C.sm[x]),b2[++t2]={C.sm[1]-B.sm[1],x};
}
sort(b1+1,b1+t1+1);
sort(b2+1,b2+t2+1);
for(x=l=1;x<=t1;++x){
while(l<=t2&&b2[l].v<b1[x].v)++l;
if(l<=t2&&b2[l].v==b1[x].v){
v1=v2={0};
C.sol(v1,b1[x].x);
C.sol(v2,b2[l].x);
printf("%d %d\n",int(v1.size()),int(v2.size()));
for(int p:v1)printf("%d ",p);puts("");
for(int p:v2)printf("%d ",p);puts("");
goto lc1;
}
}puts("Impossible");lc1:;
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 157660kb
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: 196ms
memory: 173880kb
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:
1 3 0 0 1 1 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 2 8 0 1 0 1 1 3 3 3 1 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 1 5 0 0 1 1 1 1 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: 19ms
memory: 160592kb
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