QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#667976 | #6340. Tourism | L_Hospital_# | 0 | 189ms | 62000kb | C++14 | 3.1kb | 2024-10-23 10:18:36 | 2024-10-23 10:18:43 |
Judging History
answer
#include<bits/stdc++.h>
# define rep(i, j, k) for (int i = j; i <= k; ++i)
using namespace std;
int n, m, qu, c[100005], hd[100005], to[200005], nxt[200005], etimer;
int p[100005], d[100005], sz[100005], son[100005], t1[100005], t2[100005], top[100005], id[100005], timer;
int lg2[100005], minn[20][100005], maxx[20][100005];
int ans[100005];
struct node
{
int pos, num;
bool operator<(const node &x)const{return pos < x.pos;}
};
vector < node > aff[100005];
struct oper
{
int l, r, pos, id, num;
bool operator<(const oper &x)const{return pos < x.pos || pos == x.pos && id < x.id;}
} q[2000005];
node stk[2000005];
int r, nu;
int bit[100005];
void addedge(int u, int v){to[++etimer] = v, nxt[etimer] = hd[u], hd[u] = etimer;}
void dfs_pre(int u, int fa)
{
d[u] = d[p[u] = fa] + 1, sz[u] = 1;
for (int i = hd[u]; i; i = nxt[i]) if (to[i] != fa) {dfs_pre(to[i], u); sz[u] += sz[to[i]]; if (sz[son[u]] < sz[to[i]]) son[u] = to[i];}
}
void dfs(int u)
{
t1[u] = ++timer, id[timer] = u; top[u] = (u == son[p[u]] ? top[p[u]] : u);
if (son[u]) dfs(son[u]);
for (int i = hd[u]; i; i = nxt[i]) if (to[i] != p[u] && to[i] != son[u]) dfs(to[i]);
t2[u] = timer;
}
int lca(int u, int v){while (top[u] != top[v]) if (d[top[u]] < d[top[v]]) v = p[top[v]]; else u = p[top[u]]; return d[u] < d[v] ? u : v;}
void buildst()
{
lg2[0] = -1;
rep(i, 1, n) lg2[i] = lg2[i >> 1] + 1, minn[0][i] = maxx[0][i] = t1[c[i]];
rep(p, 1, 17) rep(i, 1, n - (1 << p) + 1) minn[p][i] = min(minn[p - 1][i], minn[p - 1][i + (1 << (p - 1))]), maxx[p][i] = max(maxx[p - 1][i], maxx[p - 1][i + (1 << (p - 1))]);
}
int la(int l, int r)
{
int lg = lg2[r - l + 1];
return lca(id[min(minn[lg][l], minn[lg][r - (1 << lg) + 1])], id[max(maxx[lg][l], maxx[lg][r - (1 << lg) + 1])]);
}
void deal(int pos, int u)
{
while (u) aff[top[u]].push_back({pos, d[u] - d[top[u]] + 1}), u = p[top[u]];
}
void add(int x, int num){for (; x <= m; x += (x & (-x))) bit[x] += num;}
int query(int x){int ans = 0; for (; x; x &= (x - 1)) ans += bit[x]; return ans;}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m >> qu, nu = qu;
rep(i, 1, n - 1) {int u, v; cin >> u >> v; addedge(u, v), addedge(v, u);}
dfs_pre(1, 0), dfs(1);
rep(i, 1, m) cin >> c[i], deal(i, c[i]);
buildst();
rep(i, 1, qu) cin >> q[i].l >> q[i].r, q[i].pos = q[i].r, q[i].id = i;
rep(i, 1, n) if (!aff[i].empty())
{
sort(aff[i].begin(), aff[i].end());
r = 0;
for (int j = 0; j < aff[i].size(); ++j)
{
q[++nu] = (oper) {stk[r].pos + 1, aff[i][j].pos, aff[i][j].pos, 0, aff[i][j].num};
while (r && stk[r].num < aff[i][j].num) q[++nu] = {stk[r - 1].pos + 1, stk[r].pos, aff[i][j].pos, 0, aff[i][j].num - stk[r].num}, --r;
stk[++r] = aff[i][j];
}
}
sort(q + 1, q + nu + 1);
rep(i, 1, nu) {if (!q[i].id) add(q[i].l, q[i].num), add(q[i].r + 1, -q[i].num); else ans[q[i].id] = query(q[i].l) - d[la(q[i].l, q[i].r)] + 1;}
rep(i, 1, qu) cout << ans[i] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 24160kb
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 99 112 93 110 141 86 24 128 123 70 99 85 96 25 113 86 60 81 49 109 133 66 33 11 43 88 112 62 125 46 132 73 65 93 77 115 85 25 95 129 69 85 123 79 129 125 85 34 64 99 121 63 56 101 108 33 69 129 48 76 136 70 96 22 120 105 118 36 85 126 114 132 25 34 114 140 39 98 66 122 111 3 105 139 73 105 111 91...
result:
wrong answer 2nd numbers differ - expected: '97', found: '99'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #56:
score: 0
Wrong Answer
time: 49ms
memory: 35804kb
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:
55321 55322 55313 55306 55319 53676 55322 55306 55322 55322 55288 55322 55318 55322 55311 55311 55322 55302 55306 55319 55322 55317 55322 55319 55322 55318 55300 55318 55322 55322 55322 55281 55319 55322 55322 55322 55322 55322 55322 55322 55322 55306 55322 55186 55204 55322 55322 55319 55297 55321 ...
result:
wrong answer 1st numbers differ - expected: '55319', found: '55321'
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 18
Accepted
time: 63ms
memory: 39140kb
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: 115ms
memory: 47372kb
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: '293'
Subtask #5:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 189ms
memory: 62000kb
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:
42789 7821 39914 18091 47412 43991 2172 29300 18235 16452 44209 47527 32164 44461 32386 30156 45742 45709 47397 43519 30989 19209 13902 35077 49211 21200 43577 32111 19691 35462 45080 11602 42234 16863 23259 44559 41925 39466 34627 41081 32140 34483 41166 24623 11639 18786 29659 38065 42423 42322 30...
result:
wrong answer 1st numbers differ - expected: '42788', found: '42789'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%