oj.uz

Submission #734380

# Submission time Handle Problem Language Result Execution time Memory
734380 2023-05-02T10:51:07 Z NeroZein Two Currencies (JOI23_currencies) C++17
100 / 100
 1233 ms 40744 KB 
#include "bits/stdc++.h"
#define int long long
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

struct queries {
	int u, v, l, gold, silver;
};

const int Log = 18;
const int N = 100005;

int n, m, q;
vector<int> g[N]; 
pair<int,int> e[N];
pair<int,int> ch[N];

int idd; 
int up[Log][N];
int in[N], out[N], dep[N];

void Dfs (int v, int p) {
	in[v] = ++idd;
	for (int u : g[v]) {
		if (u == p) continue;
		dep[u] = dep[v] + 1; 
		up[0][u] = v;
		for (int i = 1; i < Log; ++i) {
			up[i][u] = up[i - 1][up[i - 1][u]];
		}
		Dfs(u, v);
	}
	out[v] = idd;
}

int Lca (int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 0; i < Log; ++i) {
		if ((dep[u] - dep[v]) >> i & 1) {
			u = up[i][u];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = Log - 1; i >= 0; --i) {
		if (up[i][u] != up[i][v]) {
			u = up[i][u], v = up[i][v];
		}
	}
	return up[0][u];
}

int tree[N];
void upd (int id, int v) {
	while (id < N) {
		tree[id] += v;
		id += id & -id;
	}
}

void upd (int l, int r, int v) {
	upd(l, v);
	upd(r + 1, -v); 
}

int qry (int id) {
	int ret = 0;
	while (id) {
		ret += tree[id];
		id -= id & -id;
	}
	return ret;
}

int getSum (int u, int v, int l) {
	return qry(in[u]) + qry(in[v]) - 2 * qry(in[l]); 
}

void addEdge (int i, bool weighted) {
	int u = e[ch[i].first].first, v = e[ch[i].first].second; 
	if (dep[u] < dep[v]) swap(u, v); 
	if (weighted) {
		upd(in[u], out[u], ch[i].second);
	} else {
		upd(in[u], out[u], 1);
	}
}

