oj.uz

Submission #383721

# Submission time Handle Problem Language Result Execution time Memory
383721 2021-03-30T17:08:48 Z rqi Designated Cities (JOI19_designated_cities) C++14
56 / 100
 2000 ms 53472 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef vector<int> vi;

#define f first
#define s second
#define mp make_pair
#define pb push_back

#define sz(x) (int)(x).size()

void ckmax(ll&a, ll b){
	a = max(a, b);
}

const int mx = 200005;
int N;
int A[mx];
int B[mx];
ll C[mx];
ll D[mx];
int E[mx];

vector<pair<int, ll>> adj[mx];
ll tot_cost;
ll ans[mx];

bool done[mx];

int sub[mx];
vi cen_nodes;

void genSub(int node, int p = -1){
	cen_nodes.pb(node);
	sub[node] = 1;
	for(auto u: adj[node]){
		if(u.f == p || done[u.f]) continue;
		genSub(u.f, node);
		sub[node]+=sub[u.f];
	}
}

int getCen(int node, int tot_sz, int p = -1){
	for(auto u: adj[node]){
		if(u.f == p || done[u.f]) continue;
		if(sub[u.f] > tot_sz/2) return getCen(u.f, tot_sz, node);
	}
	return node;
}



int genCen(int node){
	cen_nodes.clear();
	genSub(node);
	return getCen(node, sub[node]);
}

pair<int, ll> par[mx];
ll sum_up[mx];
pair<ll, int> best_down[mx];

void genUpDown(int node, int p = -1){
	sum_up[node] = 0;
	best_down[node] = mp(0, node);

	for(auto u: adj[node]){
		if(u.f == p || done[u.f]) continue;
		ll bedge = 0;
		for(auto x: adj[u.f]){
			if(done[x.f]) continue;
			if(x.f == node){
				bedge = x.s;
				break;
			}
		}
		par[u.f] = mp(node, u.s);
		sum_up[node]+=bedge;
		genUpDown(u.f, node);
		sum_up[node]+=sum_up[u.f];
		best_down[node] = max(best_down[node], mp(best_down[u.f].f+u.s, best_down[u.f].s));
	}
}

bool taken[mx];

void genAns(int cen, ll offset){
	cen = genCen(cen);

	//process cen

	genUpDown(cen);

	//update ans - remember done/offset

	//cout << "cen, offset, sumup[cen]: " << cen << " " << offset << " " << sum_up[cen] << "\n";

	ckmax(ans[1], sum_up[cen]+offset);

	priority_queue<pair<ll, int>> pq;
	for(auto u: adj[cen]){
		if(done[u.f]) continue;
		pq.push(mp(best_down[u.f].f+par[u.f].s, best_down[u.f].s));
	}

	for(auto u: cen_nodes){
		taken[u] = 0;
	}
	taken[cen] = 1;

	ll cur_sum = 0;
	ll best_outside = 0;
	bool good = 0;
	for(int i = 1; i <= sz(cen_nodes); i++){
		if(sz(pq) == 0){
			ckmax(ans[i], cur_sum+sum_up[cen]+offset);
			continue;
		}
		int take_node = pq.top().s;
		pq.pop();

		//cout << "take_node: " << i << " " << take_node << "\n";
		while(true){
			cur_sum+=par[take_node].s;
			taken[take_node] = 1;
			//cout << "add: " << take_node << " " << par[take_node].s << "\n";
			for(auto u: adj[take_node]){
				if(done[u.f] || taken[u.f] || u.f == par[take_node].f) continue;
				pq.push(mp(best_down[u.f].f+par[u.f].s, best_down[u.f].s));
				//cout << "push: " << best_down[u.f].s << "\n";
			}
			if(taken[par[take_node].f]) break;
			take_node = par[take_node].f;
		}
		
		if(i == 1){
			for(auto u: adj[cen]){
				if(done[u.f]) continue;
				if(u.f != take_node){
					ckmax(best_outside, u.s+best_down[u.f].f);
				}
			}
		}

		if(i != 1 && par[take_node].f == cen){
			good = 1;
		}

		if(good){
			ckmax(ans[i], cur_sum+sum_up[cen]+offset);
			//cout << "ckmax(ans[]: " << i << " " << cur_sum+sum_up[cen]+offset << "\n";
		}
		else{
			ckmax(ans[i+1], cur_sum+best_outside+sum_up[cen]+offset);
			//cout << "ckmax(ans[]: " << i+1 << " " << cur_sum+best_outside+sum_up[cen]+offset << "\n";
		}
	}

	//recurse

	done[cen] = 1;

	vector<pair<int, ll>> recurse;
	for(auto u: adj[cen]){
		if(done[u.f]) continue;
		ll new_offset = offset+sum_up[cen]-sum_up[u.f]+u.s;
		for(auto x: adj[u.f]){
			if(x.f == cen){
				new_offset-=x.s;
				break;
			}
		}
		recurse.pb(mp(u.f, new_offset));
	}

	for(auto u: recurse){
		genAns(u.f, u.s);
	}
}

