제출 #1257458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257458		nguyn	Two Currencies (JOI23_currencies)	C++20	0 / 100	4 ms	6156 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 1e5 + 5;

struct BIT {
	int n; 	
	vector<ll> bit; 
	
	BIT() {}
	
	BIT(int _n) : n(_n) {
		bit.assign(n + 3, 0); 
	}
	
	void update(int id, ll val) {
		for (int i = id; i <= n; i += (i & -i)) bit[i] += val; 
	}
	
	ll get(int id) {
		ll ret = 0; 
		for (int i = id; i > 0; i -= (i & -i)) ret += bit[i]; 
		return ret; 
	} 
	
	ll get(int u, int v) {
		return get(v) - get(u - 1); 
	}
} sum, cnt;

struct Query {
	int u, v, x; ll y; 
} que[N];

int n, m, q; 
vector<int> g[N];
int tin[N], tout[N]; 
pii edges[N];
int res[N];
int l[N], r[N];  
int timedfs = 0;
vector<int> ev[N]; 
vector<pair<ll, int>> vec;  
int anc[N], up[N][17], h[N]; 



void pre_dfs(int u, int p) {
	tin[u] = ++timedfs;
	for (int v : g[u]) {
		if (v == p) continue;
		up[v][0] = u; 
		h[v] = h[u] + 1;
		for (int i = 1; i < 17; i++) {
			up[v][i] = up[up[v][i - 1]][i - 1]; 
		}
		pre_dfs(v, u); 
	}
	tout[u] = ++timedfs;
}

int lca(int u, int v) {
	if (h[u] != h[v]) {
		if (h[u] < h[v]) swap(u, v); 
		int k = h[u] - h[v]; 
		for (int i = 0; (1 << i) <= k; i++) {
			if (k >> i & 1) u = up[u][i];
		}
	}
	if (u == v) return u; 
	for (int i = 16; i >= 0; i--) {
		if (up[u][i] != up[v][i]) {
			u = up[u][i];
			v = up[v][i];
		}
	}
	return up[u][0];
}


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int u, v; 
		cin >> u >> v; 
		g[u].pb(v);
		g[v].pb(u);
		edges[i] = {u, v}; 
	}
	pre_dfs(1, 0); 
	for (int i = 1; i <= m; i++) {
		int p, c;
		int u, v;
		cin >> p >> c;
		tie(u, v) = edges[p];  
		if (v == up[u][0]) swap(u, v);
		vec.pb({c, v}); 	 
	}
	for (int i = 1; i <= q; i++) {
		int u, v, x, y;
		cin >> u >> v >> x >> y; 
		que[i] = {u, v, x, y};
		anc[i] = lca(u, v); 
		l[i] = 0; 
		r[i] = vec.size() - 1; 
	} 
	sort(vec.begin(), vec.end());
	while(1) {
		bool ok = 0;
		for (int i = 1; i <= q; i++) {
			if (l[i] <= r[i]) {
				int mid = (l[i] + r[i]) / 2; 
				ok = 1;
				ev[mid].pb(i);  
			}
		}
		if (!ok) break;
		sum = BIT(2 * n);
		cnt = BIT(2 * n); 
		for (int i = 0; i < vec.size(); i++) {
			cnt.update(tin[vec[i].S], 1); 
			cnt.update(tout[vec[i].S], - 1); 
			sum.update(tin[vec[i].S], vec[i].F); 
			sum.update(tout[vec[i].S], - vec[i].F); 
			
			for (int id : ev[i]) {
				ll tmp = sum.get(tin[anc[id]] + 1, tin[que[id].u]) + sum.get(tin[anc[id]] + 1, tin[que[id].v]);
				if (tmp <= que[id].y) {
					res[id] = cnt.get(tin[anc[id]] + 1, tin[que[id].u]) + cnt.get(tin[anc[id]] + 1, tin[que[id].v]);
					l[id] = i + 1;  
				}
				else {
					r[id] = i - 1; 
				}
			}
			ev[i].clear(); 
		}
	}
	cnt = BIT(2 * n); 
	for (int i = 0; i < vec.size(); i++) {
		cnt.update(tin[vec[i].S], 1); 
		cnt.update(tout[vec[i].S], -1); 
	}
	for (int i = 1; i <= q; i++) {
		int c = cnt.get(tin[anc[i]] + 1, tin[que[i].u]) + cnt.get(tin[anc[i]] + 1, tin[que[i].v]);
//		cout << c << ' ' << res[i] << ' ' << que[i].x << ' '; 
		c -= res[i]; 
		cout << max(-1, que[i].x - c) << '\n'; 
	}
} 

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32