oj.uz

Submission #204083

# Submission time Handle Problem Language Result Execution time Memory
204083 2020-02-24T09:40:57 Z ics0503 Designated Cities (JOI19_designated_cities) C++17
100 / 100
 769 ms 84456 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y, z; };
vector<xy>edge[212121];
long long D[212121], F[212121], FW[212121];
void get_DF(long long w,long long bef) {
	D[w] = F[w] = 0; FW[w] = w;
	for (xy E : edge[w]) if (E.x != bef) {
		get_DF(E.x, w);
		D[w] += D[E.x] + E.y;
		if (F[w] < F[E.x] + E.z) {
			F[w] = F[E.x] + E.z;
			FW[w] = FW[E.x];
		}
	}
}
long long resX[212121], resY[212121], l[212121], r[212121];
void get_res(long long w, long long bef, long long fromRoot) {
	long long sum = 0, cnt = 0;
	vector<pair<long long, long long>>L;
	for (xy E : edge[w]) if (E.x != bef) {
		sum += D[E.x] + E.y;
		L.push_back({ -(F[E.x] + E.z), FW[E.x] });
	}
	sort(L.begin(), L.end());
	resX[w] = sum + fromRoot;
	if (L.size() > 0)resY[w] = -(L[0].first) + sum + fromRoot, l[w] = w, r[w] = L[0].second;
	if (L.size() > 1)resY[w] = -(L[0].first + L[1].first) + sum + fromRoot, l[w] = L[0].second, r[w] = L[1].second;
	for (xy E : edge[w]) if (E.x != bef) get_res(E.x, w, fromRoot + sum - (D[E.x] + E.y) + E.z);
}
//segtree
struct ND { int l, r; long long max, maxw, pls; }tree[616161]; int treen = 1;
void update(int w) {
	int l = tree[w].l, r = tree[w].r;
	if (tree[l].max >= tree[r].max) tree[w].max = tree[l].max, tree[w].maxw = tree[l].maxw;
	else tree[w].max = tree[r].max, tree[w].maxw = tree[r].maxw;
}
void spread(int w) {
	long long l = tree[w].l, r = tree[w].r, pls = tree[w].pls;
	tree[l].max += pls; tree[l].pls += pls;
	tree[r].max += pls; tree[r].pls += pls;
	tree[w].pls = 0;
}
void plsV(int now, int s, int e, int l, int r, long long v) {
	if (s != e)spread(now);
	if (s == l&&e == r) {
		tree[now].pls += v;
		tree[now].max += v;
		if (l == r)tree[now].maxw = l;
		return;
	}
	if (tree[now].l == 0) { tree[now].l = ++treen; tree[treen] = { 0, 0, 0, 0 }; }
	if (tree[now].r == 0) { tree[now].r = ++treen; tree[treen] = { 0, 0, 0, 0 }; }
	int m = (s + e) / 2;
	if (l <= m)plsV(tree[now].l, s, m, l, min(r, m), v);
	if (m + 1 <= r)plsV(tree[now].r, m + 1, e, max(l, m + 1), r, v);
	update(now);
}
int getMinV() {
	if (tree[1].max == 0)return -1;
	return tree[1].maxw;
}
 
int S[212121], E[212121], R[212121], dfscnt = 0, pr[212121]; long long prV[212121], depth[212121], n;
void dfs(long long w, long long bef, long long befV, long long dep) {
	S[w] = ++dfscnt;  pr[w] = bef; prV[w] = befV; depth[w] = dep;
	R[S[w]] = w;
	for (xy E : edge[w]) if (E.x != bef) {
		dfs(E.x, w, E.z, dep + E.z);
	}
	E[w] = dfscnt;
}
long long eraseE(long long w) {
	if (prV[w] == 0)return 0;
	plsV(1, 1, n, S[w], E[w], -prV[w]);
	long long res = prV[w];
	prV[w] = 0;
	res+=eraseE(pr[w]);
	return res;
}
long long ans[212121];
int main() {
	long long  i, j, allsum = 0; scanf("%lld", &n);
	for (i = 0; i < n - 1; i++) {
		long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
		allsum += a; allsum += b;
		edge[s].push_back({ e, b, a });
		edge[e].push_back({ s, a, b });
	}
	get_DF(1, -1);
	get_res(1, -1, 0);
	long long rootSum = 0, root = 1;
	for (i = 1; i <= n; i++) if (ans[1] < resX[i])ans[1] = resX[i];
	for (i = 1; i <= n; i++) if (rootSum < resY[i])rootSum = resY[i], root = i;
	ans[1] = allsum - ans[1];
	ans[2] = allsum - rootSum;
	dfs(root, -1, 0, 0);
	for (i = 1; i <= n; i++) {
		plsV(1, 1, n, S[i], S[i], depth[i]);
	}
	eraseE(l[root]);
	eraseE(r[root]);
	for (i = 3; i <= n; i++) {
		int v = R[getMinV()];
		if (v == -1) { ans[i] = ans[i - 1]; continue; }
		ans[i] = ans[i-1] - eraseE(v);
	}
	long long q, x; scanf("%lld", &q);
	for (i = 0; i < q; i++) {
		scanf("%lld", &x);
		printf("%lld\n", ans[x]);
	}
	return 0;
}

