oj.uz

Submission #888774

# Submission time Handle Problem Language Result Execution time Memory
888774 2023-12-18T07:42:22 Z vjudge1 Two Currencies (JOI23_currencies) C++17
38 / 100
 2614 ms 120624 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 998244353;
const int N = 1e5;
int n, m, q;
vector<int > g[N+10];
vector< pair<int, int> > check, edge;
int depth[N+10], sub[N+10];
int up[N+10][18], sum[N+10][18];
int tin[N+10], tout[N+10];
vector<int> val[N+10];
int bigchild[N+10], pos[N+10], chain[N+10];
int timer = 1;
void dfs(int v, int par){
	tin[v] = timer++;
	up[v][0] = par;
	for(int to : g[v]){
		if(to == par) continue;
		depth[to] = depth[v] + 1;
		dfs(to, v);
		sub[v]+= sub[to];
		if(!bigchild[v] or sub[bigchild[v]] < sub[to]){
			bigchild[v] = to;
		}
	}
	sub[v] += 1, tout[v] = timer++;
}


int upper(int p, int a){
	return (tin[p] <= tin[a] && tout[p] >= tout[a]);
}


int lca(int a, int b){
	if(depth[b] < depth[a]) swap(a, b);
	int k = depth[b] - depth[a];
	for(int i = 0;i < 18; i++){
		if(k & (1<<i)) b = up[b][i];
	}
	if(a == b) return a;
	for(int i = 17; i >= 0; i--){
		if(up[b][i] != up[a][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
	
}

void dfs2(int v, int par, int head){
	pos[v] = timer++;
	chain[v] = head;
	if(bigchild[v]){
		dfs2(bigchild[v], v, head);
	}
	for(int to : g[v]){
			if(to == par || to == bigchild[v]) continue;
			dfs2(to, v, to);
	}
}



/*
int query(int a, int b){
	if(chain[a] > chain[b]) swap(a, b);
	int sum = 0;
	while(chain[a] != chain[b]){
			if(chain[a] > chain[b]) swap(a, b);
			int l =pos[chain[b]], r = pos[b];
			//sum+= get(l, r, 1, 1, n);
			b = up[chain[b]][0];
	}
	if(chain[a] > chain[b]) swap(a, b);
	int l = pos[a], r = pos[b];
	//sum+= get(l, r, 1, 1, n);
	return sum; 
}
*/
int distance(int a, int b){
	int lc = lca(a, b);
	return (depth[a] + depth[b] - 2*depth[lc]);
}
int checks(int a, int d){
	int cnt = 0;
	for(int i = 0;i < 17; i++){
		if(d & (1<<i)){
			cnt+= sum[a][i];
			a = up[a][i];
		}
	}
	return cnt;
}

int go_k(int a, int d){
	for(int i = 0;i < 17; i++){
		if(d & (1<<i)) a = up[a][i];
	}
	return a;
	
}

struct node{
	vector<int> a, pr;
};


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	int bambo = 1;
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		if(a != i or b != a+1) bambo = 0;
		edge.push_back({a, b});
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(1, 1);
	timer = 1;
	dfs2(1, 1, 1);
	int coins = 0;
	for(int i = 0;i < m; i++){
		int p, c; cin >> p >> c;
		check.push_back({p, c});
		int a = edge[p-1].ff, b = edge[p-1].ss;
		if(depth[a] < depth[b]) swap(a, b);
		//cout << a << " , " << b << " = " << c << '\n';
		sum[a][0] += 1;
		val[a].push_back(c);
		coins = c;
	}
	for(int j = 1;j < 18; j++){
		for(int i = 1;i <= n; i++){
			up[i][j] = up[up[i][j-1]][j-1];
			sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
		}
	}
	if(max({n, m, q}) <= 2000){
		while(q--){
			int s, t; cin >> s >> t;
			int x, y; cin >> x >> y;
			int lc = lca(s, t);
			vector<pair<int, int> > vec;
			int cnt = checks(s, depth[s] - depth[lc]);
			cnt+= checks(t, depth[t] - depth[lc]);
			while(s != lc){
				for(int sa : val[s]) vec.push_back({sa, 1});
				s = up[s][0];
			}
			while(t != lc){
				for(int sa : val[t]) vec.push_back({sa, 1});
				t = up[t][0];
			}
			//cout << "ancestor : ";
			//cout << lc << "\n";
			sort(all(vec), [&](auto A, auto B){
				return A.ff < B.ff;
			});
			
			for(auto [silver, gold] : vec){
			//	cout << silver << ' ' << gold << ", ";
				if(y >= silver){
					y-= silver;
				}else{
					x-= gold;
				}
			}
			//cout << '\n';
			cout << max(-1LL, x) << '\n';
		}
		return 0;
	}else if(!bambo){
		while(q--){
			int s, t; cin >> s >> t;
			int x, y; cin >> x >> y;
			int lc = lca(s, t);
			int cnt = checks(s, depth[s] - depth[lc]);
			cnt+= checks(t, depth[t] - depth[lc]);
			cnt-= (y / coins);
			x-= max(0LL, cnt);
			cout << max(-1LL, x) << '\n';
		}
		return 0;
	}else{
		vector<int> p;
		vector<pair<int, int> > range(n+1);
		for(int i = 1;i <= n; i++){
			range[i].ff = p.size();
			for(int x : val[i]){
				p.push_back(x);
			}
			range[i].ss = p.size()-1;
		}
		int sz = p.size();
		vector<node> t(4*sz);
		auto merge=[&](auto left, auto right){
			node res ={{}, {}};
			int i = 0, j = 0;
			while(i < (int)left.a.size() || j < (int)right.a.size()){
				if(i >= (int)left.a.size() && j >= (int)right.a.size()) break;
				if(i >= (int)left.a.size()){
					res.a.push_back(right.a[j]);
					j++;
				}else if(j >= (int)right.a.size()){
					res.a.push_back(left.a[i]);
					i++;
				}else{
					if(left.a[i] < right.a[j]){
						res.a.push_back(left.a[i]);
						i++;
					}else{
						res.a.push_back(right.a[j]);
						j++;
					}
				}
				res.pr.push_back((res.pr.empty() ? 0 : res.pr.back()) + res.a.back());
			}
			return res;
		};
		
		auto build=[&](auto build, int v, int vl, int vr)->auto{
			if(vl == vr){
				t[v] = {{p[vl]}, {p[vl]}};
				return;
			}
			int mid = (vl + vr)>>1;
			build(build, v<<1, vl, mid);
			build(build, v<<1|1, mid+1, vr);
			t[v] = merge(t[v<<1], t[v<<1|1]);
		};
		node zero = {{}, {}};
		auto get=[&](auto get, int l, int r, int v, int vl, int vr)->auto{
			if(l > vr or vl > r) return zero;
			if(l <= vl && r >= vr) return t[v];
			int mid = (vl + vr)>>1;
			return merge(get(get, l, r, v<<1, vl, mid), get(get, l, r, v<<1|1, mid+1, vr));
		};
		
		auto sum=[&](auto sum, int l, int r, int x, int v, int vl, int vr)->auto{
			if(l > vr or vl > r) return 0LL;
			if(l <= vl && r >= vr){
				int it = upper_bound(all(t[v].a), x) - t[v].a.begin();
				it--;
				if(it >= 0) return t[v].pr[it];
				else return 0LL;
			} 
			int mid = (vl + vr)>>1;
			return sum(sum, l, r, x, v<<1, vl, mid) + sum(sum, l, r, x, v<<1|1, mid+1, vr);
		};
		
		auto smaller=[&](auto smaller, int l, int r, int x, int v, int vl, int vr)->auto{
			if(l > vr or vl > r) return 0LL;
			if(l <= vl && r >= vr){
				int it = upper_bound(all(t[v].a), x) - t[v].a.begin();
				return it;
			} 
			int mid = (vl + vr)>>1;
			return smaller(smaller, l, r, x, v<<1, vl, mid) + smaller(smaller, l, r, x, v<<1|1, mid+1, vr);
		};
		
		build(build, 1, 0, sz-1);
		while(q--){
			int s, t; cin >> s >> t;
			int x, y; cin >> x >> y;
			if(depth[s] < depth[t]) swap(s, t);
			int lc = t;
			int cnt = checks(s, depth[s] - depth[lc]);
			
			int l = range[go_k(s, depth[s] - depth[lc] - 1)].ff, r = range[s].ss;
			
		//	cout << "vertex 1: " << t << '\n';
			//cout << "vertex 2: " << s << '\n';
			
			
			/*for(auto x : res.a) cout << x << ' ';
			cout << '\n';
			for(auto x : res.pr) cout << x << ' ';
			cout << '\n';*/
			int lo = -1, ro = (int)1e16;
			while(lo + 1 < ro){
				int mid = (lo + ro)>>1;
				if(sum(sum, l, r, mid, 1, 0, sz-1) <= y){
					lo = mid;
				}else ro = mid;
			}
			cnt-= smaller(smaller, l, r, lo, 1, 0, sz-1);
			x-= cnt;			
			cout << max(-1LL, x) << '\n';
		}
	}
	
	
	return 0;
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:242:8: warning: variable 'get' set but not used [-Wunused-but-set-variable]
  242 |   auto get=[&](auto get, int l, int r, int v, int vl, int vr)->auto{
      |        ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11852 KB Output is correct
3 Correct 2 ms 11868 KB Output is correct
4 Correct 3 ms 11988 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 5 ms 14036 KB Output is correct
8 Correct 5 ms 14172 KB Output is correct
9 Correct 5 ms 14172 KB Output is correct
10 Correct 6 ms 14272 KB Output is correct
11 Correct 5 ms 14172 KB Output is correct
12 Correct 6 ms 14172 KB Output is correct
13 Correct 72 ms 14428 KB Output is correct
14 Correct 72 ms 14172 KB Output is correct
15 Correct 30 ms 14168 KB Output is correct
16 Correct 24 ms 14172 KB Output is correct
17 Correct 21 ms 14172 KB Output is correct
18 Correct 31 ms 14168 KB Output is correct
19 Correct 5 ms 14428 KB Output is correct
20 Correct 4 ms 14168 KB Output is correct
21 Correct 4 ms 14172 KB Output is correct
22 Correct 4 ms 14172 KB Output is correct
23 Correct 54 ms 14220 KB Output is correct
24 Correct 49 ms 14168 KB Output is correct
25 Correct 50 ms 14284 KB Output is correct
26 Correct 5 ms 14176 KB Output is correct
27 Correct 4 ms 14172 KB Output is correct
28 Correct 5 ms 14248 KB Output is correct
29 Correct 4 ms 14172 KB Output is correct
30 Correct 5 ms 14172 KB Output is correct
31 Correct 5 ms 14172 KB Output is correct
32 Correct 5 ms 14172 KB Output is correct
33 Correct 69 ms 14428 KB Output is correct
34 Correct 69 ms 14428 KB Output is correct
35 Correct 69 ms 14424 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 6 ms 14172 KB Output is correct
3 Correct 5 ms 14168 KB Output is correct
4 Correct 6 ms 14172 KB Output is correct
5 Correct 129 ms 48184 KB Output is correct
6 Correct 127 ms 41604 KB Output is correct
7 Correct 132 ms 46780 KB Output is correct
8 Correct 133 ms 46012 KB Output is correct
9 Correct 110 ms 47040 KB Output is correct
10 Correct 159 ms 48316 KB Output is correct
11 Correct 166 ms 48468 KB Output is correct
12 Correct 169 ms 48392 KB Output is correct
13 Correct 166 ms 48532 KB Output is correct
14 Correct 160 ms 48516 KB Output is correct
15 Correct 217 ms 54076 KB Output is correct
16 Correct 201 ms 54204 KB Output is correct
17 Correct 208 ms 53536 KB Output is correct
18 Correct 213 ms 48060 KB Output is correct
19 Correct 217 ms 47928 KB Output is correct
20 Correct 245 ms 48316 KB Output is correct
21 Correct 142 ms 47808 KB Output is correct
22 Correct 160 ms 47804 KB Output is correct
23 Correct 166 ms 48636 KB Output is correct
24 Correct 159 ms 48576 KB Output is correct
25 Correct 142 ms 48400 KB Output is correct
26 Correct 166 ms 48648 KB Output is correct
27 Correct 160 ms 48936 KB Output is correct
28 Correct 138 ms 48320 KB Output is correct
29 Correct 172 ms 48388 KB Output is correct
30 Correct 150 ms 48416 KB Output is correct
31 Correct 137 ms 48504 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 68 ms 14444 KB Output is correct
3 Correct 68 ms 14424 KB Output is correct
4 Correct 71 ms 14684 KB Output is correct
5 Correct 1352 ms 90404 KB Output is correct
6 Correct 1451 ms 84504 KB Output is correct
7 Correct 2037 ms 101948 KB Output is correct
8 Correct 2592 ms 120624 KB Output is correct
9 Incorrect 2614 ms 120428 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11852 KB Output is correct
3 Correct 2 ms 11868 KB Output is correct
4 Correct 3 ms 11988 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 5 ms 14036 KB Output is correct
8 Correct 5 ms 14172 KB Output is correct
9 Correct 5 ms 14172 KB Output is correct
10 Correct 6 ms 14272 KB Output is correct
11 Correct 5 ms 14172 KB Output is correct
12 Correct 6 ms 14172 KB Output is correct
13 Correct 72 ms 14428 KB Output is correct
14 Correct 72 ms 14172 KB Output is correct
15 Correct 30 ms 14168 KB Output is correct
16 Correct 24 ms 14172 KB Output is correct
17 Correct 21 ms 14172 KB Output is correct
18 Correct 31 ms 14168 KB Output is correct
19 Correct 5 ms 14428 KB Output is correct
20 Correct 4 ms 14168 KB Output is correct
21 Correct 4 ms 14172 KB Output is correct
22 Correct 4 ms 14172 KB Output is correct
23 Correct 54 ms 14220 KB Output is correct
24 Correct 49 ms 14168 KB Output is correct
25 Correct 50 ms 14284 KB Output is correct
26 Correct 5 ms 14176 KB Output is correct
27 Correct 4 ms 14172 KB Output is correct
28 Correct 5 ms 14248 KB Output is correct
29 Correct 4 ms 14172 KB Output is correct
30 Correct 5 ms 14172 KB Output is correct
31 Correct 5 ms 14172 KB Output is correct
32 Correct 5 ms 14172 KB Output is correct
33 Correct 69 ms 14428 KB Output is correct
34 Correct 69 ms 14428 KB Output is correct
35 Correct 69 ms 14424 KB Output is correct
36 Correct 2 ms 11868 KB Output is correct
37 Correct 6 ms 14172 KB Output is correct
38 Correct 5 ms 14168 KB Output is correct
39 Correct 6 ms 14172 KB Output is correct
40 Correct 129 ms 48184 KB Output is correct
41 Correct 127 ms 41604 KB Output is correct
42 Correct 132 ms 46780 KB Output is correct
43 Correct 133 ms 46012 KB Output is correct
44 Correct 110 ms 47040 KB Output is correct
45 Correct 159 ms 48316 KB Output is correct
46 Correct 166 ms 48468 KB Output is correct
47 Correct 169 ms 48392 KB Output is correct
48 Correct 166 ms 48532 KB Output is correct
49 Correct 160 ms 48516 KB Output is correct
50 Correct 217 ms 54076 KB Output is correct
51 Correct 201 ms 54204 KB Output is correct
52 Correct 208 ms 53536 KB Output is correct
53 Correct 213 ms 48060 KB Output is correct
54 Correct 217 ms 47928 KB Output is correct
55 Correct 245 ms 48316 KB Output is correct
56 Correct 142 ms 47808 KB Output is correct
57 Correct 160 ms 47804 KB Output is correct
58 Correct 166 ms 48636 KB Output is correct
59 Correct 159 ms 48576 KB Output is correct
60 Correct 142 ms 48400 KB Output is correct
61 Correct 166 ms 48648 KB Output is correct
62 Correct 160 ms 48936 KB Output is correct
63 Correct 138 ms 48320 KB Output is correct
64 Correct 172 ms 48388 KB Output is correct
65 Correct 150 ms 48416 KB Output is correct
66 Correct 137 ms 48504 KB Output is correct
67 Correct 2 ms 11868 KB Output is correct
68 Correct 68 ms 14444 KB Output is correct
69 Correct 68 ms 14424 KB Output is correct
70 Correct 71 ms 14684 KB Output is correct
71 Correct 1352 ms 90404 KB Output is correct
72 Correct 1451 ms 84504 KB Output is correct
73 Correct 2037 ms 101948 KB Output is correct
74 Correct 2592 ms 120624 KB Output is correct
75 Incorrect 2614 ms 120428 KB Output isn't correct
76 Halted 0 ms 0 KB -