QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#306559#5249. BanditsLaStataleBlueWA 606ms53756kbC++174.9kb2024-01-16 21:39:242024-01-16 21:39:25

Judging History

你现在查看的是最新测评结果

  • [2024-01-16 21:39:25]
  • 评测
  • 测评结果:WA
  • 用时:606ms
  • 内存:53756kb
  • [2024-01-16 21:39:24]
  • 提交

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;
}

詳細信息

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'