QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201030 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | hos_lyric# | 0 | 465ms | 4804kb | C++14 | 12.2kb | 2023-10-05 07:15:36 | 2024-07-04 02:16:05 |
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 <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 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;
vector<int> A, B;
int Q;
vector<int> X, Y, D;
vector<vector<int>> graph;
Hld hld;
namespace brute {
vector<int> run() {
cerr<<"[brute::run]"<<endl;
vector<int> ans(Q, 0);
for (int q = 0; q < Q; ++q) {
const int x = X[q], y = Y[q];
const int l = hld.lca(x, y);
queue<int> que;
vector<int> dist(N, -1);
auto reach = [&](int v, int c) -> void {
if (!~dist[v]) {
dist[v] = c;
que.push(v);
}
};
for (int u = x; u != l; u = hld.par[u]) reach(u, 0);
for (int u = y; u != l; u = hld.par[u]) reach(u, 0);
reach(l, 0);
for (; !que.empty(); ) {
const int u = que.front();
que.pop();
for (const int v : graph[u]) reach(v, dist[u] + 1);
}
for (int u = 0; u < N; ++u) if (dist[u] <= D[q]) {
++ans[q];
}
}
return ans;
}
} // brute
namespace sub3 {
vector<vector<pair<int, pair<int, int>>>> ess;
vector<int> ans;
vector<int> sz, del;
void dfsSz(int u, int p) {
sz[u] = 1;
for (const int v : graph[u]) if (p != v) {
dfsSz(v, u);
sz[u] += sz[v];
}
}
string dfsString(int u, int p) {
ostringstream oss;
oss << "[" << u;
for (const int v : graph[u]) if (!del[v] && p != v) {
oss << " " << dfsString(v, u);
}
oss << "]";
return oss.str();
}
/// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vector<int> par, dep;
vector<vector<int>> uss, fss;
void dfs(int j, int u, int p, int d) {
par[u] = p;
dep[u] = d;
uss[j].push_back(u);
if ((int)fss[j].size() < d + 1) fss[j].resize(d + 1, 0);
++fss[j][d];
for (const int v : graph[u]) if (!del[v] && p != v) {
dfs(j, v, u, d + 1);
}
}
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void solveSubtree(int depth, int r) {
#ifdef LOCAL
cerr << string(2 * depth, ' ') << "solveSubtree " << dfsString(r, -1) << endl;
#endif
vector<int> vs;
for (const int v : graph[r]) if (!del[v]) {
vs.push_back(v);
}
const int len = vs.size();
/// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
sort(vs.begin(), vs.end());
uss.assign(len, {});
fss.assign(len + 1, vector<int>(2, 0));
for (int j = 0; j < len; ++j) {
dfs(j, vs[j], r, 1);
}
int mx = 2;
for (int j = 0; j < len; ++j) {
chmax(mx, (int)fss[j].size());
}
fss[len].assign(mx, 0);
par[r] = -1;
dep[r] = 0;
++fss[len][0];
for (int j = 0; j < len; ++j) {
for (int d = 0; d < (int)fss[j].size(); ++d) {
fss[len][d] += fss[j][d];
}
}
for (int j = 0; j <= len; ++j) {
for (int d = 1; d < (int)fss[j].size(); ++d) {
fss[j][d] += fss[j][d - 1];
}
}
// cerr<<string(2*depth,' ')<<"uss = "<<uss<<", fss = "<<fss<<endl;
auto get = [&](int j, int d) -> int {
return fss[j][min(d, (int)fss[j].size() - 1)];
};
for (const auto &e : ess[r]) {
const int q = e.first;
ans[q] += get(len, D[q]);
for (const int v : {e.second.first, e.second.second}) {
const int j = lower_bound(vs.begin(), vs.end(), v) - vs.begin();
if (j < len && vs[j] == v) {
ans[q] -= get(j, D[q]);
}
}
}
for (int j = 0; j < len; ++j) {
for (const int u : uss[j]) {
for (const auto &e : ess[u]) {
const int q = e.first;
if (par[u] != e.second.first && par[u] != e.second.second && dep[u] <= D[q]) {
ans[q] += get(len, D[q] - dep[u]);
ans[q] -= get(j, D[q] - dep[u]);
}
}
}
}
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
void solveRec(int depth, int u) {
for (; ; ) {
int vm = -1;
for (const int v : graph[u]) if (!del[v]) {
if (!~vm || sz[vm] < sz[v]) {
vm = v;
}
}
if (!~vm || 2 * sz[vm] <= sz[u]) {
solveSubtree(depth, u);
del[u] = 1;
for (const int v : graph[u]) if (!del[v]) {
solveRec(depth + 1, v);
}
break;
} else {
sz[u] -= sz[vm];
sz[vm] += sz[u];
u = vm;
}
}
}
void centroidDecomp() {
sz.assign(N, 0);
dfsSz(0, -1);
del.assign(N, 0);
par.resize(N);
dep.resize(N);
solveRec(0, 0);
}
vector<int> run() {
cerr<<"[sub3::run]"<<endl;
ess.assign(N, {});
for (int q = 0; q < Q; ++q) {
const int x = X[q], y = Y[q];
const int l = hld.lca(x, y);
vector<int> us, vs;
for (int u = x; u != l; u = hld.par[u]) us.push_back(u);
us.push_back(l);
for (int u = y; u != l; u = hld.par[u]) vs.push_back(u);
reverse(vs.begin(), vs.end());
us.insert(us.end(), vs.begin(), vs.end());
const int usLen = us.size();
// cerr<<us<<endl;
for (int j = 0; j < usLen; ++j) {
const int uL = (j - 1 >= 0) ? us[j - 1] : -1;
const int u = us[j];
const int uR = (j + 1 < usLen) ? us[j + 1] : -1;
ess[u].emplace_back(q, make_pair(uL, uR));
}
}
ans.assign(Q, 0);
centroidDecomp();
return ans;
}
} // sub3
int main() {
for (; ~scanf("%d", &N); ) {
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];
}
scanf("%d", &Q);
X.resize(Q);
Y.resize(Q);
D.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%d%d%d", &X[q], &Y[q], &D[q]);
--X[q];
--Y[q];
}
graph.assign(N, {});
hld = Hld(N);
for (int i = 0; i < N - 1; ++i) {
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
hld.ae(A[i], B[i]);
}
hld.build(0);
vector<int> ans;
if (N <= 5000 && Q <= 5000) {
ans = brute::run();
} else {
ans = sub3::run();
}
for (int q = 0; q < Q; ++q) {
printf("%d\n", ans[q]);
}
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 427ms
memory: 4716kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 4974 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 49...
result:
ok 4966 numbers
Test #2:
score: 0
Accepted
time: 215ms
memory: 4544kb
input:
4914 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 ...
output:
3378 4914 231 4914 4914 3378 22 4914 4914 2559 4914 75 219 1407 1138 863 24 3890 4914 4914 399 399 13 139 77 4914 4095 3071 4914 23 151 110 1407 43 54 4914 4914 1919 2559 77 735 3071 24 133 479 4914 33 831 4 4914 4914 79 4914 199 3890 3071 73 567 15 75 21 126 4914 4914 203 4914 75 127 62 41 4914 409...
result:
ok 4975 numbers
Test #3:
score: -7
Wrong Answer
time: 465ms
memory: 4804kb
input:
4921 1151 2767 2767 322 322 4451 4451 4867 4867 1265 1265 3197 3197 3890 3890 1052 1052 1407 1407 1578 1578 566 566 2965 2965 260 260 4908 4908 308 308 553 553 2845 2845 4249 4249 1284 1284 73 73 1088 1088 277 277 1878 1878 4128 4128 3609 3609 2126 2126 149 149 3467 3467 1653 1653 4913 4913 3604 360...
output:
result:
wrong output format Output file not found: ""
Subtask #2:
score: 0
Judgement Failed
Test #9:
score: 0
Judgement Failed
input:
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Judgement Failed
Test #25:
score: 0
Judgement Failed
input:
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%