oj.uz

Submission #102266

# Submission time Handle Problem Language Result Execution time Memory
102266 2019-03-24T04:41:53 Z ToMo01 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 854 ms 67540 KB 
/*input
15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7	
*/
#include <bits/stdc++.h>
using namespace std;

int read() {
	int number = 0, c = getchar();
	for(; !(c > 47 && c < 58); c = getchar());
	for(; (c > 47 && c < 58); c = getchar()) number = (number << 3) + (number << 1) + c - 48;
	return number;
}

const int N = 200005;

struct Edge {
	int to, f, b;
	Edge(int _to = 0, int _f = 0, int _b = 0):
		to(_to), f(_f), b(_b) {}
} edge[400000];

long long upVal[N], downVal[N], revUpVal[N], revDownVal[N], f[N][3], h[N], tour[N];
vector<int> G[N];

struct SegmentTree {
	pair<long long, int> t[N << 2];
	long long lazy[N << 2];

	SegmentTree() { 
		memset(t, 0, sizeof t);
		memset(lazy, 0, sizeof lazy);
	}

	void build(int node, int l, int r) {
		if(l == r) t[node] = make_pair(h[tour[l]], tour[l]);
		else {
			int mid = (l + r) >> 1;
			build(node << 1, l, mid);
			build(node << 1 | 1, mid + 1, r);
			t[node] = max(t[node << 1], t[node << 1 | 1]);
		}
	}

	void down(int node, int l, int r) {
		if(lazy[node] == 0) return;

		int cur = lazy[node]; lazy[node] = 0;
		if(l != r) {
			lazy[node << 1] += cur;
			lazy[node << 1 | 1] += cur;
		}
		t[node].first += cur;
	}

	void update(int node, int l, int r, int u, int v, int val) {
		down(node, l, r);
		if(v < l || r < u) return;
		if(u <= l && r <= v) {
			lazy[node] += val;
			down(node, l, r); return;
		}
		int mid = (l + r) >> 1;
		update(node << 1, l, mid, u, v, val);
		update(node << 1 | 1, mid + 1, r, u, v, val);
		t[node] = max(t[node << 1], t[node << 1 | 1]);
	}
} seg;

void upOne(int u, int p) {
	upVal[u] = revUpVal[u] = 0;
	for(int id : G[u]) {
		int v = edge[id].to;
		if(v == p) continue;
		
		upOne(v, u);
		upVal[u] += upVal[v] + edge[id].b;
		revUpVal[u] += revUpVal[v] + edge[id].f;
	}
}

void downOne(int u, int p) {
	for(int id : G[u]) {
		int v = edge[id].to;
		if(v == p) continue;
		downVal[v] = downVal[u] + upVal[u] - upVal[v] - edge[id].b + edge[id].f;
		revDownVal[v] = revDownVal[u] + revUpVal[u] - revUpVal[v] - edge[id].f + edge[id].b;
		downOne(v, u);
	}
}

int root;
pair<long long, long long> opt[N];
long long minDis = 1e18;

void dfs(int u, int p) {
	if(G[u].size() == 1) {
		f[u][0] = f[u][1] = 0; return;
	}

	f[u][0] = 0;
	for(int id : G[u]) {
		int v = edge[id].to;
		if(v == p) continue;

		dfs(v, u);
		long long cur0 = f[u][0], cur1 = f[u][1], cur2 = f[u][2];
		f[u][0] = cur0 + f[v][0] + edge[id].f;
		f[u][1] = min(cur0 + f[v][1], cur1 + f[v][0] + edge[id].f);
		f[u][2] = min(cur1 + f[v][1], cur2 + f[v][0] + edge[id].f);
	}
	if(f[u][2] + revDownVal[u] < minDis) minDis = f[u][2] + revDownVal[u], root = u;
}

long long Ans[N];
int start[N], done[N], traversalTime, par[N], visit[N], n;

void redfs(int u) {
	if(G[u].size() == 1) opt[u] = make_pair(h[u], u);

	start[u] = ++ traversalTime;
	tour[traversalTime] = u;
	for(int id : G[u]) {
		int v = edge[id].to;
		if(v == par[u]) continue;

		Ans[2] += edge[id].f;
		h[v] = h[u] + edge[id].f;
		par[v] = u, redfs(v);

		if(u != root) opt[u] = max(opt[u], opt[v]);
			else {
				if(opt[v].first > h[opt[u].second]) opt[u].second = opt[v].second;
				if(h[opt[u].first] < h[opt[u].second]) swap(opt[u].first, opt[u].second);
			}
	}
	done[u] = traversalTime;
}

