oj.uz

Submission #937687

# Submission time Handle Problem Language Result Execution time Memory
937687 2024-03-04T10:53:55 Z WonderfulWhale Designated Cities (JOI19_designated_cities) C++17
0 / 100
 4 ms 16732 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) {
			t[v] += val;
			lz[v] += val;
			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);
	}
	int query(int l, int r, int tl=0, int tr=T-1, int v=1) {
		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[x], c.nd);
		seg.update(tout[x], 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);
	return 0;
	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 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

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 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

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