Submission #996593

#	Time	Username	Problem	Language	Result	Execution time	Memory
996593		NintsiChkhaidze	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	867 ms	122436 KiB

designated_cities

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 2e5 + 3,inf = 1e18;
vector <pii> v[N];
int dp[N],ans[N],tot,n;
pii t[4*N];
int lz[4*N],tin[N],tout[N],timer,rev[N],A,B;
pii parent[N];
unordered_map <int,pii> mp[N];

void dfs1(int x,int par,int D){
	tin[x] = ++timer;
	rev[timer] = x;
	dp[x] = D;
	for (auto [to,w]: v[x]){
		if (to == par) continue;
		tot += w;
		parent[to] = {x,w};
		dfs1(to,x,w + D);
	}
	tout[x] = timer;
}

void build(int h,int l,int r){
	lz[h] = 0;
	if (l == r){
		t[h] = {dp[rev[l]],rev[l]};
		return;
	}
	build(left);
	build(right);
	t[h] = max(t[h*2],t[h*2+1]);
}

void push(int h){
	if (lz[h] == 0) return;
	lz[h*2] += lz[h];
	lz[h*2 + 1] += lz[h];
	t[h*2].f += lz[h];
	t[h*2 + 1].f += lz[h];
	lz[h] = 0;
}

void upd(int h,int l,int r,int L,int R,int val){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t[h].f += val;
		lz[h] += val;
		return;
	}

	push(h);
	upd(left,L,R,val);
	upd(right,L,R,val);
	t[h] = max(t[h*2],t[h*2+1]);
}

void reroot(int x,int par,int total){

	ans[1] = min(ans[1],total);
	int y = t[1].s,val = t[1].f;
	if (total - val < ans[2]) {
		ans[2] = total - val;
		A = x,B = y;
	}

	for (auto [to,w]: v[x]){
		if (to == par) continue;
		int w2 = mp[x][to].f;
		if (mp[x][to].f == w) w2 = mp[x][to].s;

		upd(1,1,n,tin[to],tout[to],-w);
		upd(1,1,n,1,tin[to] - 1,+w2);
		upd(1,1,n,tout[to] + 1,n,+w2);
		total += w2 - w;

		reroot(to,x,total);

		upd(1,1,n,tin[to],tout[to],+w);
		upd(1,1,n,1,tin[to] - 1,-w2);
		upd(1,1,n,tout[to] + 1,n,-w2);
		total -= w2 - w;
	}
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	cin>>n;

	for (int i = 1; i < n; i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		v[a].pb({b,c});
		v[b].pb({a,d});
		mp[a][b] = mp[b][a] = {c,d};
	}

	for (int i = 1; i <= n; i++)
		ans[i] = inf;

	timer=tot=0;
	dfs1(1,1,0);
	build(1,1,n);
	reroot(1,1,tot);

	for (int i = 1; i <= n; i++){
		if (i != A && i != B) continue;
		tot = timer = 0;
		parent[i] = {0,0};
		dfs1(i,i,0);
		build(1,1,n);
		ans[1] = min(ans[1],tot);

		for (int j = 2; j <= n; j++){
			int val = t[1].f,x = t[1].s;
			tot -= val;
			ans[j] = min(ans[j],tot);
			
			while (val > 0){
				upd(1,1,n,tin[x],tout[x],-parent[x].s);
				val -= parent[x].s;
				x = parent[x].f;
			}
		}
	}

	int q;
	cin>>q;
	while (q--){
		int x;
		cin>>x;
		cout<<ans[x]<<"\n";
	}
}

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