QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#634209 | #9459. Tree Equation | ucup-team087# | AC ✓ | 221ms | 22044kb | C++14 | 9.8kb | 2024-10-12 16:53:05 | 2024-10-12 16:53:09 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
// 2^61 - 1 = 2'305'843'009'213'693'951
struct ModLong61 {
static constexpr unsigned long long M = (1ULL << 61) - 1;
unsigned long long x;
constexpr ModLong61() : x(0ULL) {}
constexpr ModLong61(unsigned x_) : x(x_) {}
constexpr ModLong61(unsigned long long x_) : x(x_ % M) {}
constexpr ModLong61(int x_) : x((x_ < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
constexpr ModLong61(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModLong61 &operator+=(const ModLong61 &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModLong61 &operator-=(const ModLong61 &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModLong61 &operator*=(const ModLong61 &a) {
const unsigned __int128 y = static_cast<unsigned __int128>(x) * a.x;
x = (y >> 61) + (y & M);
x = (x >= M) ? (x - M) : x;
return *this;
}
ModLong61 &operator/=(const ModLong61 &a) { return (*this *= a.inv()); }
ModLong61 pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModLong61 a = *this, b = 1ULL; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModLong61 inv() const {
unsigned long long a = M, b = x; long long y = 0, z = 1;
for (; b; ) { const unsigned long long q = a / b; const unsigned long long c = a - q * b; a = b; b = c; const long long w = y - static_cast<long long>(q) * z; y = z; z = w; }
assert(a == 1ULL); return ModLong61(y);
}
ModLong61 operator+() const { return *this; }
ModLong61 operator-() const { ModLong61 a; a.x = x ? (M - x) : 0ULL; return a; }
ModLong61 operator+(const ModLong61 &a) const { return (ModLong61(*this) += a); }
ModLong61 operator-(const ModLong61 &a) const { return (ModLong61(*this) -= a); }
ModLong61 operator*(const ModLong61 &a) const { return (ModLong61(*this) *= a); }
ModLong61 operator/(const ModLong61 &a) const { return (ModLong61(*this) /= a); }
template <class T> friend ModLong61 operator+(T a, const ModLong61 &b) { return (ModLong61(a) += b); }
template <class T> friend ModLong61 operator-(T a, const ModLong61 &b) { return (ModLong61(a) -= b); }
template <class T> friend ModLong61 operator*(T a, const ModLong61 &b) { return (ModLong61(a) *= b); }
template <class T> friend ModLong61 operator/(T a, const ModLong61 &b) { return (ModLong61(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModLong61 &a) const { return (x == a.x); }
bool operator!=(const ModLong61 &a) const { return (x != a.x); }
bool operator<(const ModLong61 &a) const { return (x < a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModLong61 &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
////////////////////////////////////////////////////////////////////////////////
using Mint = ModLong61;
vector<Mint> R;
struct Tree {
int n;
vector<int> par;
vector<vector<int>> graph;
vector<int> sz;
vector<Mint> fs;
int vm;
void build() {
graph.assign(n, {});
for (int u = 1; u < n; ++u) graph[par[u]].push_back(u);
sz.assign(n, 1);
fs.assign(n, 1);
for (int u = n; --u >= 0; ) {
for (const int v : graph[u]) {
sz[u] += sz[v];
fs[u] *= fs[v];
}
fs[u] += R[sz[u]];
}
vm = -1;
for (const int v : graph[0]) if (!~vm || sz[vm] < sz[v]) vm = v;
// cerr<<"vm = "<<vm<<", sz[vm] = "<<sz[vm]<<endl;
}
vector<int> oks;
vector<Mint> gs, zs;
void compute(int nz) {
oks.assign(n, 0);
gs.assign(n, 1);
zs.assign(n, 1);
for (int u = n; --u >= 0; ) if (sz[u] >= nz) {
if ([&]() -> bool {
for (const int v : graph[u]) if (sz[v] < nz) zs[u] *= fs[v];
zs[u] += R[nz];
int sum = nz;
for (const int v : graph[u]) if (sz[v] >= nz) {
if (!oks[v]) return false;
if (zs[u] != zs[v]) return false;
sum += sz[v];
gs[u] *= gs[v];
}
if (sz[u] != sum) return false;
assert(sum % nz == 0);
gs[u] += R[sum / nz];
return true;
}()) {
oks[u] = 1;
}
}
// cerr<<"[compute] "<<nz<<endl;
// cerr<<" oks = "<<oks<<endl;
// cerr<<" gs = "<<gs<<endl;
// cerr<<" zs = "<<zs<<endl;
}
void dfs(int u, vector<int> &us) {
us.push_back(u);
for (const int v : graph[u]) dfs(v, us);
}
vector<int> recover(int u) {
vector<int> us;
dfs(u, us);
sort(us.begin(), us.end());
const int usLen = us.size();
vector<int> ps(usLen, -1);
for (int j = 1; j < usLen; ++j) {
ps[j] = lower_bound(us.begin(), us.end(), par[us[j]]) - us.begin();
}
return ps;
}
} T[3];
vector<int> ans[2];
bool solve(int ha) {
const int hb = ha ^ 1;
// cerr<<COLOR("33")<<"[solve] "<<ha<<" "<<hb<<COLOR()<<endl;
Tree &A = T[ha];
Tree &B = T[hb];
Tree &C = T[2];
if (C.sz[C.vm] % A.sz[A.vm] != 0) return false;
const int NX = C.sz[C.vm] / A.sz[A.vm];
C.compute(NX);
if (!C.oks[C.vm]) return false;
const Mint X = C.zs[C.vm];
int ux = -1;
for (int u = 0; u < C.n; ++u) if (C.fs[u] == X) { ux = u; break; }
assert(~ux);
// cerr<<"NX = "<<NX<<", ux = "<<ux<<endl;
vector<int> used(C.n, 0);
vector<Mint> tar;
vector<pair<Mint, int>> cs;
auto cut = [&]() -> bool {
sort(tar.begin(), tar.end());
sort(cs.begin(), cs.end());
// cerr<<"[cut] "<<tar<<" "<<cs<<endl;
const int tarLen = tar.size();
const int csLen = cs.size();
int i = 0;
for (int j = 0; j < csLen; ++j) {
if (i < tarLen && tar[i] == cs[j].first) {
used[cs[j].second] = 1;
++i;
}
}
return (i == tarLen);
};
tar.clear();
cs.clear();
for (const int v : A.graph[0]) tar.push_back(A.fs[v]);
for (const int v : C.graph[0]) if (!used[v] && C.oks[v] && C.zs[v] == X) cs.emplace_back(C.gs[v], v);
if (!cut()) return false;
tar.clear();
cs.clear();
for (const int v : C.graph[ux]) tar.push_back(C.fs[v]);
for (const int v : C.graph[0]) if (!used[v]) cs.emplace_back(C.fs[v], v);
if (!cut()) return false;
// cerr<<"used = "<<used<<endl;
int vmy = -1;
for (const int v : C.graph[0]) if (!used[v]) if (!~vmy || C.sz[vmy] < C.sz[v]) vmy = v;
if (!~vmy) return false;
const int NY = C.sz[vmy] / B.sz[B.vm];
C.compute(NY);
if (!C.oks[vmy]) return false;
const Mint Y = C.zs[vmy];
int uy = -1;
for (int u = 0; u < C.n; ++u) if (C.fs[u] == Y) { uy = u; break; }
assert(~uy);
tar.clear();
cs.clear();
for (const int v : B.graph[0]) tar.push_back(B.fs[v]);
for (const int v : C.graph[0]) if (!used[v] && C.oks[v] && C.zs[v] == Y) cs.emplace_back(C.gs[v], v);
if (!cut()) return false;
tar.clear();
cs.clear();
for (const int v : C.graph[uy]) tar.push_back(C.fs[v]);
for (const int v : C.graph[0]) if (!used[v]) cs.emplace_back(C.fs[v], v);
if (!cut()) return false;
for (const int v : C.graph[0]) if (!used[v]) return false;
ans[ha] = T[2].recover(ux);
ans[hb] = T[2].recover(uy);
return true;
}
int main() {
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
for (int h = 0; h < 3; ++h) {
scanf("%d", &T[h].n);
T[h].par.assign(T[h].n, -1);
}
for (int h = 0; h < 3; ++h) {
for (int u = 0; u < T[h].n; ++u) {
scanf("%d", &T[h].par[u]);
--T[h].par[u];
}
}
R.resize(T[2].n + 1);
for (int s = 0; s <= T[2].n; ++s) R[s] = (unsigned long long)rng();
for (int h = 0; h < 3; ++h) T[h].build();
for (int h = 0; h < 2; ++h) ans[h].clear();
bool res = false;
for (int h = 0; h < 2; ++h) {
res = solve(h);
if (res) break;
}
if (res) {
printf("%d %d\n", (int)ans[0].size(), (int)ans[1].size());
for (int h = 0; h < 2; ++h) {
for (int u = 0; u < (int)ans[h].size(); ++u) {
if (u) printf(" ");
printf("%d", ans[h][u] + 1);
}
puts("");
}
} else {
puts("Impossible");
/*
cerr<<"FAIL"<<endl;
cerr<<T[0].n<<" "<<T[1].n<<" "<<T[2].n<<endl;
for(int h=0;h<3;++h){for(int u=0;u<T[h].n;++u)cerr<<T[h].par[u]+1<<" ";cerr<<endl;}
assert(false);
*/
}
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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: 221ms
memory: 22044kb
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: 3820kb
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