oj.uz

Submission #937715

# Submission time Handle Problem Language Result Execution time Memory
937715 2024-03-04T11:50:49 Z WonderfulWhale Designated Cities (JOI19_designated_cities) C++17
16 / 100
 463 ms 76568 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Incorrect 3 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 379 ms 40604 KB Output is correct
3 Correct 463 ms 65860 KB Output is correct
4 Correct 356 ms 40552 KB Output is correct
5 Correct 349 ms 40144 KB Output is correct
6 Correct 374 ms 44044 KB Output is correct
7 Correct 337 ms 39236 KB Output is correct
8 Correct 456 ms 66820 KB Output is correct
9 Correct 296 ms 36720 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 371 ms 46796 KB Output is correct
3 Correct 445 ms 76568 KB Output is correct
4 Correct 358 ms 45548 KB Output is correct
5 Correct 353 ms 46568 KB Output is correct
6 Correct 386 ms 51000 KB Output is correct
7 Correct 305 ms 46324 KB Output is correct
8 Correct 443 ms 63612 KB Output is correct
9 Correct 285 ms 43504 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Incorrect 3 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 379 ms 40604 KB Output is correct
3 Correct 463 ms 65860 KB Output is correct
4 Correct 356 ms 40552 KB Output is correct
5 Correct 349 ms 40144 KB Output is correct
6 Correct 374 ms 44044 KB Output is correct
7 Correct 337 ms 39236 KB Output is correct
8 Correct 456 ms 66820 KB Output is correct
9 Correct 296 ms 36720 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 371 ms 46796 KB Output is correct
12 Correct 445 ms 76568 KB Output is correct
13 Correct 358 ms 45548 KB Output is correct
14 Correct 353 ms 46568 KB Output is correct
15 Correct 386 ms 51000 KB Output is correct
16 Correct 305 ms 46324 KB Output is correct
17 Correct 443 ms 63612 KB Output is correct
18 Correct 285 ms 43504 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Incorrect 372 ms 47076 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Incorrect 3 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -