QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#879524 | #6340. Tourism | woohyun_jng | 0 | 665ms | 25488kb | C++23 | 3.2kb | 2025-02-02 05:17:34 | 2025-02-02 05:17:36 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define MAX 200000
using namespace std;
typedef array<int, 2> pr;
typedef array<int, 3> tp;
vector<pr> queries[MAX];
vector<int> adj[MAX];
set<tp> st;
int N, C[MAX], ans[MAX], in[MAX], top[MAX], parent[MAX], depth[MAX], sz[MAX], tree[MAX * 4], cnt = 0;
void dfs(int node, int par) {
depth[node] = depth[par] + 1, parent[node] = par, sz[node] = 1;
for (int &i : adj[node]) {
if (i == par)
continue;
dfs(i, node), sz[node] += sz[i];
if (adj[node][0] == par || sz[adj[node][0]] < sz[i])
swap(adj[node][0], i);
}
}
void hld(int node, int par) {
in[node] = ++cnt;
for (int i : adj[node]) {
if (i == par)
continue;
top[i] = i == adj[node][0] ? top[node] : i;
hld(i, node);
}
}
int query(int n, int s, int e, int l, int r) {
if (r < s || e < l)
return 0;
else if (l <= s && e <= r)
return tree[n];
else {
int m = s + e >> 1;
return query(n << 1, s, m, l, r) + query(n << 1 | 1, m + 1, e, l, r);
}
}
void update(int n, int s, int e, int x, int v) {
if (x < s || e < x)
return;
else if (s == e)
tree[n] += v;
else {
int m = s + e >> 1;
update(n << 1, s, m, x, v), update(n << 1 | 1, m + 1, e, x, v);
tree[n] = tree[n << 1] + tree[n << 1 | 1];
}
}
void upd(int s, int e, int v) {
set<tp>::iterator iter;
tp K;
iter = prev(st.lower_bound({s, N + 1, 0})), K = *iter;
while (K[1] <= e) {
st.erase(iter), update(1, 1, N, K[2], -(K[1] - K[0] + 1));
if (K[0] < s)
st.insert({K[0], s - 1, K[2]}), update(1, 1, N, K[2], s - K[0]);
iter = st.lower_bound({s, 0, 0}), K = iter == st.end() ? (tp){0, N + 1, 0} : *iter;
}
if (iter != st.end() && K[0] <= e) {
st.erase(iter), update(1, 1, N, K[2], -(K[1] - K[0] + 1));
if (K[0] < s)
st.insert({K[0], s - 1, K[2]}), update(1, 1, N, K[2], s - K[0]);
st.insert({e + 1, K[1], K[2]}), update(1, 1, N, K[2], K[1] - e);
}
st.insert({s, e, v}), update(1, 1, N, v, e - s + 1);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int M, Q, X, Y;
cin >> N >> M >> Q;
for (int i = 1; i < N; i++) {
cin >> X >> Y;
adj[X].push_back(Y), adj[Y].push_back(X);
}
dfs(1, 0), top[1] = 1, hld(1, 0);
st.insert({1, N, 1}), update(1, 1, N, 1, N);
for (int i = 1; i <= M; i++)
cin >> C[i];
for (int i = 1; i <= Q; i++) {
cin >> X >> Y;
queries[Y].push_back({i, X});
}
for (int i = 2; i <= M; i++) {
X = C[i - 1], Y = C[i];
while (top[X] ^ top[Y]) {
if (depth[top[X]] < depth[top[Y]])
swap(X, Y);
upd(in[top[X]], in[X], i), X = parent[top[X]];
}
if (depth[X] > depth[Y])
swap(X, Y);
upd(in[X], in[Y], i);
for (pr j : queries[i])
ans[j[0]] = query(1, 1, N, j[1] + 1, i);
}
for (int i = 1; i <= Q; i++)
cout << max(1ll, ans[i]) << '\n';
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 14088kb
input:
166 249 224 158 52 52 82 158 36 117 158 119 117 5 82 158 18 22 36 82 143 105 36 22 152 36 92 117 2 123 158 5 134 119 89 31 119 92 48 105 149 149 17 108 31 134 50 3 52 63 158 3 51 42 22 17 10 103 158 50 122 92 85 50 78 117 159 36 20 143 115 158 83 20 4 142 22 23 3 96 10 19 134 8 10 151 92 65 108 89 5...
output:
67 12 74 93 110 43 1 24 82 55 70 25 79 96 25 113 86 60 1 49 34 33 66 33 1 1 43 91 40 28 46 58 73 1 93 1 70 85 25 95 75 69 85 72 33 82 48 32 34 1 99 121 63 56 74 36 1 69 47 48 31 50 1 30 22 120 105 28 36 3 83 63 65 1 34 32 43 1 98 6 122 57 1 105 45 73 105 53 29 95 28 28 52 39 65 91 4 108 23 1 36 53 8...
result:
wrong answer 2nd numbers differ - expected: '97', found: '12'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #56:
score: 0
Wrong Answer
time: 81ms
memory: 25488kb
input:
55321 88650 75523 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
1 1 55313 55306 55319 53676 1 1 1 1 1 1 55318 1 55311 55311 1 1 1 55319 1 55317 1 55319 1 55318 1 55318 1 1 2 1 55319 1 1 1 1 1 1 1 1 1 1 55186 55204 1 2 55319 55297 1 1 55318 55319 1 55319 1 1 1 1 55319 55318 1 55293 28 1 28 1 55317 1 1 1 1 1 55307 1 1 1 55316 55301 1 55311 55317 55143 1 1 1 55319 ...
result:
wrong answer 1st numbers differ - expected: '55319', found: '1'
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 18
Accepted
time: 282ms
memory: 21588kb
input:
54738 54525 1797 45211 4527 4527 43609 4527 19876 16325 43609 32183 4527 16325 32579 43609 25554 32183 38972 45211 53953 16325 19810 10881 19810 45211 12698 27967 19810 25554 46338 51894 45211 25388 16325 512 25554 43609 7820 10206 512 30021 32183 48647 43609 46338 44138 16766 7820 10023 53953 19810...
output:
276 238 198 214 294 240 233 266 184 241 207 241 256 225 215 222 190 269 221 242 287 225 215 252 273 203 281 186 259 195 152 183 206 241 218 205 241 233 194 239 258 244 267 339 224 205 242 202 260 275 173 243 178 228 251 242 239 231 203 249 277 215 202 169 243 258 208 306 232 231 211 224 249 256 203 ...
result:
ok 1797 numbers
Test #70:
score: 0
Wrong Answer
time: 410ms
memory: 23412kb
input:
59284 89368 1930 4029 716 1741 4029 14542 4029 48937 4029 716 24494 29506 1741 4029 3097 2898 716 3097 8627 2898 46025 29506 15319 716 12015 1741 5566 8627 58178 2898 14837 7742 1741 21507 24494 20151 24494 48937 9926 55162 7742 32033 14837 2898 27435 12292 8627 24972 58178 55074 48937 45787 21507 1...
output:
369 311 313 353 339 335 284 364 434 382 298 243 268 306 282 383 400 371 343 357 399 329 285 264 350 350 372 391 378 398 281 257 419 308 307 462 379 357 327 356 323 427 360 368 312 394 268 310 310 324 275 312 279 347 298 281 314 291 447 257 320 269 343 311 397 279 332 319 238 268 369 334 301 321 390 ...
result:
wrong answer 1276th numbers differ - expected: '289', found: '59'
Subtask #5:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 665ms
memory: 25452kb
input:
55965 89652 95687 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...
output:
26865 1 39914 17122 9941 18973 1 29300 18235 1 7705 14588 18168 10437 9845 1360 16279 8161 21883 12817 30989 3100 13902 35077 12908 21200 43577 1 1 4016 9221 1 6526 1 23259 6647 36075 10314 5128 41081 15838 1197 41166 24623 1 18786 29659 8809 42423 26355 30971 28924 1 24798 616 10947 38023 25288 339...
result:
wrong answer 1st numbers differ - expected: '42788', found: '26865'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%