제출 #632943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632943		Arnch	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	427 ms	34456 KiB

designated_cities

#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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44