QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267557 | #7869. 建设终末树 | hos_lyric# | 0 | 146ms | 55976kb | C++14 | 11.2kb | 2023-11-27 14:25:45 | 2024-07-04 03:09:29 |
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")
struct Scc {
int n;
vector<int> as, bs;
vector<int> ptr, zu, us;
int l;
vector<int> ids;
int operator[](int u) const { return ids[u]; }
explicit Scc(int n_) : n(n_), as(), bs(), l(-1) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
as.push_back(u);
bs.push_back(v);
}
void dfs0(int u) {
if (!ids[u]) {
ids[u] = -1;
for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs0(zu[i]);
us.push_back(u);
}
}
void dfs1(int u) {
if (!~ids[u]) {
ids[u] = l;
for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs1(zu[i]);
}
}
void run() {
const int m = as.size();
ptr.resize(n + 2);
zu.resize(m);
for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
for (int i = 0; i < m; ++i) ++ptr[as[i] + 2];
for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
for (int i = 0; i < m; ++i) zu[ptr[as[i] + 1]++] = bs[i];
ids.assign(n, 0);
us.clear();
for (int u = 0; u < n; ++u) dfs0(u);
for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
for (int i = 0; i < m; ++i) ++ptr[bs[i] + 2];
for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
for (int i = 0; i < m; ++i) zu[ptr[bs[i] + 1]++] = as[i];
l = 0;
for (int j = n; --j >= 0; ) if (!~ids[us[j]]) { dfs1(us[j]); ++l; }
}
vector<vector<int>> group() const {
assert(~l);
vector<vector<int>> uss(l);
for (int u = 0; u < n; ++u) uss[ids[u]].push_back(u);
return uss;
}
};
struct Hld {
int n, rt;
// needs to be tree
// vertex lists
// modified in build(rt) (parent removed, heavy child first)
vector<vector<int>> graph;
vector<int> sz, par, dep;
int zeit;
vector<int> dis, fin, sid;
// head vertex (minimum depth) in heavy path
vector<int> head;
Hld() : n(0), rt(-1), zeit(0) {}
explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfsSz(int u) {
sz[u] = 1;
for (const int v : graph[u]) {
auto it = std::find(graph[v].begin(), graph[v].end(), u);
if (it != graph[v].end()) graph[v].erase(it);
par[v] = u;
dep[v] = dep[u] + 1;
dfsSz(v);
sz[u] += sz[v];
}
}
void dfsHld(int u) {
dis[u] = zeit++;
const int deg = graph[u].size();
if (deg > 0) {
int vm = graph[u][0];
int jm = 0;
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
if (sz[vm] < sz[v]) {
vm = v;
jm = j;
}
}
swap(graph[u][0], graph[u][jm]);
head[vm] = head[u];
dfsHld(vm);
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
head[v] = v;
dfsHld(v);
}
}
fin[u] = zeit;
}
void build(int rt_) {
assert(0 <= rt_); assert(rt_ < n);
rt = rt_;
sz.assign(n, 0);
par.assign(n, -1);
dep.assign(n, -1);
dep[rt] = 0;
dfsSz(rt);
zeit = 0;
dis.assign(n, -1);
fin.assign(n, -1);
head.assign(n, -1);
head[rt] = rt;
dfsHld(rt);
assert(zeit == n);
sid.assign(n, -1);
for (int u = 0; u < n; ++u) sid[dis[u]] = u;
}
friend ostream &operator<<(ostream &os, const Hld &hld) {
const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
vector<string> ss(2 * maxDep + 1);
int pos = 0, maxPos = 0;
for (int j = 0; j < hld.n; ++j) {
const int u = hld.sid[j];
const int d = hld.dep[u];
if (hld.head[u] == u) {
if (j != 0) {
pos = maxPos + 1;
ss[2 * d - 1].resize(pos, '-');
ss[2 * d - 1] += '+';
}
} else {
ss[2 * d - 1].resize(pos, ' ');
ss[2 * d - 1] += '|';
}
ss[2 * d].resize(pos, ' ');
ss[2 * d] += std::to_string(u);
if (maxPos < static_cast<int>(ss[2 * d].size())) {
maxPos = ss[2 * d].size();
}
}
for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
return os;
}
bool contains(int u, int v) const {
return (dis[u] <= dis[v] && dis[v] < fin[u]);
}
int lca(int u, int v) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
return (dis[u] > dis[v]) ? v : u;
}
int jumpUp(int u, int d) const {
assert(0 <= u); assert(u < n);
assert(d >= 0);
if (dep[u] < d) return -1;
const int tar = dep[u] - d;
for (u = head[u]; ; u = head[par[u]]) {
if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
}
}
int jump(int u, int v, int d) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(d >= 0);
const int l = lca(u, v);
const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
if (d <= du) {
return jumpUp(u, d);
} else if (d <= du + dv) {
return jumpUp(v, du + dv - d);
} else {
return -1;
}
}
// [u, v) or [u, v]
template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
assert(contains(v, u));
for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
if (inclusive) {
f(dis[v], dis[u] + 1);
} else {
if (v != u) f(dis[v] + 1, dis[u] + 1);
}
}
// not path order, include lca(u, v) or not
template <class F> void doPath(int u, int v, bool inclusive, F f) const {
const int l = lca(u, v);
doPathUp(u, l, false, f);
doPathUp(v, l, inclusive, f);
}
// (vs, ps): compressed tree
// vs: DFS order (sorted by dis)
// vs[ps[x]]: the parent of vs[x]
// ids[vs[x]] = x, not set for non-tree vertex
vector<int> ids;
pair<vector<int>, vector<int>> compress(vector<int> us) {
// O(n) first time
ids.resize(n, -1);
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
int usLen = us.size();
assert(usLen >= 1);
for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
usLen = us.size();
for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
vector<int> ps(usLen, -1);
for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
return make_pair(us, ps);
}
};
////////////////////////////////////////////////////////////////////////////////
int N, M, Q;
vector<int> A, B;
vector<vector<int>> C;
vector<vector<int>> V, S;
int main() {
for (; ~scanf("%d%d%d", &N, &M, &Q); ) {
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
C.resize(M);
for (int m = 0; m < M; ++m) {
int len;
scanf("%d", &len);
C[m].resize(len);
for (int &c : C[m]) {
scanf("%d", &c);
--c;
}
}
V.resize(Q);
S.resize(Q);
for (int q = 0; q < Q; ++q) {
int len;
scanf("%d", &len);
V[q].resize(len);
for (int &v : V[q]) {
scanf("%d", &v);
--v;
}
scanf("%d", &len);
S[q].resize(len);
for (int &s : S[q]) {
scanf("%d", &s);
--s;
}
}
// cerr<<"C = "<<C<<endl;
// cerr<<"V = "<<V<<endl;
// cerr<<"S = "<<S<<endl;
Hld hld(N);
for (int i = 0; i < N - 1; ++i) {
hld.ae(A[i], B[i]);
}
hld.build(0);
const auto &par = hld.par;
const auto &sid = hld.sid;
// item m is in subtree(u)
auto tru = [&](int m, int u) -> int { return (m * N + u) << 1; };
auto fal = [&](int m, int u) -> int { return (m * N + u) << 1 | 1; };
Scc scc((M * N) << 1);
// x ==> y
auto add = [&](int x, int y) -> void {
if (x != y) {
scc.ae(x, y);
if ((x ^ 1) != y) {
scc.ae(y ^ 1, x ^ 1);
}
}
};
for (int m = 0; m < M; ++m) {
vector<int> dp(N, 0);
for (const int c : C[m]) {
dp[c] += 1;
}
for (int j = N; --j >= 1; ) {
const int u = sid[j];
dp[par[u]] += dp[u];
}
for (int u = 0; u < N; ++u) {
if (dp[u] == (int)C[m].size()) add(fal(m, u), tru(m, u));
if (dp[u] == 0) add(tru(m, u), fal(m, u));
}
for (int u = 0; u < N; ++u) {
const auto &vs = hld.graph[u];
for (int j0 = 0; j0 < (int)vs.size(); ++j0) for (int j1 = j0 + 1; j1 < (int)vs.size(); ++j1) {
add(tru(m, vs[j0]), fal(m, vs[j1]));
}
}
}
for (int q = 0; q < Q; ++q) {
vector<int> dp(N, 0);
for (const int v : V[q]) {
dp[v] += 1;
}
for (int j = N; --j >= 1; ) {
const int u = sid[j];
dp[par[u]] += dp[u];
}
for (int u = 0; u < N; ++u) {
if (dp[u] == (int)V[q].size()) continue;
if (dp[u] == 0) continue;
// same side when cut (par[u], u)
for (const int m0 : S[q]) for (const int m1 : S[q]) {
add(tru(m0, u), tru(m1, u));
}
}
}
scc.run();
bool ok = true;
for (int x = 0; x < scc.n; x += 2) {
ok = ok && (scc[x] != scc[x ^ 1]);
}
if (ok) {
vector<int> ans(M, -1);
for (int m = 0; m < M; ++m) {
for (int j = N; --j >= 0; ) {
const int u = sid[j];
if (scc[fal(m, u)] < scc[tru(m, u)]) {
ans[m] = u;
break;
}
}
}
for (int m = 0; m < M; ++m) {
if (m) printf(" ");
printf("%d", ans[m] + 1);
}
puts("");
} else {
puts("-1");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
1999 1998 27199 1368 233 233 617 233 388 233 1127 1905 233 907 233 233 40 233 1325 233 1940 1739 233 501 233 233 33 735 233 233 283 233 1427 1992 233 233 632 233 685 1188 233 648 233 233 344 233 1321 986 233 848 233 770 233 256 233 164 233 936 233 1206 233 53 233 1054 233 1430 233 1714 233 86 233 11...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 15
Accepted
time: 0ms
memory: 3808kb
input:
10 10 8 4 2 2 9 6 9 8 7 4 10 7 2 5 2 2 1 5 3 3 10 7 2 2 10 2 2 4 10 2 10 4 2 8 2 2 4 10 1 8 2 2 10 1 1 1 10 2 10 9 3 10 3 4 2 7 1 3 10 6 3 2 4 8 2 3 2 4 2 9 4 6 2 5 7 2 3 9 2 2 1 4 10 6 8 5 4 10 6 1 2 2 1 4 2 7 5 2 5 3 2 8 3
output:
10 10 10 10 8 10 8 10 1 10
result:
ok Accepted.
Test #9:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
10 10 9 9 10 3 5 2 3 9 2 2 6 1 3 8 5 1 7 6 4 1 7 1 8 2 10 2 4 8 5 1 2 2 10 9 2 2 7 1 8 4 1 8 5 2 2 10 6 4 9 2 4 3 2 3 10 2 5 3 2 8 3 2 8 5 2 5 3 2 6 5 2 5 9 2 9 3 2 9 8 2 1 8 3 7 1 6 2 2 8 2 10 2 3 8 1 4 2 9 5 3 1 6 8 3 9 4 3 2 1 7
output:
7 8 10 8 10 3 8 3 10 4
result:
ok Accepted.
Test #10:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
10 10 8 7 1 3 2 6 1 2 1 3 5 10 8 4 7 9 2 6 10 1 9 2 3 5 2 10 8 3 9 1 5 1 9 2 1 8 1 10 4 2 7 9 3 3 9 3 6 3 1 9 3 3 3 1 2 3 8 2 9 2 1 9 2 8 9 2 4 2 3 2 8 9 3 4 9 6 3 7 3 6 2 7 10 2 5 8 2 5 9 2 1 5 3 9 7 1 2 9 4 3 8 3 7 3 7 6 3
output:
9 5 10 5 9 10 10 3 3 3
result:
ok Accepted.
Test #11:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
10 10 6 8 1 3 10 6 1 9 2 8 5 3 7 9 7 6 4 6 3 2 1 6 3 6 10 3 1 8 4 10 1 4 3 3 3 1 6 3 1 4 10 2 9 2 2 9 2 3 6 1 4 2 7 10 3 3 2 9 3 3 4 6 5 4 8 10 5 9 5 5 6 4 9 1 2 5 9 4 2 6 5 10 3 7 3 8 3 1 9 2 3 2 8 9 2 10 2 4 10 5 3 2 3 6 2 10
output:
-1
result:
ok Accepted.
Test #12:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
10 10 9 1 7 7 5 7 8 3 7 7 10 4 7 7 9 6 7 2 7 3 6 3 9 3 8 2 4 6 2 7 5 3 6 8 3 4 5 10 4 6 4 10 9 7 5 10 4 6 9 8 1 6 8 9 4 10 5 2 3 4 5 1 7 7 8 5 1 10 9 6 2 8 7 2 3 7 2 6 2 2 3 6 3 3 9 2 2 10 1 2 8 1 2 8 5 2 9 5 2 7 3 2 5 3 3 2 10 8 2 5 8 2 1 3 2 8 4 3 4 5 6 2 9 2 2 10 9 3 3 8 9
output:
7 2 7 7 7 7 2 7 7 7
result:
ok Accepted.
Test #13:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
10 10 6 4 9 8 4 4 7 3 4 5 4 2 4 4 6 1 4 10 4 9 8 1 6 4 9 10 5 3 2 5 4 2 10 7 3 2 4 6 2 6 4 8 2 6 10 5 3 9 1 8 8 7 9 10 6 5 3 2 1 8 7 8 10 5 2 1 9 3 8 5 10 7 6 2 9 8 3 9 10 5 7 1 8 9 3 2 6 6 3 2 6 10 5 7 3 5 2 4 2 10 4 4 10 6 8 2 3 10 5 2 4 3 1 8 5 2 6 9 3 7 4 10 6 8 9 7 3 6 1 4 3 8 7 2 3 5 10 2 2 5 ...
output:
2 4 4 4 4 4 4 4 4 4
result:
ok Accepted.
Test #14:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
10 10 7 10 6 10 4 2 10 8 10 10 1 5 10 3 10 7 10 9 10 5 8 1 3 5 6 10 2 10 8 5 7 9 3 6 4 1 7 4 8 6 10 3 5 9 2 1 10 7 7 6 10 8 4 1 9 1 5 9 9 4 6 10 1 7 2 3 5 10 6 4 3 9 1 5 8 7 2 10 2 8 2 8 6 1 3 5 7 4 8 9 3 8 5 4 3 10 5 4 2 10 4 3 4 2 10 3 6 7 1 3 4 10 5 2 6 3 2 7 2 4 8 7 6 4 3 8 3 9 4 10 8 4 5 3 10 2...
output:
10 10 10 10 10 5 10 10 10 10
result:
ok Accepted.
Test #15:
score: -15
Wrong Answer
time: 0ms
memory: 3784kb
input:
10 10 9 8 7 5 3 1 8 7 6 10 4 3 6 1 2 5 9 9 4 5 7 6 9 1 10 3 10 5 9 2 9 6 2 3 4 5 10 6 5 4 3 3 9 3 8 4 3 8 2 10 3 8 4 2 5 3 9 10 8 2 1 5 2 5 7 2 7 4 2 10 7 2 7 9 2 6 5 2 8 1 2 8 1 2 3 5 2 3 10 4 5 8 3 7 3 2 4 5 2 7 5 3 5 1 2 2 1 6 2 2 10 2 8 4 2 2 8 2 7 1
output:
10 10 9 9 9 9 9 9 2 5
result:
wrong answer restrict 2 is not satisfied.
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 146ms
memory: 55976kb
input:
500 498 5000 60 409 462 125 461 410 42 178 133 372 137 265 358 27 450 294 45 454 76 405 132 118 333 331 365 230 114 218 112 377 49 429 60 299 488 95 85 362 89 33 426 308 427 198 468 481 289 363 195 430 61 21 162 55 12 487 395 85 79 475 391 215 244 351 331 43 452 186 247 271 224 390 206 347 447 165 9...
output:
266 198 83 93 384 464 123 482 363 84 257 205 482 37 466 48 259 402 253 1 236 499 419 409 471 321 7 242 443 394 317 492 495 442 482 364 292 133 494 275 231 135 183 278 261 452 211 482 296 301 482 253 4 78 1 279 441 188 288 132 42 266 441 261 1 213 424 432 492 140 207 337 301 330 279 253 342 92 402 30...
result:
wrong answer restrict 36 is not satisfied.
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%