Submission #102266

#	Time	Username	Problem	Language	Result	Execution time	Memory
102266		ToMo01	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	854 ms	67540 KiB

designated_cities

/*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
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44