Compilation message

designated_cities.cpp: In function 'void get_res(long long int, long long int, long long int)':
designated_cities.cpp:21:21: warning: unused variable 'cnt' [-Wunused-variable]
  long long sum = 0, cnt = 0;
                     ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:85:16: warning: unused variable 'j' [-Wunused-variable]
  long long  i, j, allsum = 0; scanf("%lld", &n);
                ^
designated_cities.cpp:85:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long  i, j, allsum = 0; scanf("%lld", &n);
                               ~~~~~^~~~~~~~~~~~
designated_cities.cpp:87:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long q, x; scanf("%lld", &q);
                  ~~~~~^~~~~~~~~~~~
designated_cities.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 9 ms 5496 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 8 ms 5368 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 711 ms 51700 KB Output is correct
3 Correct 712 ms 79140 KB Output is correct
4 Correct 642 ms 52076 KB Output is correct
5 Correct 665 ms 52984 KB Output is correct
6 Correct 692 ms 56696 KB Output is correct
7 Correct 615 ms 52872 KB Output is correct
8 Correct 747 ms 80376 KB Output is correct
9 Correct 552 ms 49368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 686 ms 52320 KB Output is correct
3 Correct 694 ms 84216 KB Output is correct
4 Correct 614 ms 52348 KB Output is correct
5 Correct 660 ms 53148 KB Output is correct
6 Correct 701 ms 57464 KB Output is correct
7 Correct 564 ms 54404 KB Output is correct
8 Correct 731 ms 70136 KB Output is correct
9 Correct 534 ms 49112 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 9 ms 5496 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 8 ms 5368 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 7 ms 5368 KB Output is correct
13 Correct 11 ms 5860 KB Output is correct
14 Correct 12 ms 6008 KB Output is correct
15 Correct 11 ms 5880 KB Output is correct
16 Correct 11 ms 5880 KB Output is correct
17 Correct 11 ms 5880 KB Output is correct
18 Correct 12 ms 5880 KB Output is correct
19 Correct 11 ms 5880 KB Output is correct
20 Correct 11 ms 5880 KB Output is correct
21 Correct 11 ms 5880 KB Output is correct
22 Correct 11 ms 5880 KB Output is correct
23 Correct 11 ms 5880 KB Output is correct
24 Correct 11 ms 6008 KB Output is correct
25 Correct 12 ms 6136 KB Output is correct
26 Correct 11 ms 5880 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 711 ms 51700 KB Output is correct
3 Correct 712 ms 79140 KB Output is correct
4 Correct 642 ms 52076 KB Output is correct
5 Correct 665 ms 52984 KB Output is correct
6 Correct 692 ms 56696 KB Output is correct
7 Correct 615 ms 52872 KB Output is correct
8 Correct 747 ms 80376 KB Output is correct
9 Correct 552 ms 49368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 686 ms 52320 KB Output is correct
12 Correct 694 ms 84216 KB Output is correct
13 Correct 614 ms 52348 KB Output is correct
14 Correct 660 ms 53148 KB Output is correct
15 Correct 701 ms 57464 KB Output is correct
16 Correct 564 ms 54404 KB Output is correct
17 Correct 731 ms 70136 KB Output is correct
18 Correct 534 ms 49112 KB Output is correct
19 Correct 8 ms 5368 KB Output is correct
20 Correct 687 ms 51960 KB Output is correct
21 Correct 769 ms 84456 KB Output is correct
22 Correct 621 ms 52088 KB Output is correct
23 Correct 700 ms 52472 KB Output is correct
24 Correct 661 ms 52216 KB Output is correct
25 Correct 704 ms 52216 KB Output is correct
26 Correct 697 ms 52348 KB Output is correct
27 Correct 668 ms 52536 KB Output is correct
28 Correct 701 ms 56184 KB Output is correct
29 Correct 686 ms 52472 KB Output is correct
30 Correct 646 ms 52360 KB Output is correct
31 Correct 608 ms 52388 KB Output is correct
32 Correct 728 ms 71032 KB Output is correct
33 Correct 552 ms 48984 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 9 ms 5496 KB Output is correct
7 Correct 8 ms 5368 KB Output is correct
8 Correct 8 ms 5368 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 8 ms 5368 KB Output is correct
13 Correct 711 ms 51700 KB Output is correct
14 Correct 712 ms 79140 KB Output is correct
15 Correct 642 ms 52076 KB Output is correct
16 Correct 665 ms 52984 KB Output is correct
17 Correct 692 ms 56696 KB Output is correct
18 Correct 615 ms 52872 KB Output is correct
19 Correct 747 ms 80376 KB Output is correct
20 Correct 552 ms 49368 KB Output is correct
21 Correct 8 ms 5368 KB Output is correct
22 Correct 686 ms 52320 KB Output is correct
23 Correct 694 ms 84216 KB Output is correct
24 Correct 614 ms 52348 KB Output is correct
25 Correct 660 ms 53148 KB Output is correct
26 Correct 701 ms 57464 KB Output is correct
27 Correct 564 ms 54404 KB Output is correct
28 Correct 731 ms 70136 KB Output is correct
29 Correct 534 ms 49112 KB Output is correct
30 Correct 7 ms 5368 KB Output is correct
31 Correct 11 ms 5860 KB Output is correct
32 Correct 12 ms 6008 KB Output is correct
33 Correct 11 ms 5880 KB Output is correct
34 Correct 11 ms 5880 KB Output is correct
35 Correct 11 ms 5880 KB Output is correct
36 Correct 12 ms 5880 KB Output is correct
37 Correct 11 ms 5880 KB Output is correct
38 Correct 11 ms 5880 KB Output is correct
39 Correct 11 ms 5880 KB Output is correct
40 Correct 11 ms 5880 KB Output is correct
41 Correct 11 ms 5880 KB Output is correct
42 Correct 11 ms 6008 KB Output is correct
43 Correct 12 ms 6136 KB Output is correct
44 Correct 11 ms 5880 KB Output is correct
45 Correct 8 ms 5368 KB Output is correct
46 Correct 687 ms 51960 KB Output is correct
47 Correct 769 ms 84456 KB Output is correct
48 Correct 621 ms 52088 KB Output is correct
49 Correct 700 ms 52472 KB Output is correct
50 Correct 661 ms 52216 KB Output is correct
51 Correct 704 ms 52216 KB Output is correct
52 Correct 697 ms 52348 KB Output is correct
53 Correct 668 ms 52536 KB Output is correct
54 Correct 701 ms 56184 KB Output is correct
55 Correct 686 ms 52472 KB Output is correct
56 Correct 646 ms 52360 KB Output is correct
57 Correct 608 ms 52388 KB Output is correct
58 Correct 728 ms 71032 KB Output is correct
59 Correct 552 ms 48984 KB Output is correct
60 Correct 8 ms 5368 KB Output is correct
61 Correct 754 ms 53112 KB Output is correct
62 Correct 733 ms 79224 KB Output is correct
63 Correct 671 ms 52600 KB Output is correct
64 Correct 759 ms 52984 KB Output is correct
65 Correct 722 ms 52636 KB Output is correct
66 Correct 740 ms 53036 KB Output is correct
67 Correct 729 ms 52856 KB Output is correct
68 Correct 734 ms 53392 KB Output is correct
69 Correct 747 ms 56312 KB Output is correct
70 Correct 747 ms 53496 KB Output is correct
71 Correct 702 ms 53460 KB Output is correct
72 Correct 654 ms 53912 KB Output is correct
73 Correct 763 ms 68344 KB Output is correct
74 Correct 602 ms 50916 KB Output is correct