oj.uz

Submission #966660

# Submission time Handle Problem Language Result Execution time Memory
966660 2024-04-20T07:51:27 Z biximo Designated Cities (JOI19_designated_cities) C++17
16 / 100
 1206 ms 46432 KB 
#include <bits/stdc++.h>
#define N 200005
#define INF 1000000000000000000LL
using namespace std;
typedef long long ll;
bool vs[N];
struct P {
	int to, cto, cfr;
};
vector<P> adj[N];
int tree_sz[N];
void sz_DFS(int c, int pr) {
	tree_sz[c] = 1;
	for(auto&i: adj[c]) {
		if(vs[i.to] || i.to == pr) continue;
		sz_DFS(i.to, c);
		tree_sz[c] += tree_sz[i.to];
	}
}
int find_cent(int c, int pr, int sz) {
	for(auto&i: adj[c]) {
		if(i.to == pr || vs[i.to] || tree_sz[i.to]*2 < sz) continue;
		 return find_cent(i.to, c, sz);
	}
	return c;
}
vector<ll> vals[N];
priority_queue<ll> pq1, pq2;
ll initVal, ans[N];
ll update_DFS(int c, int pr) {
	ll sum = 0;
	vals[c].clear();
	for(auto&i: adj[c]) {
		if(i.to == pr || vs[i.to]) continue;
		sum += i.cfr;
		sum += update_DFS(i.to, c);
		vals[c].push_back(vals[i.to].back()+i.cfr);
	}
	if(vals[c].empty()) vals[c].push_back(0);
	sort(vals[c].begin(),vals[c].end());
	for(ll i: vals[c]) pq1.push(i);
	if(pr == -1) {
		if(vals[c].size() < 2) {
			initVal = -INF;
			pq2 = priority_queue<ll>();
		} else {
			initVal = vals[c].back(); vals[c].pop_back();
			initVal += vals[c].back(); vals[c].pop_back();
			for(ll i: vals[c]) pq2.push(i);
		}
	} else {
		for(ll i: vals[c]) pq2.push(i);
	}
	return sum;
}
ll getSum(int c, int pr) {
	ll sum = 0;
	for(auto&i: adj[c]) {
		if(vs[i.to] || i.to == pr) continue;
		sum += i.cfr + getSum(i.to, c);
	}
	return sum;
}
vector<ll> updateVals(int rt, ll cum) {
	ll sum = update_DFS(rt, -1);
	ans[2] = min(ans[2], cum+sum-initVal);
	for(int i = 3; pq2.size(); i ++, pq2.pop()) {
		initVal += pq2.top();
		ans[i] = min(ans[i], cum+sum-initVal);
	}
	ans[1] = min(ans[1], cum+sum);
	initVal = 0;
	for(int i = 2; pq1.size(); i ++, pq1.pop()) {
		initVal += pq1.top();
		ans[i] = min(ans[i],cum+sum-initVal);
	}
	vector<ll> cs;
	for(auto&i: adj[rt]) {
		if(vs[i.to]) continue;
		cs.push_back(getSum(i.to,rt)+i.cfr);
	}
	return cs;
}
void DNC(int c, ll cum) {
	sz_DFS(c, -1);
	int cent = find_cent(c, -1, tree_sz[c]);
	vector<ll> sms = updateVals(cent, cum);
	for(ll i: sms) cum += i;
	auto it = sms.begin();
	vs[cent] = 1;
	for(auto&i: adj[cent]) {
		if(vs[i.to]) continue;
		DNC(i.to, cum - (*it) + i.cto);
		it ++;
	}
}
int n, q;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; i ++) {
    	int a, b, csf, cst;
    	cin >> a >> b >> csf >> cst;
    	swap(csf, cst);
    	adj[a].push_back({b, csf, cst});
    	adj[b].push_back({a, cst, csf});
    }
    for(auto&i: ans) i = INF;
    DNC(1, 0);
	for(int i = 2; i <= n; i ++) {
		ans[i] = min(ans[i], ans[i-1]);
	}
	cin >> q;
	while(q--) {
		int i;
		cin >> i;
		cout << ans[i] << "\n";
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Incorrect 3 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 910 ms 39172 KB Output is correct
3 Correct 1152 ms 45484 KB Output is correct
4 Correct 865 ms 39520 KB Output is correct
5 Correct 365 ms 40928 KB Output is correct
6 Correct 1129 ms 43436 KB Output is correct
7 Correct 271 ms 43168 KB Output is correct
8 Correct 1138 ms 45480 KB Output is correct
9 Correct 203 ms 45808 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 956 ms 43068 KB Output is correct
3 Correct 1187 ms 46432 KB Output is correct
4 Correct 861 ms 39460 KB Output is correct
5 Correct 321 ms 41716 KB Output is correct
6 Correct 1115 ms 42768 KB Output is correct
7 Correct 204 ms 45400 KB Output is correct
8 Correct 1206 ms 44112 KB Output is correct
9 Correct 209 ms 45828 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Incorrect 3 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 910 ms 39172 KB Output is correct
3 Correct 1152 ms 45484 KB Output is correct
4 Correct 865 ms 39520 KB Output is correct
5 Correct 365 ms 40928 KB Output is correct
6 Correct 1129 ms 43436 KB Output is correct
7 Correct 271 ms 43168 KB Output is correct
8 Correct 1138 ms 45480 KB Output is correct
9 Correct 203 ms 45808 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 956 ms 43068 KB Output is correct
12 Correct 1187 ms 46432 KB Output is correct
13 Correct 861 ms 39460 KB Output is correct
14 Correct 321 ms 41716 KB Output is correct
15 Correct 1115 ms 42768 KB Output is correct
16 Correct 204 ms 45400 KB Output is correct
17 Correct 1206 ms 44112 KB Output is correct
18 Correct 209 ms 45828 KB Output is correct
19 Correct 4 ms 12040 KB Output is correct
20 Incorrect 871 ms 40952 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 12124 KB Output is correct
2 Incorrect 3 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -