oj.uz

Submission #376249

# Submission time Handle Problem Language Result Execution time Memory
376249 2021-03-11T06:08:05 Z Kevin_Zhang_TW Designated Cities (JOI19_designated_cities) C++17
22 / 100
 596 ms 46684 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 200010;
const ll inf = 1ll << 59;

int n, q;
ll dprt[MAX_N], dpson[MAX_N], res[MAX_N], allsum;
ll goup[MAX_N];
vector<pair<int,int>> edge[MAX_N];

ll dfs1(int x, int lst = -1) {
	ll uplen = 0;
	for (auto [u, w] : edge[x]) if (u != lst) 
		dpson[x] += dfs1(u, x);
	else uplen = w;
	return dpson[x] + uplen;
}

void dfs2(int x, int lst = -1, ll upson = 0) {
	if (lst == -1) dprt[x] = dpson[x];
	dprt[x] += upson;
	for (auto [u, w] : edge[x]) if (u == lst)
		dprt[x] -= w;
	for (auto [u, w] : edge[x]) if (u != lst)
		dfs2(u, x, dprt[x] + w);
}

pair<int,int> best[MAX_N];
ll bstsum[MAX_N];

pair<ll,ll> mxlen[MAX_N];

void dfs3(int x, int lst = -1) {
	mxlen[x] = {0, x};
	for (auto [u, w] : edge[x]) if (u != lst) {
		dfs3(u, x);
		if (chmax(bstsum[x], bstsum[u]))
			best[x] = best[u];
		mxlen[u].first += w;

		if (chmax(bstsum[x], 
					mxlen[x].first + mxlen[u].first + dprt[x]))
			best[x] = {mxlen[x].second, mxlen[u].second};
		chmax(mxlen[x], mxlen[u]);
	}
}

int pa[MAX_N], paint[MAX_N];
ll gain[MAX_N];

void dfs4(int x, int lst = -1) {
	if (paint[x]) gain[x] = 0;
	pa[x] = lst;
	int sz = 0;
	for (auto [u, w] : edge[x]) if (u != lst) {
		gain[u] = gain[x] + w;
		dfs4(u, x);
		edge[x][sz++] = {u, w};
	}
	edge[x].resize(sz);
}
void dfs6(int x, int lst = -1) {
	for (auto [u, w] : edge[x]) if (u != lst) {
		dfs6(u, x);
	}
	sort(AI(edge[x]), [&](pair<int,int> a, pair<int,int> b) {
		return a.second + gain[a.first] > b.second + gain[b.first];
	});
	if (edge[x].size())
		gain[x] = gain[ edge[x][0].first ];
}
int rt;
void takeout(int x) {
	while (x != -1) {
		paint[x] = true;
		x = pa[x];
	}
	dfs4(rt);
}

vector<ll> cand;

void dfs5(int x, int lst = -1, ll sum = 0) {
	if (paint[x]) sum = 0;
	for (auto [u, w] : edge[x]) if (u != lst) {
		dfs5(u, x, sum + w);
		sum = 0;
	}
	cand.pb(sum);
}

void solve() {
	dfs3(1);
	res[2] = bstsum[1];
	rt = best[1].first;
	dfs4(rt);
	takeout(best[1].second);
	dfs6(rt);
	dfs5(rt);
	sort(AI(cand));
	for (int i = 3;i <= n;++i) {
		res[i] = res[i-1];
		if (cand.size()) {
			res[i] += cand.back();
			cand.pop_back();
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int a, b, c, d, i = 1;i < n;++i) {
		cin >> a >> b >> c >> d;
		edge[a].pb(b, c);
		edge[b].pb(a, d);
		allsum += c + d;
	}

	dfs1(1);
	dfs2(1);

	res[1] = *max_element(dprt+1, dprt+1+n);

	solve();

	cin >> q;

	for (int i = 0, v;i < q;++i) {
		cin >> v;
		cout << allsum - res[v] << '\n';
	}
}

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 5248 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 5 ms 5100 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 467 ms 29360 KB Output is correct
3 Correct 594 ms 46556 KB Output is correct
4 Correct 430 ms 28336 KB Output is correct
5 Correct 436 ms 28124 KB Output is correct
6 Correct 476 ms 31196 KB Output is correct
7 Correct 354 ms 28148 KB Output is correct
8 Correct 596 ms 45660 KB Output is correct
9 Correct 252 ms 23908 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 473 ms 29136 KB Output is correct
3 Correct 581 ms 46684 KB Output is correct
4 Correct 477 ms 28540 KB Output is correct
5 Correct 464 ms 28400 KB Output is correct
6 Correct 472 ms 31964 KB Output is correct
7 Correct 325 ms 28768 KB Output is correct
8 Correct 547 ms 40416 KB Output is correct
9 Correct 275 ms 23872 KB Output is correct

Subtask #4
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 5248 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 Incorrect 7 ms 5484 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 467 ms 29360 KB Output is correct
3 Correct 594 ms 46556 KB Output is correct
4 Correct 430 ms 28336 KB Output is correct
5 Correct 436 ms 28124 KB Output is correct
6 Correct 476 ms 31196 KB Output is correct
7 Correct 354 ms 28148 KB Output is correct
8 Correct 596 ms 45660 KB Output is correct
9 Correct 252 ms 23908 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 473 ms 29136 KB Output is correct
12 Correct 581 ms 46684 KB Output is correct
13 Correct 477 ms 28540 KB Output is correct
14 Correct 464 ms 28400 KB Output is correct
15 Correct 472 ms 31964 KB Output is correct
16 Correct 325 ms 28768 KB Output is correct
17 Correct 547 ms 40416 KB Output is correct
18 Correct 275 ms 23872 KB Output is correct
19 Correct 4 ms 5248 KB Output is correct
20 Incorrect 469 ms 28868 KB Output isn't correct
21 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 5248 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 467 ms 29360 KB Output is correct
14 Correct 594 ms 46556 KB Output is correct
15 Correct 430 ms 28336 KB Output is correct
16 Correct 436 ms 28124 KB Output is correct
17 Correct 476 ms 31196 KB Output is correct
18 Correct 354 ms 28148 KB Output is correct
19 Correct 596 ms 45660 KB Output is correct
20 Correct 252 ms 23908 KB Output is correct
21 Correct 4 ms 5100 KB Output is correct
22 Correct 473 ms 29136 KB Output is correct
23 Correct 581 ms 46684 KB Output is correct
24 Correct 477 ms 28540 KB Output is correct
25 Correct 464 ms 28400 KB Output is correct
26 Correct 472 ms 31964 KB Output is correct
27 Correct 325 ms 28768 KB Output is correct
28 Correct 547 ms 40416 KB Output is correct
29 Correct 275 ms 23872 KB Output is correct
30 Correct 4 ms 5100 KB Output is correct
31 Incorrect 7 ms 5484 KB Output isn't correct
32 Halted 0 ms 0 KB -