int ans[N]; 
int L[N], R[N];
pair<int,int> Mid[N]; 

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> q; 
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		e[i] = {u, v};   
	}
	Dfs(1, 1);
	for (int i = 0; i < m; ++i) {
		int p, c;
		cin >> p >> c;
		ch[i] = {p - 1, c}; 
		addEdge(i, 0);
	}
	vector<queries> qs(q); 
	for (int i = 0; i < q; ++i) {
		int u, v, gold, silver;
		cin >> u >> v >> gold >> silver;
		qs[i] = {u, v, Lca(u, v), gold, silver}; 
		ans[i] = getSum(u, v, qs[i].l); 
	}
	sort(ch, ch + m, [&](pair<int,int>& a, pair<int,int>& b) {
		return a.second < b.second;
	});
	for (int i = 0; i < q; ++i) {
		L[i] = -1, R[i] = m - 1; 
	}
	while (true) {
		memset(tree, 0, sizeof tree);
		bool changed = false;
		for (int i = 0; i < q; ++i) {
			if (L[i] != R[i]) {
				Mid[i] = make_pair((L[i] + R[i] + 1) >> 1, i);				
				changed = true; 
			} else {
				Mid[i] = make_pair(L[i], i); 
			}
		}
		sort(Mid, Mid + q); 
		int p = 0;
		if (!changed) {
			for (int i = 0; i < q; ++i) {
				while (p <= Mid[i].first) {
					addEdge(p, 0); 
					p++; 
				}
				ans[Mid[i].second] = qs[Mid[i].second].gold - (ans[Mid[i].second] - getSum(qs[Mid[i].second].u, qs[Mid[i].second].v, qs[Mid[i].second].l));  
			}
			break; 
		}
		for (int i = 0; i < q; ++i) {
			while (p <= Mid[i].first) {
				addEdge(p, 1); 
				p++;
			}
			int id = Mid[i].second;
			if (getSum(qs[id].u, qs[id].v, qs[id].l) <= qs[id].silver) {
				L[id] = Mid[i].first;
			} else {
				R[id] = Mid[i].first - 1; 
			}
		}
	}
	for (int i = 0; i < q; ++i) {
		cout << max(-1LL, ans[i]) << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 2 ms 3540 KB Output is correct
3 Correct 2 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 6 ms 4052 KB Output is correct
6 Correct 8 ms 4156 KB Output is correct
7 Correct 8 ms 4052 KB Output is correct
8 Correct 10 ms 4180 KB Output is correct
9 Correct 10 ms 4180 KB Output is correct
10 Correct 8 ms 4180 KB Output is correct
11 Correct 10 ms 4180 KB Output is correct
12 Correct 12 ms 4232 KB Output is correct
13 Correct 9 ms 4300 KB Output is correct
14 Correct 13 ms 4180 KB Output is correct
15 Correct 9 ms 4180 KB Output is correct
16 Correct 9 ms 4180 KB Output is correct
17 Correct 9 ms 4180 KB Output is correct
18 Correct 10 ms 4248 KB Output is correct
19 Correct 11 ms 4180 KB Output is correct
20 Correct 9 ms 4180 KB Output is correct
21 Correct 11 ms 4180 KB Output is correct
22 Correct 8 ms 4180 KB Output is correct
23 Correct 9 ms 4236 KB Output is correct
24 Correct 8 ms 4180 KB Output is correct
25 Correct 9 ms 4180 KB Output is correct
26 Correct 9 ms 4180 KB Output is correct
27 Correct 8 ms 4228 KB Output is correct
28 Correct 9 ms 4180 KB Output is correct
29 Correct 10 ms 4180 KB Output is correct
30 Correct 10 ms 4232 KB Output is correct
31 Correct 10 ms 4180 KB Output is correct
32 Correct 12 ms 4180 KB Output is correct
33 Correct 9 ms 4308 KB Output is correct
34 Correct 13 ms 4280 KB Output is correct
35 Correct 10 ms 4288 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3540 KB Output is correct
2 Correct 11 ms 4232 KB Output is correct
3 Correct 10 ms 4228 KB Output is correct
4 Correct 12 ms 4236 KB Output is correct
5 Correct 946 ms 31644 KB Output is correct
6 Correct 879 ms 27248 KB Output is correct
7 Correct 970 ms 29944 KB Output is correct
8 Correct 741 ms 28824 KB Output is correct
9 Correct 626 ms 28364 KB Output is correct
10 Correct 1061 ms 34836 KB Output is correct
11 Correct 1126 ms 34836 KB Output is correct
12 Correct 1124 ms 34832 KB Output is correct
13 Correct 1164 ms 34772 KB Output is correct
14 Correct 975 ms 34844 KB Output is correct
15 Correct 1042 ms 40080 KB Output is correct
16 Correct 951 ms 40544 KB Output is correct
17 Correct 950 ms 39800 KB Output is correct
18 Correct 1063 ms 34388 KB Output is correct
19 Correct 1233 ms 34468 KB Output is correct
20 Correct 1109 ms 34508 KB Output is correct
21 Correct 1026 ms 34896 KB Output is correct
22 Correct 1008 ms 34964 KB Output is correct
23 Correct 918 ms 34988 KB Output is correct
24 Correct 988 ms 34892 KB Output is correct
25 Correct 816 ms 34972 KB Output is correct
26 Correct 822 ms 34892 KB Output is correct
27 Correct 777 ms 34920 KB Output is correct
28 Correct 794 ms 34836 KB Output is correct
29 Correct 668 ms 34804 KB Output is correct
30 Correct 714 ms 34868 KB Output is correct
31 Correct 725 ms 34860 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 9 ms 4260 KB Output is correct
3 Correct 8 ms 4344 KB Output is correct
4 Correct 9 ms 4308 KB Output is correct
5 Correct 545 ms 36196 KB Output is correct
6 Correct 478 ms 35536 KB Output is correct
7 Correct 553 ms 27264 KB Output is correct
8 Correct 816 ms 40696 KB Output is correct
9 Correct 884 ms 40692 KB Output is correct
10 Correct 905 ms 40640 KB Output is correct
11 Correct 728 ms 40620 KB Output is correct
12 Correct 746 ms 40616 KB Output is correct
13 Correct 731 ms 40612 KB Output is correct
14 Correct 750 ms 40744 KB Output is correct
15 Correct 768 ms 40608 KB Output is correct
16 Correct 752 ms 40624 KB Output is correct
17 Correct 799 ms 40616 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 2 ms 3540 KB Output is correct
3 Correct 2 ms 3540 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 6 ms 4052 KB Output is correct
6 Correct 8 ms 4156 KB Output is correct
7 Correct 8 ms 4052 KB Output is correct
8 Correct 10 ms 4180 KB Output is correct
9 Correct 10 ms 4180 KB Output is correct
10 Correct 8 ms 4180 KB Output is correct
11 Correct 10 ms 4180 KB Output is correct
12 Correct 12 ms 4232 KB Output is correct
13 Correct 9 ms 4300 KB Output is correct
14 Correct 13 ms 4180 KB Output is correct
15 Correct 9 ms 4180 KB Output is correct
16 Correct 9 ms 4180 KB Output is correct
17 Correct 9 ms 4180 KB Output is correct
18 Correct 10 ms 4248 KB Output is correct
19 Correct 11 ms 4180 KB Output is correct
20 Correct 9 ms 4180 KB Output is correct
21 Correct 11 ms 4180 KB Output is correct
22 Correct 8 ms 4180 KB Output is correct
23 Correct 9 ms 4236 KB Output is correct
24 Correct 8 ms 4180 KB Output is correct
25 Correct 9 ms 4180 KB Output is correct
26 Correct 9 ms 4180 KB Output is correct
27 Correct 8 ms 4228 KB Output is correct
28 Correct 9 ms 4180 KB Output is correct
29 Correct 10 ms 4180 KB Output is correct
30 Correct 10 ms 4232 KB Output is correct
31 Correct 10 ms 4180 KB Output is correct
32 Correct 12 ms 4180 KB Output is correct
33 Correct 9 ms 4308 KB Output is correct
34 Correct 13 ms 4280 KB Output is correct
35 Correct 10 ms 4288 KB Output is correct
36 Correct 3 ms 3540 KB Output is correct
37 Correct 11 ms 4232 KB Output is correct
38 Correct 10 ms 4228 KB Output is correct
39 Correct 12 ms 4236 KB Output is correct
40 Correct 946 ms 31644 KB Output is correct
41 Correct 879 ms 27248 KB Output is correct
42 Correct 970 ms 29944 KB Output is correct
43 Correct 741 ms 28824 KB Output is correct
44 Correct 626 ms 28364 KB Output is correct
45 Correct 1061 ms 34836 KB Output is correct
46 Correct 1126 ms 34836 KB Output is correct
47 Correct 1124 ms 34832 KB Output is correct
48 Correct 1164 ms 34772 KB Output is correct
49 Correct 975 ms 34844 KB Output is correct
50 Correct 1042 ms 40080 KB Output is correct
51 Correct 951 ms 40544 KB Output is correct
52 Correct 950 ms 39800 KB Output is correct
53 Correct 1063 ms 34388 KB Output is correct
54 Correct 1233 ms 34468 KB Output is correct
55 Correct 1109 ms 34508 KB Output is correct
56 Correct 1026 ms 34896 KB Output is correct
57 Correct 1008 ms 34964 KB Output is correct
58 Correct 918 ms 34988 KB Output is correct
59 Correct 988 ms 34892 KB Output is correct
60 Correct 816 ms 34972 KB Output is correct
61 Correct 822 ms 34892 KB Output is correct
62 Correct 777 ms 34920 KB Output is correct
63 Correct 794 ms 34836 KB Output is correct
64 Correct 668 ms 34804 KB Output is correct
65 Correct 714 ms 34868 KB Output is correct
66 Correct 725 ms 34860 KB Output is correct
67 Correct 2 ms 3540 KB Output is correct
68 Correct 9 ms 4260 KB Output is correct
69 Correct 8 ms 4344 KB Output is correct
70 Correct 9 ms 4308 KB Output is correct
71 Correct 545 ms 36196 KB Output is correct
72 Correct 478 ms 35536 KB Output is correct
73 Correct 553 ms 27264 KB Output is correct
74 Correct 816 ms 40696 KB Output is correct
75 Correct 884 ms 40692 KB Output is correct
76 Correct 905 ms 40640 KB Output is correct
77 Correct 728 ms 40620 KB Output is correct
78 Correct 746 ms 40616 KB Output is correct
79 Correct 731 ms 40612 KB Output is correct
80 Correct 750 ms 40744 KB Output is correct
81 Correct 768 ms 40608 KB Output is correct
82 Correct 752 ms 40624 KB Output is correct
83 Correct 799 ms 40616 KB Output is correct
84 Correct 661 ms 28360 KB Output is correct
85 Correct 655 ms 22820 KB Output is correct
86 Correct 571 ms 22496 KB Output is correct
87 Correct 939 ms 34884 KB Output is correct
88 Correct 1018 ms 34880 KB Output is correct
89 Correct 1010 ms 34844 KB Output is correct
90 Correct 1055 ms 34844 KB Output is correct
91 Correct 1060 ms 34956 KB Output is correct
92 Correct 989 ms 38272 KB Output is correct
93 Correct 973 ms 39648 KB Output is correct
94 Correct 1158 ms 34584 KB Output is correct
95 Correct 1182 ms 34528 KB Output is correct
96 Correct 1208 ms 34516 KB Output is correct
97 Correct 1012 ms 34604 KB Output is correct
98 Correct 965 ms 34888 KB Output is correct
99 Correct 950 ms 34940 KB Output is correct
100 Correct 937 ms 34936 KB Output is correct
101 Correct 1039 ms 34920 KB Output is correct
102 Correct 892 ms 34896 KB Output is correct
103 Correct 889 ms 34844 KB Output is correct
104 Correct 858 ms 34840 KB Output is correct
105 Correct 727 ms 34836 KB Output is correct
106 Correct 770 ms 34848 KB Output is correct
107 Correct 831 ms 34840 KB Output is correct
108 Correct 885 ms 34844 KB Output is correct