Submission #937773

#	Time	Username	Problem	Language	Result	Execution time	Memory
937773		WonderfulWhale	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	1969 ms	62588 KiB

designated_cities

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

#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;
	pii t[2*T];
	int lz[2*T];
	void push(int v) {
		t[2*v].st += lz[v];
		lz[2*v] += lz[v];
		t[2*v+1].st += 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].st += 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]);
	}
	pii 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, -1};
		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, seg1, seg2;

int n;
vector<pair<int, pii>> G[MAXN];
int tin[MAXN], tout[MAXN], T;
int sum[MAXN];
int heavy[MAXN];
int head[MAXN];
int pos[MAXN], P;
int par[MAXN];
pii cost[MAXN];

pii dp[MAXN];

void dfs(int x, int p=-1) {
	par[x] = p;
	tin[x] = ++T;
	seg.t[tin[x]+seg.T].nd = x;
	seg.update(tin[x], tin[x], INF);
	for(auto [y, c]:G[x]) {
		if(y==p) 
			continue;
		cost[y] = c;
		sum[x] += c.nd;
		dfs(y, x);
		sum[x] += sum[y];
	}
	tout[x] = ++T;
	seg.t[tout[x]+seg.T].nd = x;
	seg.update(tout[x], tout[x], INF);
	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 dfs3(int x, int p=-1) {
	int s = 1;
	int max_s = 0;
	for(auto [y, c]:G[x]) {
		if(y==p) continue;
		int c_s = dfs3(y, x);
		s += c_s;
		if(c_s>max_s) {
			max_s = c_s;
			heavy[x] = y;
		}
	}
	return s;
}

void decompose(int x, int h, int p=-1) {
	head[x] = h;
	pos[x] = P++;
	if(heavy[x]!=0)
		decompose(heavy[x], h, x);
	for(auto [y, c]:G[x]) {
		if(y!=p&&y!=heavy[x])
			decompose(y, y, x);
	}
	//cerr << "hld: " << x << "->" << pos[x] << "\n";
}

int ans[MAXN];

void erase_e(int x, int type) {
	//cerr << "erasing edge: " << x << " " << type << "\n";
	if(type==0) {
		seg.update(1, tin[x]-1, -cost[x].nd);
		seg.update(tout[x]+1, 2*n, -cost[x].nd);
		seg1.update(pos[x], pos[x], -INF);
	}
	if(type==1) {
		seg.update(tin[x], tout[x], -cost[x].st);
		seg2.update(pos[x], pos[x], -INF);
	}
}

void erase_v(int x) {
	//cerr << "erasing v: " << x << "\n";
	seg.update(tin[x], tin[x], -INF);
	seg.update(tout[x], tout[x], -INF);
	vector<pii> segments;
	int cur = x;
	while(cur!=-1) {
		segments.pb({pos[head[cur]], pos[cur]});
		cur = par[head[cur]];
	}
	reverse(all(segments));
	for(pii x:segments) {
		//cerr << x.st << " " << x.nd << "\n";
	}
	int pre = 0;
	for(pii x:segments) {
		pii y = seg1.query(pre, x.st-1);
		//cerr << "querying: "<< pre << " " << x.st-1 << "\n";
		while(y.st>0) {
			erase_e(y.nd, 0);
			y = seg1.query(pre, x.st-1);
		}
		pre = x.nd+1;
	}
	pii Y = seg1.query(pre, n);
	while(Y.st>0) {
		erase_e(Y.nd, 0);
		Y = seg1.query(pre, n);
	}
	for(pii x:segments) {
		pii y = seg2.query(x.st, x.nd);
		while(y.st>0) {
			erase_e(y.nd, 1);
			y = seg2.query(x.st, x.nd);
		}
	}
}

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

	for(int i=0;i<2*seg.T;i++) {
		seg.t[i].st = -INF;
	}

	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);
	dfs3(1);
	decompose(1, 1);
	for(int i=2;i<=n;i++) {
		seg1.t[pos[i]+seg1.T].nd = i;
		seg1.update(pos[i], pos[i], cost[i].nd);
		seg2.t[pos[i]+seg2.T].nd = i;
		seg2.update(pos[i], pos[i], cost[i].nd);
	}
	//cerr << "cos: " << tin[2] << "\n";
	ans[1] = seg.query(1, 2*n).st;
	ans[2] = start.st;
	erase_v(start.nd.st);
	erase_v(start.nd.nd);
	for(int i=3;i<=n;i++) {
		//cerr << seg.query(tin[2], tin[2]).st << " xd\n";
		//cerr << seg.query(tin[0], tin[0]).st << " xd\n";
		pii x = seg.query(1, 2*n);
		//cerr << "New year, new me " << x.nd << "\n";
		//cerr << "with some weird value: " << x.st << "\n";
		ans[i] = ans[i-1] + x.st;
		erase_v(x.nd);
	}
	int q;
	cin >> q;
	while(q--) {
		int x;
		cin >> x;
		cout << S-ans[x] << "\n";
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'void erase_v(int)':
designated_cities.cpp:169:10: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  169 |  for(pii x:segments) {
      |          ^

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