oj.uz

Submission #996589

# Submission time Handle Problem Language Result Execution time Memory
996589 2024-06-10T21:14:59 Z NintsiChkhaidze Designated Cities (JOI19_designated_cities) C++17
23 / 100
 2000 ms 42840 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 3 ms 18288 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 2 ms 18268 KB Output is correct
6 Correct 2 ms 18268 KB Output is correct
7 Correct 3 ms 18268 KB Output is correct
8 Correct 3 ms 18308 KB Output is correct
9 Correct 3 ms 18268 KB Output is correct
10 Correct 3 ms 18284 KB Output is correct
11 Correct 3 ms 18264 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18268 KB Output is correct
2 Execution timed out 2041 ms 42840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Execution timed out 2082 ms 42776 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 3 ms 18288 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 2 ms 18268 KB Output is correct
6 Correct 2 ms 18268 KB Output is correct
7 Correct 3 ms 18268 KB Output is correct
8 Correct 3 ms 18308 KB Output is correct
9 Correct 3 ms 18268 KB Output is correct
10 Correct 3 ms 18284 KB Output is correct
11 Correct 3 ms 18264 KB Output is correct
12 Correct 3 ms 18264 KB Output is correct
13 Correct 798 ms 18480 KB Output is correct
14 Correct 632 ms 18524 KB Output is correct
15 Correct 784 ms 18468 KB Output is correct
16 Correct 787 ms 18264 KB Output is correct
17 Correct 800 ms 18268 KB Output is correct
18 Correct 836 ms 18500 KB Output is correct
19 Correct 792 ms 18472 KB Output is correct
20 Correct 759 ms 18484 KB Output is correct
21 Correct 797 ms 18496 KB Output is correct
22 Correct 782 ms 18496 KB Output is correct
23 Correct 762 ms 18492 KB Output is correct
24 Correct 634 ms 18488 KB Output is correct
25 Correct 713 ms 18548 KB Output is correct
26 Correct 610 ms 18476 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18268 KB Output is correct
2 Execution timed out 2041 ms 42840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 3 ms 18288 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 2 ms 18268 KB Output is correct
6 Correct 2 ms 18268 KB Output is correct
7 Correct 3 ms 18268 KB Output is correct
8 Correct 3 ms 18308 KB Output is correct
9 Correct 3 ms 18268 KB Output is correct
10 Correct 3 ms 18284 KB Output is correct
11 Correct 3 ms 18264 KB Output is correct
12 Correct 2 ms 18268 KB Output is correct
13 Execution timed out 2041 ms 42840 KB Time limit exceeded
14 Halted 0 ms 0 KB -