oj.uz

Submission #632943

# Submission time Handle Problem Language Result Execution time Memory
632943 2022-08-21T09:33:47 Z Arnch Designated Cities (JOI19_designated_cities) C++17
0 / 100
 427 ms 34456 KB 
#include<bits/stdc++.h>
using namespace std;

constexpr int N = 2e5 + 10;

int n;
int total;
int ps[N], cnt[N], par[N], up[N];
int st[N], fn[N], id[N], tim;
int ans[N];

bool mark[N];

vector<pair<int, int> > adj[N];

void preDFS(int x, int p = 0) {
	for(auto j : adj[x]) {
		if(j.first == p) {
			up[x] = up[p] + j.second;
			break;
		}
	}
	for(auto j : adj[x]) {
		if(j.first == p) {
			continue;
		}
		cnt[j.first] = j.second;
		ps[j.first] = ps[x] + j.second;
		preDFS(j.first, x);
	}
}
void DFS(int x, int p = 0) {
	id[tim] = x;
	st[x] = tim++;
	par[x] = p;
	for(auto j : adj[x]) {
		if(j.first == p) {
			continue;
		}
		total += j.second;
		DFS(j.first, x);
	}
	fn[x] = tim;
}

struct node {
	int cnt, id, lz;
	node() {
		cnt = id = lz = 0;
	}
} x[N << 2];

void build(int l = 0, int r = n, int v = 1) {
	if(r - l < 2) {
		x[v].cnt = ps[id[l]];
		x[v].id = id[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2 * v), build(mid, r, 2 * v + 1);

	x[v].cnt = max(x[2 * v].cnt, x[2 * v + 1].cnt);
	x[v].id = (x[v].cnt == x[2 * v].cnt)? (x[2 * v].id): (x[2 * v + 1].id);
}
void put(int l, int r, int v) {
	if(x[v].lz == 0) return;
	
	x[2 * v].cnt -= x[v].lz, x[2 * v + 1].cnt -= x[v].lz;
	x[2 * v].lz += x[v].lz, x[2 * v + 1].lz += x[v].lz;

	x[v].lz = 0;
}
void change(int s, int e, int val, int l = 0, int r = n, int v = 1) {
	if(r <= s || l >= e) return;
	if(l >= s && r <= e) {
		x[v].cnt -= val;
		x[v].lz += val;
		return;
	}
	put(l, r, v);
	int mid = (l + r) >> 1;
	change(s, e, val, l, mid, 2 * v), change(s, e, val, mid, r, 2 * v + 1);
	
	x[v].cnt = max(x[2 * v].cnt, x[2 * v + 1].cnt);
	x[v].id = (x[v].cnt == x[2 * v].cnt)? (x[2 * v].id): (x[2 * v + 1].id);
}

int main() {
	cin >>n;
	for(int i = 0; i < n - 1; i++) {
		int u, v, w, wp; cin >>u >>v >>w >>wp;
		adj[u].push_back({v, w}), adj[v].push_back({u, wp});
	}

	preDFS(1);
	
	int root = max_element(ps + 1, ps + n + 1) - ps;

	ps[root] = up[root] = 0;
	preDFS(root);
	DFS(root);
	mark[root] = 1;

	for(int i = 1; i <= n; i++) ans[1] = min(ans[1], up[i] - ps[i]);
	
	build();
	
	ans[1] += total;
	for(int i = 2; i <= n; i++) {
		int v = x[1].id;
		while(!mark[v]) {
			mark[v] = 1;
			total -= cnt[v];
			change(st[v], fn[v], cnt[v]);
			v = par[v];
		}
		ans[i] = total;
	}

	int q; cin >>q;
	for(int i = 0; i < q; i++) {
		int nu; cin >>nu;

		cout<<ans[nu] <<endl;
	}

}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 8 ms 14440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 426 ms 28048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 427 ms 34456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 8 ms 14440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 426 ms 28048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 8 ms 14440 KB Output isn't correct
3 Halted 0 ms 0 KB -