void Pick(int u) {
	for(; !visit[u]; u = par[u]) seg.update(1, 1, n, start[u], done[u], h[par[u]] - h[u]), visit[u] = 1;
}

int main() {
	n = read();
	for(int i = 1; i < n; ++ i) {
		int u = read(), v = read(), C = read(), D = read();
		edge[i << 1] = Edge(v, C, D), edge[i << 1 | 1] = Edge(u, D, C);
		G[u].emplace_back(i << 1), G[v].emplace_back(i << 1 | 1);
	}

	if(n == 2) {
		for(int q = read(); q -- > 0;) {
			int x = read();
			if(x == 2) puts("0");
				else printf("%d\n", min(edge[2].f, edge[2].b));
		}
		return 0;
	}

	for(int i = 1; i <= n; ++ i) if(G[i].size() > 1) root = i;

	upOne(root, root), downOne(root, root);
	for(int i = 1; i <= n; ++ i) Ans[1] = min(Ans[1], -(upVal[i] + downVal[i]));
	for(int i = 1; i < n; ++ i) Ans[1] += edge[i << 1].f + edge[i << 1].b;

	memset(f, 63, sizeof f), dfs(root, root);
	redfs(root), seg.build(1, 1, n);

	Ans[2] -= h[opt[root].first] + h[opt[root].second];
	for(int i = 1; i <= n; ++ i) visit[i] = (i == root);
	Pick(opt[root].first), Pick(opt[root].second);

	for(int i = 3; i <= n; ++ i) {
		if(seg.t[1].first == 0) {
			Ans[i] = 0; break;
		}
		Ans[i] = Ans[i - 1] - seg.t[1].first, Pick(seg.t[1].second);
	}
	for(int q = read(); q -- > 0;) printf("%lld\n", Ans[read()]);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28536 KB Output is correct
2 Correct 32 ms 33280 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 29 ms 33272 KB Output is correct
5 Correct 31 ms 33316 KB Output is correct
6 Correct 29 ms 33272 KB Output is correct
7 Incorrect 31 ms 33272 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 28544 KB Output is correct
2 Correct 573 ms 56908 KB Output is correct
3 Correct 789 ms 63992 KB Output is correct
4 Correct 664 ms 56072 KB Output is correct
5 Correct 494 ms 56952 KB Output is correct
6 Correct 561 ms 58492 KB Output is correct
7 Correct 400 ms 57072 KB Output is correct
8 Correct 854 ms 67192 KB Output is correct
9 Correct 556 ms 57612 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28504 KB Output is correct
2 Correct 548 ms 56820 KB Output is correct
3 Correct 797 ms 65732 KB Output is correct
4 Correct 635 ms 58332 KB Output is correct
5 Correct 505 ms 59252 KB Output is correct
6 Correct 602 ms 60540 KB Output is correct
7 Correct 379 ms 59752 KB Output is correct
8 Correct 689 ms 67540 KB Output is correct
9 Correct 482 ms 59700 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28536 KB Output is correct
2 Correct 32 ms 33280 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 29 ms 33272 KB Output is correct
5 Correct 31 ms 33316 KB Output is correct
6 Correct 29 ms 33272 KB Output is correct
7 Incorrect 31 ms 33272 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 28544 KB Output is correct
2 Correct 573 ms 56908 KB Output is correct
3 Correct 789 ms 63992 KB Output is correct
4 Correct 664 ms 56072 KB Output is correct
5 Correct 494 ms 56952 KB Output is correct
6 Correct 561 ms 58492 KB Output is correct
7 Correct 400 ms 57072 KB Output is correct
8 Correct 854 ms 67192 KB Output is correct
9 Correct 556 ms 57612 KB Output is correct
10 Correct 28 ms 28504 KB Output is correct
11 Correct 548 ms 56820 KB Output is correct
12 Correct 797 ms 65732 KB Output is correct
13 Correct 635 ms 58332 KB Output is correct
14 Correct 505 ms 59252 KB Output is correct
15 Correct 602 ms 60540 KB Output is correct
16 Correct 379 ms 59752 KB Output is correct
17 Correct 689 ms 67540 KB Output is correct
18 Correct 482 ms 59700 KB Output is correct
19 Correct 28 ms 28500 KB Output is correct
20 Incorrect 522 ms 59156 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28536 KB Output is correct
2 Correct 32 ms 33280 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 29 ms 33272 KB Output is correct
5 Correct 31 ms 33316 KB Output is correct
6 Correct 29 ms 33272 KB Output is correct
7 Incorrect 31 ms 33272 KB Output isn't correct
8 Halted 0 ms 0 KB -