QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#633387 | #9459. Tree Equation | ucup-team159# | AC ✓ | 240ms | 16144kb | C++20 | 10.3kb | 2024-10-12 15:13:39 | 2024-10-13 18:42:29 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < (t); ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define newline puts("")
#define vc vector
using namespace std;
template<class T> using vv = vc<vc<T>>;
template<class T> using PQ = priority_queue<T,vc<T>,greater<T>>;
using uint = unsigned; using ull = unsigned long long;
using vi = vc<int>; using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>;
using P = pair<int,int>; using vp = vc<P>; using vvp = vv<P>; using LP = pair<ll,ll>;
int geti(){int x;scanf("%d",&x);return x;}
vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;}
template<class T1,class T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.fi>>v.se;}
template<class T1,class T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;}
template<class T>istream& operator>>(istream&i,vc<T>&v){rep(j,sz(v))i>>v[j];return i;}
template<class T>string join(const T&v,const string&d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();}
template<class T>ostream& operator<<(ostream&o,const vc<T>&v){if(sz(v))o<<join(v," ");return o;}
template<class T>void vin(vc<T>&a){int n;cin>>n;a=vc<T>(n);cin>>a;}
template<class T>void vin(vv<T>&a){int n,m;cin>>n>>m;a=vv<T>(n,vc<T>(m));cin>>a;}
template<class T1,class T2>void operator--(pair<T1,T2>&a,int){a.fi--;a.se--;}
template<class T1,class T2>void operator++(pair<T1,T2>&a,int){a.fi++;a.se++;}
template<class T>void operator--(vc<T>&a,int){for(T&x:a)x--;}
template<class T>void operator++(vc<T>&a,int){for(T&x:a)x++;}
template<class T1,class T2>void operator+=(vc<T1>&a,T2 b){for(T1&x:a)x+=b;}
template<class T1,class T2>void operator-=(vc<T1>&a,T2 b){for(T1&x:a)x-=b;}
template<class T1,class T2>void operator*=(vc<T1>&a,T2 b){for(T1&x:a)x*=b;}
template<class T1,class T2>void operator/=(vc<T1>&a,T2 b){for(T1&x:a)x/=b;}
template<class T>void operator+=(vc<T>&a,const vc<T>&b){a.insert(a.end(),rng(b));}
template<class T1,class T2>pair<T1,T2>operator+(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi+b.fi,a.se+b.se};}
template<class T1,class T2>pair<T1,T2>operator-(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi-b.fi,a.se-b.se};}
template<class T>pair<T,T>operator*(const pair<T,T>&a,T b){return {a.fi*b,a.se*b};}
template<class T1,class T2>bool mins(T1& x,const T2&y){if(y<x){x=y;return true;}else return false;}
template<class T1,class T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;}
template<class T>T min(const vc<T>&a){return *min_element(rng(a));}
template<class T>T max(const vc<T>&a){return *max_element(rng(a));}
template<class Tx,class Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;}
template<class T>ll suma(const vc<T>&a){ll s=0;for(auto&&x:a)s+=x;return s;}
template<class T>ll suma(const vv<T>&a){ll s=0;for(auto&&x:a)s+=suma(x);return s;}
template<class T>void uni(T&a){sort(rng(a));a.erase(unique(rng(a)),a.end());}
template<class T>void prepend(vc<T>&a,const T&x){a.insert(a.begin(),x);}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return;}
#define yes { puts("Yes"); return;}
#define no { puts("No"); return;}
#define rtn(x) { cout<<(x)<<'\n'; return;} // flush!
#define yn {puts("Yes");}else{puts("No");}
random_device _rd;
struct xrand {
static const uint64_t _x = 88172645463325252ull;
uint64_t x;
xrand(): x(_x ^ (_rd()+time(0))) {}
xrand(uint64_t seed): x(_x ^ seed) {}
uint64_t get() {
x = x ^ (x << 7);
return x = x ^ (x >> 9);
}
ull operator()() { return get();}
ull operator()(ull n) { return get()%n;}
ll operator()(ll l, ll r) { return get()%(r-l+1) + l;}
} rnd;
template<typename T> void shuffle(vc<T>& a) {
for (int i = a.size(); i >= 2; --i) swap(a[i-1],a[rnd(i)]);
}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
// mod pair for hash
const int p1 = 33487;
struct mints {
template<int mod>
struct mint {
uint x;
mint(ull x=0):x(x%mod){}
mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
mint& operator*=(const mint& a) { x=(ull)x*a.x%mod; return *this;}
mint& operator/=(const mint& a) { x=(ull)x*a.pow(mod-2).x%mod; return *this;}
mint operator+(const mint& a)const{ return mint(*this) += a;}
mint operator-(const mint& a)const{ return mint(*this) -= a;}
mint operator*(const mint& a)const{ return mint(*this) *= a;}
mint operator/(const mint& a)const{ return mint(*this) /= a;}
bool operator<(const mint& a)const{ return x < a.x;}
bool operator==(const mint& a)const{ return x == a.x;}
mint pow(ll t) const {
if(!t) return 1;
mint res = pow(t/2);
res *= res;
return (t&1)?res*x:res;
}
};
mint<1011235817> x;
mint<987654347> y;
mints(ll x=0):x(x),y(x){}
mints& operator+=(const mints& a){ x+=a.x; y+=a.y; return *this;}
mints& operator-=(const mints& a){ x-=a.x; y-=a.y; return *this;}
mints& operator*=(const mints& a){ x*=a.x; y*=a.y; return *this;}
mints& operator/=(const mints& a){ x/=a.x; y/=a.y; return *this;}
mints operator+(const mints& a)const{ return mints(*this) += a;}
mints operator-(const mints& a)const{ return mints(*this) -= a;}
mints operator*(const mints& a)const{ return mints(*this) *= a;}
mints operator/(const mints& a)const{ return mints(*this) /= a;}
bool operator<(const mints& a)const{ return (x==a.x)?(y<a.y):(x<a.x);}
bool operator==(const mints& a)const{ return x==a.x && y==a.y;}
ll get() const { return (ull)x.x<<32|y.x;}
};
ostream& operator<<(ostream&o,const mints&a){o<<a.x.x*ll(1e9)+a.y.x;return o;}
using vm = vector<mints>;
//
tuple<int,vvi,vi> ing(int n) {
vvi to(n); vi pa(n);
int rt = -1;
rep(i,n) {
int p;
scanf("%d",&p);
if (p == 0) rt = i, pa[i] = -1;
else to[p-1].pb(i), pa[i] = p-1;
}
return {rt,to,pa};
}
struct Solver {
void solve() {
int na,nb,nc;
scanf("%d%d%d",&na,&nb,&nc);
auto [ra,ga,paa] = ing(na);
auto [rb,gb,pab] = ing(nb);
auto [rc,gc,pac] = ing(nc);
vi depa(na), depb(nb), depc(nc);
auto getdep = [&](vvi& g, int rt, vi& dep) {
auto dfs = [&](auto f, int v) -> P {
P res(0,v);
for (int u : g[v]) maxs(res,f(f,u));
dep[v] = res.fi;
res.fi++;
return res;
};
return dfs(dfs,rt).se;
};
getdep(ga,ra,depa);
getdep(gb,rb,depb);
int dv = getdep(gc,rc,depc);
vm hsh(nc);
rep(i,nc) hsh[i] = rnd();
vm hc(nc);
{
auto dfs = [&](auto f, int v) -> mints {
mints x = 1;
for (int u : gc[v]) x *= f(f,u);
x += hsh[depc[v]];
return hc[v] = x;
};
dfs(dfs,rc);
};
vc<pair<ll,int>> chs;
for (int ch : gc[rc]) chs.eb(hc[ch].get(),ch);
sort(rng(chs));
// cerr<<hc<<endl;
rep(ab,2) {
// cerr<<"ab: " << ab <<endl;
if ([&] {
if (depa[ra] > depc[rc]) return false;
int rx = dv, depx = depc[rc]-depa[ra];
rep(i,depx) rx = pac[rx];
mints hx = hc[rx] - hsh[depc[rx]];
// cerr<<rx<<endl;
vm ha(na);
{
auto dfs = [&](auto f, int v) -> mints {
mints x = hx;
for (int u : ga[v]) x *= f(f,u);
x += hsh[depa[v]+depx];
return ha[v] = x;
};
dfs(dfs,ra);
}
// cerr<<hx<<endl;
// cerr<<ha<<endl;
vi used(nc);
vl nchs;
{
vl nhs;
for (int ch : ga[ra]) nhs.pb(ha[ch].get());
for (int ch : gc[rx]) nhs.pb(hc[ch].get());
sort(rng(nhs));
int ni = 0;
for (auto [nh,ch] : chs) {
if (ni < sz(nhs) && nh == nhs[ni]) {
ni++;
used[ch] = 1;
} else {
nchs.eb(nh);
}
}
if (ni != sz(nhs)) return false;
}
// cerr<<nchs<<endl;
int ry = rc, ndep = 0;
{
while (1) {
P mx(-1,-1);
for (int ch : gc[ry]) if (!used[ch]) {
maxs(mx,P(depc[ch],ch));
}
if (mx.fi == -1) break;
ry = mx.se;
ndep++;
}
}
if (depb[rb] > ndep) return false;
int depy = ndep-depb[rb];
rep(i,depy) ry = pac[ry];
mints hy = hc[ry] - hsh[depc[ry]];
// cerr<<ry<<endl;
vm hb(nb);
{
auto dfs = [&](auto f, int v) -> mints {
mints x = hy;
for (int u : gb[v]) x *= f(f,u);
x += hsh[depb[v]+depy];
return hb[v] = x;
};
dfs(dfs,rb);
}
{
vl nhs;
for (int ch : gb[rb]) nhs.pb(hb[ch].get());
for (int ch : gc[ry]) nhs.pb(hc[ch].get());
sort(rng(nhs));
if (nhs != nchs) return false;
}
auto getans = [&](int rt) {
vi ans;
auto dfs = [&](auto f, int v, int pa=0) -> void {
ans.pb(pa);
int k = sz(ans);
for (int u : gc[v]) f(f,u,k);
};
dfs(dfs,rt);
return ans;
};
vi ansx = getans(rx);
vi ansy = getans(ry);
if (ab) swap(ansx,ansy);
printf("%d %d\n",sz(ansx),sz(ansy));
priv(ansx);
priv(ansy);
return true;
}()) return;
swap(na,nb);
swap(ga,gb);
swap(ra,rb);
swap(paa,pab);
swap(depa,depb);
}
puts("Impossible");
}
};
int main() {
// cin.tie(nullptr); ios::sync_with_stdio(false);
int ts = 1;
scanf("%d",&ts);
rep1(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
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: 240ms
memory: 16144kb
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 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: 1ms
memory: 4148kb
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