oj.uz

Submission #383765

# Submission time Handle Problem Language Result Execution time Memory
383765 2021-03-30T19:28:33 Z rqi Designated Cities (JOI19_designated_cities) C++14
56 / 100
 2000 ms 43492 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
typedef vector<int> vi;
typedef vector<ll> vl;
 
#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];
 
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) 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) 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) continue;
		ll bedge = 0;
		for(auto x: adj[u.f]){
			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];
vl sums;
 
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);

 
	queue<int> q;
	ll val1 = 0;
	ll val2 = 0;
	for(auto u: adj[cen]){
		q.push(best_down[u.f].s);
		ckmax(val2, best_down[u.f].f+par[u.f].s);
		if(val1 < val2){
			swap(val1, val2);
		}
	}
 
	for(auto &u: cen_nodes){
		taken[u] = 0;
	}
	taken[cen] = 1;
 
	sums.clear();

	while(sz(q)){
		int take_node = q.front();
		q.pop();
 
		//cout << "take_node: " << i << " " << take_node << "\n";
		ll sum = 0;
		while(true){
			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(taken[u.f] || u.f == par[take_node].f) continue;
				q.push(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;
		}
		sums.pb(sum);
	}


	sort(sums.rbegin(), sums.rend());
	// cout << "sums: ";
	// for(auto u: sums){
	// 	cout << u << " ";
	// }
	// cout << "\n";

	//cout << "vals: " << val1 << " " << val2 << "\n";

	ll cur_sum = 0;
	for(int i = 1; i <= sz(cen_nodes); i++){
		if(i-1 >= sz(sums)){
			ckmax(ans[i], cur_sum+offset+sum_up[cen]);
			continue;
		}
		cur_sum+=sums[i-1];

		if(i == 1) continue;

		if(sums[i-1] > val2){
			//cout << i+1 << " " << cur_sum+val2+offset+sum_up[cen] << "\n";
			ckmax(ans[i+1], cur_sum+val2+offset+sum_up[cen]);
		}
		else{
			ckmax(ans[i], cur_sum+offset+sum_up[cen]);
		}
	}

 
	//recurse
	for(auto u: adj[cen]){
		ll new_offset = offset+sum_up[cen]-sum_up[u.f]+u.s;
		vector<pair<int, ll>> v;
		for(auto x: adj[u.f]){
			if(x.f == cen){
				new_offset-=x.s;
				continue;
			}
			v.pb(x);
		}
		adj[u.f] = v;
		genAns(u.f, new_offset);
	}
}
 
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 5 ms 5100 KB Output is correct
6 Correct 5 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5248 KB Output is correct
2 Correct 1129 ms 31992 KB Output is correct
3 Correct 1488 ms 41852 KB Output is correct
4 Correct 1071 ms 32032 KB Output is correct
5 Correct 598 ms 32144 KB Output is correct
6 Correct 1318 ms 33668 KB Output is correct
7 Correct 589 ms 32988 KB Output is correct
8 Correct 1533 ms 42172 KB Output is correct
9 Correct 460 ms 34804 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 1212 ms 31924 KB Output is correct
3 Correct 1499 ms 43360 KB Output is correct
4 Correct 1218 ms 31900 KB Output is correct
5 Correct 586 ms 32064 KB Output is correct
6 Correct 1357 ms 33816 KB Output is correct
7 Correct 489 ms 34656 KB Output is correct
8 Correct 1459 ms 39136 KB Output is correct
9 Correct 450 ms 34772 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 5 ms 5100 KB Output is correct
6 Correct 5 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 14 ms 5484 KB Output is correct
14 Correct 14 ms 5484 KB Output is correct
15 Correct 13 ms 5356 KB Output is correct
16 Correct 13 ms 5356 KB Output is correct
17 Correct 13 ms 5356 KB Output is correct
18 Correct 17 ms 5356 KB Output is correct
19 Correct 15 ms 5356 KB Output is correct
20 Correct 13 ms 5356 KB Output is correct
21 Correct 14 ms 5356 KB Output is correct
22 Correct 14 ms 5356 KB Output is correct
23 Correct 13 ms 5356 KB Output is correct
24 Correct 13 ms 5356 KB Output is correct
25 Correct 14 ms 5484 KB Output is correct
26 Correct 12 ms 5356 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5248 KB Output is correct
2 Correct 1129 ms 31992 KB Output is correct
3 Correct 1488 ms 41852 KB Output is correct
4 Correct 1071 ms 32032 KB Output is correct
5 Correct 598 ms 32144 KB Output is correct
6 Correct 1318 ms 33668 KB Output is correct
7 Correct 589 ms 32988 KB Output is correct
8 Correct 1533 ms 42172 KB Output is correct
9 Correct 460 ms 34804 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 1212 ms 31924 KB Output is correct
12 Correct 1499 ms 43360 KB Output is correct
13 Correct 1218 ms 31900 KB Output is correct
14 Correct 586 ms 32064 KB Output is correct
15 Correct 1357 ms 33816 KB Output is correct
16 Correct 489 ms 34656 KB Output is correct
17 Correct 1459 ms 39136 KB Output is correct
18 Correct 450 ms 34772 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 1094 ms 32056 KB Output is correct
21 Correct 1427 ms 43492 KB Output is correct
22 Correct 1078 ms 32228 KB Output is correct
23 Correct 1130 ms 32236 KB Output is correct
24 Correct 1071 ms 32428 KB Output is correct
25 Correct 1113 ms 32412 KB Output is correct
26 Correct 1080 ms 32440 KB Output is correct
27 Correct 589 ms 32260 KB Output is correct
28 Correct 1309 ms 33908 KB Output is correct
29 Correct 1065 ms 32568 KB Output is correct
30 Correct 969 ms 32096 KB Output is correct
31 Correct 542 ms 34460 KB Output is correct
32 Correct 1465 ms 39728 KB Output is correct
33 Correct 492 ms 34928 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 5 ms 5100 KB Output is correct
6 Correct 5 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 5248 KB Output is correct
13 Correct 1129 ms 31992 KB Output is correct
14 Correct 1488 ms 41852 KB Output is correct
15 Correct 1071 ms 32032 KB Output is correct
16 Correct 598 ms 32144 KB Output is correct
17 Correct 1318 ms 33668 KB Output is correct
18 Correct 589 ms 32988 KB Output is correct
19 Correct 1533 ms 42172 KB Output is correct
20 Correct 460 ms 34804 KB Output is correct
21 Correct 4 ms 5100 KB Output is correct
22 Correct 1212 ms 31924 KB Output is correct
23 Correct 1499 ms 43360 KB Output is correct
24 Correct 1218 ms 31900 KB Output is correct
25 Correct 586 ms 32064 KB Output is correct
26 Correct 1357 ms 33816 KB Output is correct
27 Correct 489 ms 34656 KB Output is correct
28 Correct 1459 ms 39136 KB Output is correct
29 Correct 450 ms 34772 KB Output is correct
30 Correct 4 ms 5100 KB Output is correct
31 Correct 14 ms 5484 KB Output is correct
32 Correct 14 ms 5484 KB Output is correct
33 Correct 13 ms 5356 KB Output is correct
34 Correct 13 ms 5356 KB Output is correct
35 Correct 13 ms 5356 KB Output is correct
36 Correct 17 ms 5356 KB Output is correct
37 Correct 15 ms 5356 KB Output is correct
38 Correct 13 ms 5356 KB Output is correct
39 Correct 14 ms 5356 KB Output is correct
40 Correct 14 ms 5356 KB Output is correct
41 Correct 13 ms 5356 KB Output is correct
42 Correct 13 ms 5356 KB Output is correct
43 Correct 14 ms 5484 KB Output is correct
44 Correct 12 ms 5356 KB Output is correct
45 Correct 4 ms 5100 KB Output is correct
46 Correct 1094 ms 32056 KB Output is correct
47 Correct 1427 ms 43492 KB Output is correct
48 Correct 1078 ms 32228 KB Output is correct
49 Correct 1130 ms 32236 KB Output is correct
50 Correct 1071 ms 32428 KB Output is correct
51 Correct 1113 ms 32412 KB Output is correct
52 Correct 1080 ms 32440 KB Output is correct
53 Correct 589 ms 32260 KB Output is correct
54 Correct 1309 ms 33908 KB Output is correct
55 Correct 1065 ms 32568 KB Output is correct
56 Correct 969 ms 32096 KB Output is correct
57 Correct 542 ms 34460 KB Output is correct
58 Correct 1465 ms 39728 KB Output is correct
59 Correct 492 ms 34928 KB Output is correct
60 Correct 4 ms 5100 KB Output is correct
61 Correct 1688 ms 34548 KB Output is correct
62 Execution timed out 2035 ms 43036 KB Time limit exceeded
63 Halted 0 ms 0 KB -