제출 #937715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937715		WonderfulWhale	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	463 ms	76568 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int MAXN = 200'009;
const int INF = 1e9;

struct SegTree {
		const static int T = 1<<19;
	int t[2*T], lz[2*T];
	void push(int v) {
		t[2*v] += lz[v];
		lz[2*v] += lz[v];
		t[2*v+1] += lz[v];
		lz[2*v+1] += lz[v];
		lz[v] = 0;
	}
	void update(int l, int r, int val, int tl=0, int tr=T-1, int v=1) {
		//if(v==1) cerr << l << " " << r << " " << val << "\n";
		if(l>r) return;
		if(l==tl&&r==tr) {
			//cerr << "adding: " << v << " " << val << "\n";
			t[v] += val;
			lz[v] += val;
			//cerr << "new: " << t[v] << "\n";
			return;
		}
		int tm = (tl+tr)/2;
		push(v);
		update(l, min(r, tm), val, tl, tm, 2*v);
		update(max(l, tm+1), r, val, tm+1, tr, 2*v+1);
		t[v] = max(t[2*v], t[2*v+1]);
	}
	int query(int l, int r, int tl=0, int tr=T-1, int v=1) {
		//cerr << "query: " << l <<  " " << r << " " << v << " "<<t[v] << "\n";
		if(l>r) return -INF;
		if(l==tl&&r==tr) return t[v];
		int tm = (tl+tr)/2;
		push(v);
		return max(query(l, min(r, tm), tl, tm, 2*v),
				query(max(l, tm+1), r, tm+1, tr, 2*v+1));
	}
} seg;

int n;
vector<pair<int, pii>> G[MAXN];
int tin[MAXN], tout[MAXN], T;
int sum[MAXN];

pii dp[MAXN];

void dfs(int x, int p=-1) {
	tin[x] = ++T;
	for(auto [y, c]:G[x]) {
		if(y==p) 
			continue;
		sum[x] += c.nd;
		dfs(y, x);
		sum[x] += sum[y];
	}
	tout[x] = ++T;
	for(auto [y, c]:G[x]) {
		if(y==p) continue;
		//cerr << "updates: " << x << " " << y << "\n";
		seg.update(tin[y], tout[y], c.st);
		seg.update(1, tin[y]-1, c.nd);
		seg.update(tout[y]+1, 2*n, c.nd);
	}
}

pair<int, pii> start;

void dfs2(int x, int p=-1, int s=0) {
	pii best[2];
	best[0] = {0, x};
	best[1].st = -INF;
	for(auto [y, c]:G[x]) {
		if(y==p) continue;
		dfs2(y, x, s+c.st+sum[x]-sum[y]-c.nd);
		int val = dp[y].st+c.st+c.nd-sum[y]-c.nd;
		if(val>=best[0].st) {
			best[1] = best[0];
			best[0] = {val, dp[y].nd};
		} else if(val>=best[1].st) {
			best[1] = {val, dp[y].nd};
		}
	}
	start = max(start, {best[0].st+best[1].st+s+sum[x], 
			{best[0].nd, best[1].nd}});
	dp[x] = {sum[x], x};
	for(auto [y, c]:G[x]) {
		if(y==p) continue;
		dp[x] = max(dp[x], 
				{dp[y].st+c.st+c.nd+sum[x]-sum[y]-c.nd, dp[y].nd});
	}
}

int ans[MAXN];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n;
	int S = 0;
	for(int i=0;i<n-1;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		S += c+d;
		G[a].pb({b, {c, d}});
		G[b].pb({a, {d, c}});
	}
	dfs(1);
	dfs2(1);
	ans[1] = seg.query(1, 2*n);
	ans[2] = start.st;
	int q;
	cin >> q;
	while(q--) {
		int x;
		cin >> x;
		cout << S-ans[x] << "\n";
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44