oj.uz

Submission #966681

# Submission time Handle Problem Language Result Execution time Memory
966681 2024-04-20T08:14:01 Z biximo Designated Cities (JOI19_designated_cities) C++17
7 / 100
 824 ms 42324 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(int i = 0; i < vals[c].size()-1; i ++) {
		pq1.push(vals[c][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(int i = 0; i < vals[c].size()-1; i ++) {
			pq2.push(vals[c][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";
	}
}

Compilation message

designated_cities.cpp: In function 'll update_DFS(int, int)':
designated_cities.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < vals[c].size()-1; i ++) {
      |                 ~~^~~~~~~~~~~~~~~~~~
designated_cities.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i = 0; i < vals[c].size()-1; i ++) {
      |                  ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 691 ms 35292 KB Output is correct
3 Correct 824 ms 42324 KB Output is correct
4 Correct 680 ms 34000 KB Output is correct
5 Correct 285 ms 35696 KB Output is correct
6 Correct 779 ms 36600 KB Output is correct
7 Correct 228 ms 37484 KB Output is correct
8 Correct 775 ms 42196 KB Output is correct
9 Correct 204 ms 41860 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 691 ms 35292 KB Output is correct
3 Correct 824 ms 42324 KB Output is correct
4 Correct 680 ms 34000 KB Output is correct
5 Correct 285 ms 35696 KB Output is correct
6 Correct 779 ms 36600 KB Output is correct
7 Correct 228 ms 37484 KB Output is correct
8 Correct 775 ms 42196 KB Output is correct
9 Correct 204 ms 41860 KB Output is correct
10 Incorrect 3 ms 12124 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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