Submission #376195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
376195	2021-03-11T04:01:05 Z	8e7	Designated Cities (JOI19_designated_cities)	C++14	23 / 100	2000 ms	22572 KB

designated_cities

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#define ll long long
#define maxn 200005
#define pii pair<int, ll>
#define ff first
#define ss second
#define mod 1000000007
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

vector<pii> adj[maxn];

ll tup[maxn], up[maxn], best[maxn], bind[maxn], ans[maxn];
int par[maxn];
bool done[maxn];
void dfs(int n, int pa) {
	par[n] = pa;
	for (auto v:adj[n]) {
		if (v.ff != pa) {
			dfs(v.ff, n);
			tup[n] += tup[v.ff] + up[v.ff];
			if (v.ss + best[v.ff] > best[n]) {
				best[n] = v.ss + best[v.ff];
				bind[n] = bind[v.ff] == 0 ? v.ff : bind[v.ff];
			}
		} else {
			up[n] = v.ss;
		}
	}
}
void reroot(int u, int v, ll w) {
	tup[u] -= tup[v] + up[v];
	up[u] = w;
	tup[v] += tup[u] + up[u];
	up[v] = 0;
}
int type = 1;
void solve(int n, int par) {
	ans[1] = max(ans[1], tup[n]);
	for (auto v:adj[n]) {
		if (v.ff != par) {
			ll tmp = up[v.ff];
			reroot(n, v.ff, v.ss);
			solve(v.ff, n);
			reroot(v.ff, n, tmp);
		}
	}
}

ll add = 0, addind = 0;
void getweight(int n, int par, ll cur) {
	if (cur > add) {
		addind = n;
		add = cur;
	}
	for (auto v:adj[n]) {
		if (v.ff != par) {
			getweight(v.ff, n, cur + (done[v.ff] ? 0 : v.ss));
		}
	}
}
int main() {
	io
	int n;
	cin >> n;
	ll tot = 0;
	for (int i = 0;i < n - 1;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		tot += c + d;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, d));
	}
	dfs(1, 0);
	solve(1, 0);
	int p1 = bind[1];
	for (int j = 1;j <= n;j++) tup[j] = 0, up[j] = 0, best[j] = 0, bind[j] = 0;
	dfs(p1, 0);
	ans[2] = tup[p1] + best[p1];
	int p2 = bind[p1], cur = p2;
	//p1 and p2 are diameter
	while (cur != p1) {
		done[cur] = 1;
		cur = par[cur];
	}

	for (int i = 3;i <= n;i++) {
		add = 0, addind = 0;
		getweight(p1, 0, 0);
		if (add == 0) {
			ans[i] = ans[i - 1];
		} else {
			ans[i] = ans[i - 1] + add;
			cur = addind;
			while (!done[cur]) {
				done[cur] = 1;
				cur = par[cur];
			}
		}
	}


	int q;
	cin >> q;
	for (int i = 0;i < q;i++) {
		int t;
		cin >> t;
		cout << tot - ans[t] << "\n";
	}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
1
2


 */

Subtask #1

6.0 / 6.0

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

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Execution timed out	2023 ms	22572 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5100 KB	Output is correct
2	Execution timed out	2086 ms	22508 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	4 ms	5100 KB	Output is correct
4	Correct	4 ms	5100 KB	Output is correct
5	Correct	4 ms	5100 KB	Output is correct
6	Correct	4 ms	5100 KB	Output is correct
7	Correct	4 ms	5100 KB	Output is correct
8	Correct	4 ms	5100 KB	Output is correct
9	Correct	4 ms	5100 KB	Output is correct
10	Correct	4 ms	5100 KB	Output is correct
11	Correct	5 ms	5100 KB	Output is correct
12	Correct	4 ms	5100 KB	Output is correct
13	Correct	74 ms	5356 KB	Output is correct
14	Correct	90 ms	5484 KB	Output is correct
15	Correct	72 ms	5356 KB	Output is correct
16	Correct	74 ms	5356 KB	Output is correct
17	Correct	74 ms	5356 KB	Output is correct
18	Correct	73 ms	5356 KB	Output is correct
19	Correct	87 ms	5356 KB	Output is correct
20	Correct	69 ms	5356 KB	Output is correct
21	Correct	71 ms	5356 KB	Output is correct
22	Correct	72 ms	5356 KB	Output is correct
23	Correct	63 ms	5356 KB	Output is correct
24	Correct	48 ms	5484 KB	Output is correct
25	Correct	87 ms	5484 KB	Output is correct
26	Correct	41 ms	5356 KB	Output is correct

Subtask #5

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Execution timed out	2023 ms	22572 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #6

0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5100 KB	Output is correct
2	Correct	4 ms	5100 KB	Output is correct
3	Correct	4 ms	5100 KB	Output is correct
4	Correct	4 ms	5100 KB	Output is correct
5	Correct	4 ms	5100 KB	Output is correct
6	Correct	4 ms	5100 KB	Output is correct
7	Correct	4 ms	5100 KB	Output is correct
8	Correct	4 ms	5100 KB	Output is correct
9	Correct	4 ms	5100 KB	Output is correct
10	Correct	4 ms	5100 KB	Output is correct
11	Correct	5 ms	5100 KB	Output is correct
12	Correct	4 ms	5100 KB	Output is correct
13	Execution timed out	2023 ms	22572 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-