oj.uz

Submission #376248

# Submission time Handle Problem Language Result Execution time Memory
376248 2021-03-11T06:05:18 Z Kevin_Zhang_TW Designated Cities (JOI19_designated_cities) C++17
16 / 100
 571 ms 48920 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);
	sort(AI(edge[x]), [&](pair<int,int> a, pair<int,int> b) {
		return a.second + gain[a.first] > b.second + gain[b.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);
	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
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 5116 KB Output is correct
8 Incorrect 4 ms 5100 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 449 ms 28512 KB Output is correct
3 Correct 557 ms 47884 KB Output is correct
4 Correct 426 ms 28896 KB Output is correct
5 Correct 400 ms 29324 KB Output is correct
6 Correct 462 ms 32364 KB Output is correct
7 Correct 356 ms 29420 KB Output is correct
8 Correct 571 ms 46920 KB Output is correct
9 Correct 249 ms 25308 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 441 ms 28728 KB Output is correct
3 Correct 557 ms 48920 KB Output is correct
4 Correct 415 ms 29540 KB Output is correct
5 Correct 436 ms 30300 KB Output is correct
6 Correct 442 ms 34140 KB Output is correct
7 Correct 279 ms 30684 KB Output is correct
8 Correct 507 ms 42432 KB Output is correct
9 Correct 246 ms 25948 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 5116 KB Output is correct
8 Incorrect 4 ms 5100 KB Output isn't correct
9 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 449 ms 28512 KB Output is correct
3 Correct 557 ms 47884 KB Output is correct
4 Correct 426 ms 28896 KB Output is correct
5 Correct 400 ms 29324 KB Output is correct
6 Correct 462 ms 32364 KB Output is correct
7 Correct 356 ms 29420 KB Output is correct
8 Correct 571 ms 46920 KB Output is correct
9 Correct 249 ms 25308 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 441 ms 28728 KB Output is correct
12 Correct 557 ms 48920 KB Output is correct
13 Correct 415 ms 29540 KB Output is correct
14 Correct 436 ms 30300 KB Output is correct
15 Correct 442 ms 34140 KB Output is correct
16 Correct 279 ms 30684 KB Output is correct
17 Correct 507 ms 42432 KB Output is correct
18 Correct 246 ms 25948 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Incorrect 438 ms 30844 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 5116 KB Output is correct
8 Incorrect 4 ms 5100 KB Output isn't correct
9 Halted 0 ms 0 KB -