Submission #996589

#	Time	Username	Problem	Language	Result	Execution time	Memory
996589		NintsiChkhaidze	Designated Cities (JOI19_designated_cities)	C++17	23 / 100	2082 ms	42840 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;
pii t[4*N];
int lz[4*N],tin[N],tout[N],timer,rev[N];
pii parent[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]);
}
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n;
	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});
	}

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

	for (int i = 1; i <= n; i++){
		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: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44