oj.uz

Submission #204080

# Submission time Handle Problem Language Result Execution time Memory
204080 2020-02-24T09:26:49 Z ics0503 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 780 ms 88184 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, int 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Incorrect 8 ms 5368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 525 ms 56184 KB Output is correct
3 Correct 763 ms 83624 KB Output is correct
4 Correct 609 ms 54952 KB Output is correct
5 Correct 628 ms 57088 KB Output is correct
6 Correct 566 ms 60536 KB Output is correct
7 Correct 621 ms 56976 KB Output is correct
8 Correct 780 ms 84600 KB Output is correct
9 Correct 548 ms 53588 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5372 KB Output is correct
2 Correct 531 ms 56184 KB Output is correct
3 Correct 703 ms 88184 KB Output is correct
4 Correct 632 ms 54832 KB Output is correct
5 Correct 632 ms 57172 KB Output is correct
6 Correct 568 ms 61204 KB Output is correct
7 Correct 570 ms 58240 KB Output is correct
8 Correct 698 ms 74360 KB Output is correct
9 Correct 571 ms 53180 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Incorrect 8 ms 5368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 525 ms 56184 KB Output is correct
3 Correct 763 ms 83624 KB Output is correct
4 Correct 609 ms 54952 KB Output is correct
5 Correct 628 ms 57088 KB Output is correct
6 Correct 566 ms 60536 KB Output is correct
7 Correct 621 ms 56976 KB Output is correct
8 Correct 780 ms 84600 KB Output is correct
9 Correct 548 ms 53588 KB Output is correct
10 Correct 8 ms 5372 KB Output is correct
11 Correct 531 ms 56184 KB Output is correct
12 Correct 703 ms 88184 KB Output is correct
13 Correct 632 ms 54832 KB Output is correct
14 Correct 632 ms 57172 KB Output is correct
15 Correct 568 ms 61204 KB Output is correct
16 Correct 570 ms 58240 KB Output is correct
17 Correct 698 ms 74360 KB Output is correct
18 Correct 571 ms 53180 KB Output is correct
19 Correct 8 ms 5368 KB Output is correct
20 Incorrect 554 ms 56440 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Incorrect 8 ms 5368 KB Output isn't correct
3 Halted 0 ms 0 KB -