oj.uz

Submission #937694

# Submission time Handle Problem Language Result Execution time Memory
937694 2024-03-04T11:11:09 Z WonderfulWhale Designated Cities (JOI19_designated_cities) C++17
7 / 100
 445 ms 68260 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;

void dfs(int x, int p=-1) {
	tin[x] = ++T;
	for(auto [y, c]:G[x]) {
		if(y==p) 
			continue;
		dfs(y, x);
	}
	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);
	}
}

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);
	ans[1] = seg.query(1, 2*n);
	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 Incorrect 4 ms 16728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 360 ms 35640 KB Output is correct
3 Correct 445 ms 67496 KB Output is correct
4 Correct 332 ms 40488 KB Output is correct
5 Correct 344 ms 41676 KB Output is correct
6 Correct 343 ms 45680 KB Output is correct
7 Correct 321 ms 41260 KB Output is correct
8 Correct 441 ms 68260 KB Output is correct
9 Correct 284 ms 39928 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 16728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 360 ms 35640 KB Output is correct
3 Correct 445 ms 67496 KB Output is correct
4 Correct 332 ms 40488 KB Output is correct
5 Correct 344 ms 41676 KB Output is correct
6 Correct 343 ms 45680 KB Output is correct
7 Correct 321 ms 41260 KB Output is correct
8 Correct 441 ms 68260 KB Output is correct
9 Correct 284 ms 39928 KB Output is correct
10 Incorrect 3 ms 16732 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 16728 KB Output isn't correct
2 Halted 0 ms 0 KB -