oj.uz

Submission #888695

# Submission time Handle Problem Language Result Execution time Memory
888695 2023-12-18T05:46:09 Z vjudge1 Two Currencies (JOI23_currencies) C++17
10 / 100
 136 ms 52156 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];
		}
	}
	if(a == b) return a;
	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; 
}
*/


/*
8 7 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
3 7 2 31

*/
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 < 18; i++){
		if(d & (1<<i)) cnt+= sum[a][i];
	}
	return cnt;
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		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;
			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{
		while(q--){
			int s, t; cin >> s >> t;
			int x, y; cin >> x >> y;
			int lc = lca(s, t);
			int d = distance(s, t);
			int cnt = checks(s, d-1);
			
			cnt-= (y / coins);
			x-= cnt;
			cout << max(-1LL, x) << '\n';
		}
		return 0;
	}
	
	
	return 0;
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:188:8: warning: unused variable 'lc' [-Wunused-variable]
  188 |    int lc = lca(s, t);
      |        ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 3 ms 11920 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 6 ms 14172 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 5 ms 14048 KB Output is correct
8 Correct 5 ms 14264 KB Output is correct
9 Correct 5 ms 14172 KB Output is correct
10 Correct 5 ms 14172 KB Output is correct
11 Correct 5 ms 14272 KB Output is correct
12 Correct 5 ms 14172 KB Output is correct
13 Correct 71 ms 14416 KB Output is correct
14 Correct 80 ms 14364 KB Output is correct
15 Correct 30 ms 14168 KB Output is correct
16 Correct 24 ms 14316 KB Output is correct
17 Correct 19 ms 14172 KB Output is correct
18 Correct 30 ms 14316 KB Output is correct
19 Correct 4 ms 14168 KB Output is correct
20 Correct 4 ms 14172 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 14316 KB Output is correct
24 Correct 50 ms 14168 KB Output is correct
25 Correct 49 ms 14168 KB Output is correct
26 Correct 5 ms 14172 KB Output is correct
27 Correct 6 ms 14324 KB Output is correct
28 Correct 5 ms 14172 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 14228 KB Output is correct
32 Correct 5 ms 14172 KB Output is correct
33 Correct 67 ms 14424 KB Output is correct
34 Correct 68 ms 14424 KB Output is correct
35 Correct 67 ms 14424 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 5 ms 14172 KB Output is correct
3 Correct 5 ms 14172 KB Output is correct
4 Correct 5 ms 14172 KB Output is correct
5 Incorrect 136 ms 48416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 68 ms 14424 KB Output is correct
3 Correct 68 ms 14168 KB Output is correct
4 Correct 76 ms 14424 KB Output is correct
5 Incorrect 114 ms 52156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 3 ms 11920 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 6 ms 14172 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 5 ms 14048 KB Output is correct
8 Correct 5 ms 14264 KB Output is correct
9 Correct 5 ms 14172 KB Output is correct
10 Correct 5 ms 14172 KB Output is correct
11 Correct 5 ms 14272 KB Output is correct
12 Correct 5 ms 14172 KB Output is correct
13 Correct 71 ms 14416 KB Output is correct
14 Correct 80 ms 14364 KB Output is correct
15 Correct 30 ms 14168 KB Output is correct
16 Correct 24 ms 14316 KB Output is correct
17 Correct 19 ms 14172 KB Output is correct
18 Correct 30 ms 14316 KB Output is correct
19 Correct 4 ms 14168 KB Output is correct
20 Correct 4 ms 14172 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 14316 KB Output is correct
24 Correct 50 ms 14168 KB Output is correct
25 Correct 49 ms 14168 KB Output is correct
26 Correct 5 ms 14172 KB Output is correct
27 Correct 6 ms 14324 KB Output is correct
28 Correct 5 ms 14172 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 14228 KB Output is correct
32 Correct 5 ms 14172 KB Output is correct
33 Correct 67 ms 14424 KB Output is correct
34 Correct 68 ms 14424 KB Output is correct
35 Correct 67 ms 14424 KB Output is correct
36 Correct 2 ms 11864 KB Output is correct
37 Correct 5 ms 14172 KB Output is correct
38 Correct 5 ms 14172 KB Output is correct
39 Correct 5 ms 14172 KB Output is correct
40 Incorrect 136 ms 48416 KB Output isn't correct
41 Halted 0 ms 0 KB -