답안 #653848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653848	2022-10-28T12:54:19 Z	dooompy	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	629 ms	59232 KB

designated_cities

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
constexpr int N = 2e5 + 10;
 
int n;
ll total;
ll ps[N], cnt[N], par[N], up[N];
int st[N], fn[N], id[N], tim;
ll 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 {
	ll 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);
	for(int i = 1; i <= n; i++) ans[1] = min(ans[1], up[i] - ps[i]);

	int root = max_element(ps + 1, ps + n + 1) - ps;
 
	ps[root] = up[root] = 0;
	preDFS(root);
	DFS(root);
	mark[root] = 1;
 
	
	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	11 ms	23788 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	23800 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	23764 KB	Output is correct
2	Correct	604 ms	41600 KB	Output is correct
3	Correct	555 ms	59232 KB	Output is correct
4	Correct	532 ms	46348 KB	Output is correct
5	Correct	547 ms	47956 KB	Output is correct
6	Correct	578 ms	49880 KB	Output is correct
7	Correct	467 ms	48168 KB	Output is correct
8	Correct	629 ms	55388 KB	Output is correct
9	Correct	478 ms	48080 KB	Output is correct