QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#306559 | #5249. Bandits | LaStataleBlue | WA | 606ms | 53756kb | C++17 | 4.9kb | 2024-01-16 21:39:24 | 2024-01-16 21:39:25 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
constexpr int MAXN = 1e5 + 5;
constexpr ll MAXR = 1e9 + 5;
vector<pii> g[MAXN];
namespace lca
{
int timer = 0, tin[MAXN], tout[MAXN];
ll dist[MAXN];
constexpr int LOGMAXN = 18;
int up[MAXN][LOGMAXN];
void dfs(int n, int p)
{
tin[n] = timer++;
up[n][0] = p;
for (int i = 1; i < LOGMAXN; i++)
up[n][i] = up[up[n][i - 1]][i - 1];
for (const auto &[a, w] : g[n])
if (a != p)
{
dist[a] = dist[n] + w;
dfs(a, n);
}
tout[n] = timer++;
}
void init()
{
dist[1] = 0;
dfs(1, 1);
}
bool is_ancestor(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
if (is_ancestor(u, v))
return u;
if (is_ancestor(v, u))
return v;
for (int i = LOGMAXN - 1; i >= 0; i--)
if (!is_ancestor(up[u][i], v))
u = up[u][i];
return up[u][0];
}
ll getdist(int u, int v)
{
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
} // namespace lca
namespace centroid
{
int treesize[MAXN];
bool used[MAXN];
int up[MAXN];
short depth[MAXN];
void dfs(int n, int p)
{
treesize[n] = 1;
for (const auto &[a, _] : g[n])
if (a != p && !used[a])
{
dfs(a, n);
treesize[n] += treesize[a];
}
}
int centroid(int n, int p, int sz)
{
for (const auto &[a, _] : g[n])
if (a != p && !used[a] && treesize[a] > sz / 2)
return centroid(a, n, sz);
return n;
}
void decomposition(int n, int p, int dep)
{
dfs(n, n);
int c = centroid(n, n, treesize[n]);
up[c] = p;
used[c] = true;
depth[c] = dep;
for (const auto &[a, _] : g[c])
if (!used[a])
decomposition(a, c, dep + 1);
}
void init()
{
decomposition(1, -1, 0);
}
} // namespace centroid
struct FenwickTree
{
vector<int> tree;
void init(int n)
{
tree.assign(n + 1, 0);
}
void update(int p, int a)
{
p++;
while (p < tree.size())
{
tree[p] += a;
p += p & (-p);
}
}
int query(int p)
{
int s = 0;
p++;
while (p > 0)
{
s += tree[p];
p -= p & (-p);
}
return s;
}
};
#define allvec(v) v.data(), v.data() + v.size()
struct QueryStuff
{
vector<int> rs[MAXN];
FenwickTree ft[MAXN];
void addquery(int cn, int radius)
{
rs[cn].push_back(radius);
}
void init(int N)
{
for (int i = 1; i <= N; i++)
if (rs[i].size() != 0)
{
vector<int> &r = rs[i];
sort(allvec(r));
int nsz = unique(allvec(r)) - r.data();
r.resize(nsz);
ft[i].init(nsz);
}
}
void update(int cn, int radius)
{
if (rs[cn].size() == 0)
return;
int l = 0, r = rs[cn].size();
while (l + 1 != r)
{
int m = (l + r) / 2;
if (rs[cn][m] <= radius)
l = m;
else
r = m;
}
ft[cn].update(l, 1);
}
int query(int cn, int minrad)
{
if (rs[cn].size() == 0)
return 0;
const auto getlt = [this, cn](int val) -> int
{
if (rs[cn][0] >= val)
return 0;
int l = 0, r = rs[cn].size();
while (l + 1 != r)
{
int m = (l + r) / 2;
if (rs[cn][m] < val)
l = m;
else
r = m;
}
return ft[cn].query(l);
};
return getlt(MAXR) - getlt(minrad);
}
};
QueryStuff qs, qb;
int main()
{
int N;
scanf("%d", &N);
vector<pii> edges(N);
for (int i = 0, u, v, w; i < N - 1; i++)
{
scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
edges[i] = {u, v};
}
lca::init();
centroid::init();
int Q;
scanf("%d", &Q);
vector<pii> queries(Q);
for (int i = 0; i < Q; i++)
{
char t[2];
int a, b = -1;
scanf("%s %d", t, &a);
if (t[0] == '+')
scanf("%d", &b);
queries[i] = {a, b};
if (t[0] == '+')
{
int prev;
const int start = a;
for (int cn = start; cn != -1; cn = centroid::up[cn])
{
const ll radius = b - lca::getdist(start, cn);
if (radius > 0)
{
qs.addquery(cn, radius);
if (cn != start)
qb.addquery(prev, radius);
}
prev = cn;
}
}
}
qs.init(N);
qb.init(N);
for (const auto &[a, b] : queries)
if (b == -1)
{
int ans = 0;
const auto [v0, v1] = edges[a - 1];
const int start = centroid::depth[v0] > centroid::depth[v1] ? v0 : v1;
int prev;
for (int cn = start; cn != -1; cn = centroid::up[cn])
{
const ll dist = max(lca::getdist(v0, cn), lca::getdist(v1, cn));
if (dist < MAXR)
{
ans += qs.query(cn, dist);
if (cn != start)
ans -= qb.query(prev, dist);
}
prev = cn;
}
printf("%d\n", ans);
}
else
{
const int start = a;
int prev;
for (int cn = start; cn != -1; cn = centroid::up[cn])
{
const ll radius = b - lca::getdist(start, cn);
if (radius > 0)
{
qs.update(cn, radius);
if (cn != start)
qb.update(prev, radius);
}
prev = cn;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 571ms
memory: 51872kb
input:
100000 2670 75097 4080 87477 75802 1712 51835 36626 2883 19412 25923 5852 23976 19312 2520 82536 19514 2492 27160 66601 4483 99087 15088 3504 47050 58820 2964 37063 5696 9901 7717 1496 4891 79136 5448 4340 22575 81285 9289 96280 3803 9877 41980 32139 2855 44236 64938 3298 5983 99947 9666 95856 62545...
output:
0 0 0 2 2 5 2 2 3 4 4 7 8 9 11 10 14 12 12 10 11 10 10 9 10 11 11 9 15 11 14 13 14 16 11 17 15 13 15 14 14 20 15 20 22 22 20 17 23 23 24 29 24 26 30 31 36 28 37 39 35 34 45 39 46 45 43 46 42 49 44 50 43 47 52 50 49 57 51 56 61 58 68 66 69 69 61 63 67 63 72 74 78 72 73 78 77 73 85 76 86 82 85 76 82 8...
result:
ok 50000 lines
Test #2:
score: 0
Accepted
time: 340ms
memory: 43160kb
input:
100000 30038 18547 1594 65857 34063 4575 36600 72585 2328 99199 77595 1590 64257 48199 589 72301 40302 5083 69474 97536 606 60079 67381 9331 65982 39033 205 84122 65285 8508 18167 44905 3704 93490 94986 5941 27155 46374 6616 36232 62969 2212 79807 68652 7199 87352 59101 6880 94571 53224 3552 63610 8...
output:
0 1 3 3 3 3 4 6 10 10 12 14 14 16 18 19 19 19 19 22 22 23 23 23 23 24 25 26 26 26 26 26 26 28 31 31 31 31 31 34 34 36 40 41 41 42 42 42 42 42 44 44 44 47 48 48 48 48 48 48 48 48 48 49 50 50 53 54 54 55 55 56 56 56 56 56 59 62 62 62 62 62 62 62 62 62 62 63 65 67 69 69 69 73 73 73 74 76 76 76 76 76 79...
result:
ok 50000 lines
Test #3:
score: 0
Accepted
time: 220ms
memory: 35264kb
input:
100000 61878 94907 27495452 40498 66053 163324081 9987 91760 269034612 88613 6169 634714395 87422 83687 263182872 22328 64374 595886322 57437 38976 201931120 75020 26926 516189886 88639 96262 269100132 88285 44915 173237252 88407 91931 174315082 12843 50312 641940581 13297 52746 120211351 89089 4638...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 50000 lines
Test #4:
score: 0
Accepted
time: 220ms
memory: 35272kb
input:
100000 45843 69600 747867718 13793 70429 681785830 79985 74443 517803908 38369 67457 257059055 49843 59820 901603712 26439 25214 598556764 10275 5998 613157018 13517 10279 61272074 45577 49749 153772596 30727 68824 827689136 21752 9334 936611496 49173 73121 899562409 67808 9217 665070707 38351 13721...
output:
0 0 0 0 3 0 0 0 0 1 1 0 4 2 0 1 1 0 2 0 3 1 0 0 0 1 1 0 1 2 1 0 0 1 0 1 1 2 2 2 0 0 0 0 2 0 1 1 0 0 3 2 0 0 0 0 0 1 0 1 0 1 0 0 0 2 2 2 0 0 1 0 0 1 1 0 0 0 1 3 2 0 0 0 0 0 0 2 2 0 0 0 0 3 2 3 1 1 0 0 3 1 1 0 2 1 1 2 1 0 1 2 1 0 4 2 1 3 1 1 1 0 0 0 0 1 3 1 1 1 2 1 2 1 0 1 1 0 0 0 2 0 0 0 3 3 1 0 1 1 ...
result:
ok 50000 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 21128kb
input:
10 1 6 50 5 7 60 10 7 57 1 7 7 8 10 71 9 8 66 1 3 79 9 4 92 8 2 41 8 ? 5 ? 2 + 5 159 ? 7 ? 4 + 9 184 ? 7 + 3 291
output:
0 0 1 1 1
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 432ms
memory: 43256kb
input:
100000 34346 47902 18 27392 33766 77 6756 26094 49 22936 48815 19 5650 6237 49 30025 40524 59 54595 38103 73 31226 14746 66 90535 30187 7 31954 7326 41 88688 84625 35 87060 2678 4 51031 33729 53 78866 33403 76 16783 75299 96 96244 52833 50 72746 8315 62 3610 74402 43 5479 75776 55 98976 97524 74 261...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 2 0 0 3 0 1 0 1 0 2 3 0 0 0 0 0 0 1 3 0 1 0 0 1 0 0 1 0 2 2 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 2 3 0 0 1 1 2 1 1 2 0 0 1 0 0 3 1 0 0 1 2 1 1 0 1 0 1 1 0 2 0 1 ...
result:
ok 50000 lines
Test #7:
score: 0
Accepted
time: 584ms
memory: 49640kb
input:
100000 64148 54183 29 11068 35332 64 25618 18806 90 77040 76732 10 84812 90880 38 42283 75749 18 16322 30644 94 36973 59934 83 29747 75832 83 65108 11462 34 56098 73933 71 13086 78104 88 61180 33475 85 14006 4857 5 3734 96760 71 71250 14549 2 33684 24761 9 14693 12183 86 16730 80793 35 4985 57321 20...
output:
0 0 3 3 3 5 8 10 10 11 12 13 12 13 13 13 14 14 15 16 16 18 17 21 23 22 23 22 22 26 26 33 36 37 36 36 37 36 38 39 41 38 39 42 43 42 42 46 46 46 48 53 49 52 53 54 53 56 58 57 54 59 59 58 58 59 59 55 58 62 58 62 62 60 60 68 68 65 64 70 69 70 72 78 78 76 76 76 77 80 79 80 82 80 84 85 84 86 89 87 83 90 9...
result:
ok 50000 lines
Test #8:
score: 0
Accepted
time: 606ms
memory: 48688kb
input:
100000 14082 229 36 27210 94270 83 4742 68213 50 87953 67081 92 51909 51726 24 90045 60667 69 24283 69653 69 315 54923 19 44878 20782 60 65714 37239 18 18550 90268 99 90511 90267 26 74527 52573 9 44461 37153 92 94712 75548 81 54222 86266 71 99559 95348 72 19824 84320 53 57415 91290 10 1848 64264 73 ...
output:
29569 22292 26968 29422 29480 29605 28379 19743 24389 24969 24814 19826 28407 22403 29124 28900 24214 21261 20969 29297 22382 27345 16938 24009 21936 21580 28754 27089 26016 28921 28981 26058 26175 17364 29296 20002 27815 29591 23866 26980 26606 20345 27293 19831 20130 18982 27761 25353 21109 16845 ...
result:
ok 50000 lines
Test #9:
score: 0
Accepted
time: 5ms
memory: 19140kb
input:
10 5 9 19 10 7 2 7 8 62 4 6 79 1 4 34 2 10 44 2 3 27 6 3 52 1 9 65 8 + 7 67 ? 2 + 2 15 ? 5 ? 5 ? 5 + 9 6 ? 9
output:
1 0 0 0 0
result:
ok 5 lines
Test #10:
score: 0
Accepted
time: 269ms
memory: 41944kb
input:
100000 76345 58764 90 38618 20579 17 64447 62815 58 59951 76798 55 74438 62576 95 53180 2222 89 11870 17020 38 39889 48984 74 16333 40563 97 25845 69446 58 5310 92817 62 3253 1870 7 89005 49525 84 82761 65333 77 84354 79477 21 580 24067 88 37079 78987 1 71193 72699 69 74616 30155 89 57080 85169 71 6...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 ...
result:
ok 50000 lines
Test #11:
score: 0
Accepted
time: 554ms
memory: 53756kb
input:
100000 93170 87268 37 92583 41762 3 93445 95084 53 73369 81234 79 22891 43413 79 16715 69518 7 24171 20852 78 85174 42270 89 66924 67254 49 43354 42747 38 49859 42160 93 40042 50857 22 4048 65749 86 24257 79582 28 87393 44008 99 72905 724 0 91334 97136 21 94537 97499 73 25630 70522 17 60066 15405 10...
output:
0 0 0 0 1 1 1 1 3 4 3 4 4 4 7 7 7 7 7 8 7 9 10 10 10 10 10 14 15 15 17 17 17 17 17 17 19 18 19 23 26 26 24 27 26 29 28 30 30 26 31 35 36 37 38 39 40 41 40 42 40 38 36 42 36 39 40 38 40 50 51 50 54 42 44 56 45 56 59 61 51 63 61 68 62 67 62 69 55 70 68 70 72 72 74 65 66 60 67 74 79 81 67 76 71 90 88 9...
result:
ok 50000 lines
Test #12:
score: 0
Accepted
time: 515ms
memory: 51624kb
input:
100000 19572 74611 8 48607 74319 78 93319 98288 59 52549 90890 45 94797 90913 3 39349 35315 61 38406 98513 80 93016 86528 75 8738 42441 86 30903 41462 74 10393 85631 20 42211 49293 9 94579 14667 32 12354 61859 3 74498 17678 30 73444 85087 70 66415 69027 94 43638 69756 59 39651 46403 85 85460 86047 9...
output:
9967 10077 10052 9942 10077 10159 9742 9523 8936 9982 9997 9033 10148 10124 10094 10155 10003 10077 10088 10116 9958 10208 6409 8007 10173 10046 9956 10078 8473 10167 9797 6675 10136 10067 10098 10107 10033 10138 9480 7747 10040 9954 10013 8801 9980 5539 9953 10077 10072 9992 10040 10153 10134 7920 ...
result:
ok 50000 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 19076kb
input:
10 2 9 4 7 9 90 9 6 18 9 3 17 9 4 36 8 9 4 9 5 11 9 1 99 9 10 75 10 + 2 5 + 6 75 ? 8 + 10 14 ? 4 ? 2 ? 4 + 5 96 ? 8 + 10 53
output:
0 1 0 1 0
result:
ok 5 lines
Test #14:
score: 0
Accepted
time: 79ms
memory: 34164kb
input:
100000 49647 87470 68018 49647 66838 706542 90701 49647 804547 49647 49695 565349 89649 49647 58330 85202 49647 867857 49647 36014 819333 72467 49647 976326 49647 79763 583342 70175 49647 517474 49647 33568 520456 1985 49647 345782 66678 49647 972856 49647 68759 529647 49647 74524 568714 61394 49647...
output:
2 2 3 3 0 0 3 1 7 7 7 0 0 8 6 8 6 4 7 1 6 8 4 7 6 14 5 10 0 4 13 3 14 1 15 7 12 5 3 7 5 15 18 7 4 8 0 3 22 8 5 5 2 16 3 15 6 0 14 5 26 27 3 4 4 28 9 4 0 4 21 5 21 33 3 30 4 14 13 10 14 21 8 36 6 27 38 10 5 32 12 7 0 35 7 7 10 17 10 38 5 2 0 5 5 37 2 45 44 0 44 39 8 4 31 11 2 20 31 10 37 0 0 16 12 1 ...
result:
ok 50000 lines
Test #15:
score: 0
Accepted
time: 83ms
memory: 34692kb
input:
100000 89731 79663 351984 79663 48602 135355 79663 1628 661293 37635 79663 426439 42597 79663 617809 80941 79663 434012 79663 55353 351562 70259 79663 728593 56083 79663 465864 79663 49873 535094 79663 82032 99951 79663 72331 884689 4287 79663 744479 53983 79663 394859 79663 11490 97473 23469 79663 ...
output:
1 1 0 5 3 2 5 3 9 4 12 9 8 13 7 7 5 8 16 5 9 14 11 6 9 7 9 9 17 10 18 22 10 20 18 31 8 23 34 23 27 15 10 25 42 12 10 30 12 29 37 22 14 12 15 20 17 21 17 46 50 46 25 13 17 15 25 21 46 33 48 52 15 31 13 54 47 51 41 27 13 17 36 13 17 28 42 13 54 16 55 20 43 52 40 20 19 28 34 60 52 20 41 36 40 48 56 38 ...
result:
ok 50000 lines
Test #16:
score: 0
Accepted
time: 106ms
memory: 35132kb
input:
100000 21181 45480 383856 34048 21181 325232 21181 11533 106623 38797 21181 537777 14756 21181 106703 21181 95747 645967 21181 31947 917286 21181 83178 496425 21181 40900 130293 73538 21181 904098 21181 80057 191948 83460 21181 805492 21181 24716 460337 21181 27955 783121 21181 26269 144971 70919 21...
output:
1 1 1 1 3 4 5 7 7 7 7 7 7 10 10 10 10 16 18 18 18 18 19 19 20 20 20 20 20 22 26 26 31 31 34 35 34 34 34 36 36 37 38 39 40 41 43 43 46 46 47 48 49 50 49 53 52 55 55 55 55 55 57 60 58 58 58 62 62 62 61 66 68 67 68 69 68 70 72 73 77 73 76 74 79 78 80 81 81 82 83 84 87 87 89 89 89 89 89 89 91 90 92 94 9...
result:
ok 50000 lines
Test #17:
score: 0
Accepted
time: 4ms
memory: 19368kb
input:
10 10 4 0 7 3 0 10 6 1 5 1 1 5 10 1 8 6 0 10 2 1 1 9 1 1 7 1 10 ? 4 + 6 2 + 9 0 ? 8 + 8 1 + 10 0 ? 4 + 4 2 ? 5 ? 7
output:
0 0 0 2 2
result:
ok 5 lines
Test #18:
score: -100
Wrong Answer
time: 218ms
memory: 38412kb
input:
100000 50403 23870 1 2269 77786 0 88236 65765 0 28248 4408 0 74558 79109 1 75664 73208 1 10792 28375 1 98567 27634 0 90845 81177 0 32096 76545 1 11733 25888 1 68554 31308 0 1066 2492 0 93224 8314 1 69887 89588 1 16083 47361 1 60248 97232 1 86630 50173 0 31340 46107 0 20258 51269 0 39376 44028 0 8841...
output:
0 0 0 0 0 1 0 3 1 3 1 1 1 0 0 0 0 0 1 2 3 5 5 4 9 6 8 0 5 9 0 6 7 7 0 2 7 7 5 10 0 0 0 8 5 7 16 13 2 4 7 3 4 1 1 10 18 2 8 18 1 15 5 13 16 3 11 0 6 13 21 6 0 6 5 16 6 5 1 1 6 24 0 3 20 9 16 4 24 5 14 15 0 0 8 8 11 0 20 10 0 8 7 10 6 8 5 35 2 6 22 1 7 8 3 2 7 4 8 0 8 10 1 13 5 2 4 7 12 36 3 10 2 1 38...
result:
wrong answer 138th lines differ - expected: '19', found: '17'