int main(){
	cin >> N;
	for(int i = 1; i <= N-1; i++){
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		adj[A[i]].pb(mp(B[i], C[i]));
		adj[B[i]].pb(mp(A[i], D[i]));
		tot_cost+=C[i]+D[i];
	}

	genAns(1, 0);

	// cout << "tot: " << tot_cost << "\n";
	// for(int i = 1; i <= N; i++){
	// 	cout << "i, ans[i]: " << i << " " << ans[i] << "\n";
	// }

	for(int i = 1; i <= N; i++){
		ans[i] = tot_cost-ans[i];
	}

	//cout << ans[N] << "\n";

	assert(ans[N] == 0);

	int Q;
	cin >> Q;
	for(int i = 1; i <= Q; i++){
		cin >> E[i];
		cout << ans[E[i]] << "\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 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5100 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 1237 ms 39736 KB Output is correct
3 Correct 1512 ms 50912 KB Output is correct
4 Correct 1244 ms 36448 KB Output is correct
5 Correct 636 ms 39968 KB Output is correct
6 Correct 1560 ms 41952 KB Output is correct
7 Correct 589 ms 42692 KB Output is correct
8 Correct 1549 ms 51876 KB Output is correct
9 Correct 529 ms 47316 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 1341 ms 40032 KB Output is correct
3 Correct 1504 ms 52832 KB Output is correct
4 Correct 1283 ms 36636 KB Output is correct
5 Correct 654 ms 40032 KB Output is correct
6 Correct 1680 ms 42208 KB Output is correct
7 Correct 539 ms 46676 KB Output is correct
8 Correct 1677 ms 48372 KB Output is correct
9 Correct 518 ms 47060 KB Output is correct

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 4 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 15 ms 5484 KB Output is correct
14 Correct 15 ms 5612 KB Output is correct
15 Correct 14 ms 5484 KB Output is correct
16 Correct 14 ms 5484 KB Output is correct
17 Correct 14 ms 5484 KB Output is correct
18 Correct 14 ms 5484 KB Output is correct
19 Correct 14 ms 5484 KB Output is correct
20 Correct 13 ms 5484 KB Output is correct
21 Correct 15 ms 5484 KB Output is correct
22 Correct 14 ms 5484 KB Output is correct
23 Correct 14 ms 5484 KB Output is correct
24 Correct 13 ms 5612 KB Output is correct
25 Correct 15 ms 5612 KB Output is correct
26 Correct 14 ms 5612 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 1237 ms 39736 KB Output is correct
3 Correct 1512 ms 50912 KB Output is correct
4 Correct 1244 ms 36448 KB Output is correct
5 Correct 636 ms 39968 KB Output is correct
6 Correct 1560 ms 41952 KB Output is correct
7 Correct 589 ms 42692 KB Output is correct
8 Correct 1549 ms 51876 KB Output is correct
9 Correct 529 ms 47316 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 1341 ms 40032 KB Output is correct
12 Correct 1504 ms 52832 KB Output is correct
13 Correct 1283 ms 36636 KB Output is correct
14 Correct 654 ms 40032 KB Output is correct
15 Correct 1680 ms 42208 KB Output is correct
16 Correct 539 ms 46676 KB Output is correct
17 Correct 1677 ms 48372 KB Output is correct
18 Correct 518 ms 47060 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 1297 ms 40032 KB Output is correct
21 Correct 1506 ms 53220 KB Output is correct
22 Correct 1227 ms 36704 KB Output is correct
23 Correct 1256 ms 40032 KB Output is correct
24 Correct 1239 ms 38880 KB Output is correct
25 Correct 1273 ms 40144 KB Output is correct
26 Correct 1271 ms 38652 KB Output is correct
27 Correct 643 ms 39728 KB Output is correct
28 Correct 1576 ms 41952 KB Output is correct
29 Correct 1249 ms 40288 KB Output is correct
30 Correct 1149 ms 40404 KB Output is correct
31 Correct 570 ms 43356 KB Output is correct
32 Correct 1650 ms 48740 KB Output is correct
33 Correct 521 ms 47548 KB Output is correct

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 4 ms 5100 KB Output is correct
12 Correct 5 ms 5100 KB Output is correct
13 Correct 1237 ms 39736 KB Output is correct
14 Correct 1512 ms 50912 KB Output is correct
15 Correct 1244 ms 36448 KB Output is correct
16 Correct 636 ms 39968 KB Output is correct
17 Correct 1560 ms 41952 KB Output is correct
18 Correct 589 ms 42692 KB Output is correct
19 Correct 1549 ms 51876 KB Output is correct
20 Correct 529 ms 47316 KB Output is correct
21 Correct 4 ms 5100 KB Output is correct
22 Correct 1341 ms 40032 KB Output is correct
23 Correct 1504 ms 52832 KB Output is correct
24 Correct 1283 ms 36636 KB Output is correct
25 Correct 654 ms 40032 KB Output is correct
26 Correct 1680 ms 42208 KB Output is correct
27 Correct 539 ms 46676 KB Output is correct
28 Correct 1677 ms 48372 KB Output is correct
29 Correct 518 ms 47060 KB Output is correct
30 Correct 4 ms 5100 KB Output is correct
31 Correct 15 ms 5484 KB Output is correct
32 Correct 15 ms 5612 KB Output is correct
33 Correct 14 ms 5484 KB Output is correct
34 Correct 14 ms 5484 KB Output is correct
35 Correct 14 ms 5484 KB Output is correct
36 Correct 14 ms 5484 KB Output is correct
37 Correct 14 ms 5484 KB Output is correct
38 Correct 13 ms 5484 KB Output is correct
39 Correct 15 ms 5484 KB Output is correct
40 Correct 14 ms 5484 KB Output is correct
41 Correct 14 ms 5484 KB Output is correct
42 Correct 13 ms 5612 KB Output is correct
43 Correct 15 ms 5612 KB Output is correct
44 Correct 14 ms 5612 KB Output is correct
45 Correct 4 ms 5100 KB Output is correct
46 Correct 1297 ms 40032 KB Output is correct
47 Correct 1506 ms 53220 KB Output is correct
48 Correct 1227 ms 36704 KB Output is correct
49 Correct 1256 ms 40032 KB Output is correct
50 Correct 1239 ms 38880 KB Output is correct
51 Correct 1273 ms 40144 KB Output is correct
52 Correct 1271 ms 38652 KB Output is correct
53 Correct 643 ms 39728 KB Output is correct
54 Correct 1576 ms 41952 KB Output is correct
55 Correct 1249 ms 40288 KB Output is correct
56 Correct 1149 ms 40404 KB Output is correct
57 Correct 570 ms 43356 KB Output is correct
58 Correct 1650 ms 48740 KB Output is correct
59 Correct 521 ms 47548 KB Output is correct
60 Correct 4 ms 5100 KB Output is correct
61 Correct 1801 ms 41440 KB Output is correct
62 Execution timed out 2003 ms 53472 KB Time limit exceeded
63 Halted 0 ms 0 KB -