oj.uz

답안 #791986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791986 2023-07-24T13:28:28 Z TranGiaHuy1508 Two Currencies (JOI23_currencies) C++17
100 / 100
 1573 ms 116128 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long

using ii = pair<int, int>;

struct Segtree{
	vector<int> tree;
	int _n;

	Segtree() = default;
	Segtree(int N): tree(4*N), _n(N) {}

	int get(int pos) { return get(1, 0, _n - 1, pos); }
	int get(int i, int l, int r, int pos){
		if (l == pos && r == pos) return tree[i];
		int mid = (l + r) >> 1;
		if (pos <= mid) return tree[i] + get(i<<1, l, mid, pos);
		else return tree[i] + get(i<<1|1, mid+1, r, pos);
	}

	void update(int tl, int tr, int delta) { update(1, 0, _n - 1, tl, tr, delta); }
	void update(int i, int l, int r, int tl, int tr, int delta){
		if (tl <= l && r <= tr) tree[i] += delta;
		else if (tl > r || tr < l) return;
		else{
			int mid = (l + r) >> 1;
			update(i<<1, l, mid, tl, tr, delta);
			update(i<<1|1, mid+1, r, tl, tr, delta);
		}
	}
};

template <class T>
struct RMQ{
	vector<vector<T>> table;
	int _n, _lg;

	RMQ() = default;
	RMQ(vector<T> &V){
		_n = V.size();
		_lg = 64 - __builtin_clzll(_n);

		table.assign(_lg, vector<T>(_n));
		table[0] = V;

		for (int j = 1; j < _lg; j++){
			for (int i = 0; i + (1 << j) <= _n; i++){
				table[j][i] = min(table[j-1][i], table[j-1][i + (1 << (j-1))]);
			}
		}
	}

	T get(int l, int r){
		if (l > r) swap(l, r);
		int j = 63 - __builtin_clzll(r - l + 1);
		return min(table[j][l], table[j][r - (1 << j) + 1]);
	}
};

struct Query{
	int a, b;
	int lca;
	int gold, silver;

	int idx;
};

struct PBS{
	int lb, rb;
	vector<Query> qs;
};

int n, m, q;
vector<vector<int>> adj;
vector<ii> edges;
vector<ii> checkpoints;
vector<Query> all_queries;

int timer = 0;
vector<int> tin, tout, occ;
vector<ii> eulertour;
RMQ<ii> rmq;

vector<int> max_silver;

void dfs_euler(int x, int p = -1, int d = 0){
	tin[x] = timer++;
	occ[x] = eulertour.size();
	eulertour.emplace_back(d, x);

	for (auto k: adj[x]){
		if (k == p) continue;
		dfs_euler(k, x, d+1);
		eulertour.emplace_back(d, x);
	}

	tout[x] = timer - 1;
}

inline int LCA(int x, int y){
	return rmq.get(occ[x], occ[y]).second;
}

void main_program(){
	cin >> n >> m >> q;

	adj.resize(n);
	edges.resize(n-1);
	checkpoints.resize(m);
	all_queries.resize(q);

	tin.resize(n);
	tout.resize(n);
	occ.resize(n);
	max_silver.resize(q);

	for (int i = 0; i < n-1; i++){
		int x, y; cin >> x >> y;
		x--; y--;

		adj[x].push_back(y);
		adj[y].push_back(x);

		edges[i] = {x, y};
	}

	for (int i = 0; i < m; i++){
		int P, cost; cin >> P >> cost;
		P--;

		checkpoints[i] = {P, cost};
	}

	sort(checkpoints.begin(), checkpoints.end(), [](ii A, ii B){
		return A.second < B.second;
	});

	dfs_euler(0);
	rmq = RMQ<ii>(eulertour);

	for (int i = 0; i < n-1; i++){
		if (tin[edges[i].first] > tin[edges[i].second])
			swap(edges[i].first, edges[i].second);
	}

	for (int i = 0; i < q; i++){
		int a, b, gold, silver;
		cin >> a >> b >> gold >> silver;
		a--; b--;
		int lca = LCA(a, b);

		all_queries[i] = Query{a, b, lca, gold, silver, i};
	}

	vector<PBS> crrpbs = {PBS{0, m, all_queries}};
	while (!crrpbs.empty()){
		vector<PBS> nxtpbs;
		int prev = -1;
		Segtree st(n);
		Segtree stcnt(n);
		for (auto range: crrpbs){
			if (range.lb == range.rb){
				for (int i = prev + 1; i < range.lb; i++){
					auto [P, cost] = checkpoints[i];
					int x = edges[P].second;
					st.update(tin[x], tout[x], cost);
					stcnt.update(tin[x], tout[x], 1);
				}
				prev = max(prev, range.lb - 1);

				for (auto query: range.qs){
					max_silver[query.idx] =
					stcnt.get(tin[query.a]) + stcnt.get(tin[query.b]) - stcnt.get(tin[query.lca]) * 2;
				}
				continue;
			}

			int mid = (range.lb + range.rb) >> 1;
			for (int i = prev + 1; i <= mid; i++){
				auto [P, cost] = checkpoints[i];
				int x = edges[P].second;
				st.update(tin[x], tout[x], cost);
				stcnt.update(tin[x], tout[x], 1);
			}
			prev = max(prev, mid);

			PBS leftnode{range.lb, mid, {}}, rightnode{mid+1, range.rb, {}};
			for (auto query: range.qs){
				int silver_cost = st.get(tin[query.a]) + st.get(tin[query.b]) - st.get(tin[query.lca]) * 2;
				if (silver_cost <= query.silver) rightnode.qs.push_back(query);
				else leftnode.qs.push_back(query);
			}

			if (!leftnode.qs.empty()) nxtpbs.push_back(leftnode);
			if (!rightnode.qs.empty()) nxtpbs.push_back(rightnode);
		}
		crrpbs.swap(nxtpbs);
	}

	Segtree st(n);
	for (auto pt: checkpoints){
		int x = edges[pt.first].second;
		st.update(tin[x], tout[x], 1);
	}

	for (int i = 0; i < q; i++){
		auto query = all_queries[i];
		int cnt_pt = st.get(tin[query.a]) + st.get(tin[query.b]) - st.get(tin[query.lca]) * 2;
		int gold_cost = cnt_pt - max_silver[i];
		if (gold_cost > query.gold) cout << "-1\n";
		else cout << query.gold - gold_cost << "\n";
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 9 ms 1740 KB Output is correct
6 Correct 11 ms 2032 KB Output is correct
7 Correct 9 ms 1620 KB Output is correct
8 Correct 11 ms 2132 KB Output is correct
9 Correct 11 ms 2124 KB Output is correct
10 Correct 12 ms 2132 KB Output is correct
11 Correct 12 ms 2132 KB Output is correct
12 Correct 11 ms 2124 KB Output is correct
13 Correct 12 ms 2204 KB Output is correct
14 Correct 11 ms 2104 KB Output is correct
15 Correct 12 ms 2132 KB Output is correct
16 Correct 12 ms 2092 KB Output is correct
17 Correct 13 ms 2132 KB Output is correct
18 Correct 13 ms 2100 KB Output is correct
19 Correct 10 ms 2096 KB Output is correct
20 Correct 10 ms 2128 KB Output is correct
21 Correct 10 ms 2132 KB Output is correct
22 Correct 10 ms 2128 KB Output is correct
23 Correct 11 ms 2132 KB Output is correct
24 Correct 9 ms 2132 KB Output is correct
25 Correct 9 ms 2132 KB Output is correct
26 Correct 8 ms 2132 KB Output is correct
27 Correct 8 ms 2124 KB Output is correct
28 Correct 8 ms 2132 KB Output is correct
29 Correct 8 ms 2156 KB Output is correct
30 Correct 12 ms 2132 KB Output is correct
31 Correct 11 ms 2132 KB Output is correct
32 Correct 11 ms 2120 KB Output is correct
33 Correct 13 ms 2160 KB Output is correct
34 Correct 11 ms 2228 KB Output is correct
35 Correct 11 ms 2228 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 11 ms 2132 KB Output is correct
3 Correct 11 ms 2132 KB Output is correct
4 Correct 11 ms 2008 KB Output is correct
5 Correct 931 ms 99528 KB Output is correct
6 Correct 963 ms 82124 KB Output is correct
7 Correct 914 ms 92592 KB Output is correct
8 Correct 757 ms 87884 KB Output is correct
9 Correct 756 ms 85780 KB Output is correct
10 Correct 1181 ms 108728 KB Output is correct
11 Correct 1215 ms 109108 KB Output is correct
12 Correct 1165 ms 108868 KB Output is correct
13 Correct 1270 ms 108968 KB Output is correct
14 Correct 1151 ms 110124 KB Output is correct
15 Correct 1408 ms 114700 KB Output is correct
16 Correct 1535 ms 115044 KB Output is correct
17 Correct 1194 ms 114360 KB Output is correct
18 Correct 1308 ms 107936 KB Output is correct
19 Correct 1320 ms 109740 KB Output is correct
20 Correct 1337 ms 109188 KB Output is correct
21 Correct 1104 ms 109704 KB Output is correct
22 Correct 1085 ms 109164 KB Output is correct
23 Correct 1109 ms 108380 KB Output is correct
24 Correct 1105 ms 108408 KB Output is correct
25 Correct 897 ms 109088 KB Output is correct
26 Correct 847 ms 109352 KB Output is correct
27 Correct 833 ms 110524 KB Output is correct
28 Correct 814 ms 108548 KB Output is correct
29 Correct 788 ms 107428 KB Output is correct
30 Correct 852 ms 108716 KB Output is correct
31 Correct 895 ms 109092 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 11 ms 2152 KB Output is correct
3 Correct 11 ms 2228 KB Output is correct
4 Correct 11 ms 2252 KB Output is correct
5 Correct 771 ms 100428 KB Output is correct
6 Correct 708 ms 98372 KB Output is correct
7 Correct 946 ms 73176 KB Output is correct
8 Correct 1252 ms 116128 KB Output is correct
9 Correct 1178 ms 115344 KB Output is correct
10 Correct 1230 ms 114592 KB Output is correct
11 Correct 918 ms 115052 KB Output is correct
12 Correct 999 ms 113864 KB Output is correct
13 Correct 876 ms 115260 KB Output is correct
14 Correct 759 ms 115364 KB Output is correct
15 Correct 751 ms 114980 KB Output is correct
16 Correct 827 ms 115620 KB Output is correct
17 Correct 883 ms 114476 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 9 ms 1740 KB Output is correct
6 Correct 11 ms 2032 KB Output is correct
7 Correct 9 ms 1620 KB Output is correct
8 Correct 11 ms 2132 KB Output is correct
9 Correct 11 ms 2124 KB Output is correct
10 Correct 12 ms 2132 KB Output is correct
11 Correct 12 ms 2132 KB Output is correct
12 Correct 11 ms 2124 KB Output is correct
13 Correct 12 ms 2204 KB Output is correct
14 Correct 11 ms 2104 KB Output is correct
15 Correct 12 ms 2132 KB Output is correct
16 Correct 12 ms 2092 KB Output is correct
17 Correct 13 ms 2132 KB Output is correct
18 Correct 13 ms 2100 KB Output is correct
19 Correct 10 ms 2096 KB Output is correct
20 Correct 10 ms 2128 KB Output is correct
21 Correct 10 ms 2132 KB Output is correct
22 Correct 10 ms 2128 KB Output is correct
23 Correct 11 ms 2132 KB Output is correct
24 Correct 9 ms 2132 KB Output is correct
25 Correct 9 ms 2132 KB Output is correct
26 Correct 8 ms 2132 KB Output is correct
27 Correct 8 ms 2124 KB Output is correct
28 Correct 8 ms 2132 KB Output is correct
29 Correct 8 ms 2156 KB Output is correct
30 Correct 12 ms 2132 KB Output is correct
31 Correct 11 ms 2132 KB Output is correct
32 Correct 11 ms 2120 KB Output is correct
33 Correct 13 ms 2160 KB Output is correct
34 Correct 11 ms 2228 KB Output is correct
35 Correct 11 ms 2228 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 11 ms 2132 KB Output is correct
38 Correct 11 ms 2132 KB Output is correct
39 Correct 11 ms 2008 KB Output is correct
40 Correct 931 ms 99528 KB Output is correct
41 Correct 963 ms 82124 KB Output is correct
42 Correct 914 ms 92592 KB Output is correct
43 Correct 757 ms 87884 KB Output is correct
44 Correct 756 ms 85780 KB Output is correct
45 Correct 1181 ms 108728 KB Output is correct
46 Correct 1215 ms 109108 KB Output is correct
47 Correct 1165 ms 108868 KB Output is correct
48 Correct 1270 ms 108968 KB Output is correct
49 Correct 1151 ms 110124 KB Output is correct
50 Correct 1408 ms 114700 KB Output is correct
51 Correct 1535 ms 115044 KB Output is correct
52 Correct 1194 ms 114360 KB Output is correct
53 Correct 1308 ms 107936 KB Output is correct
54 Correct 1320 ms 109740 KB Output is correct
55 Correct 1337 ms 109188 KB Output is correct
56 Correct 1104 ms 109704 KB Output is correct
57 Correct 1085 ms 109164 KB Output is correct
58 Correct 1109 ms 108380 KB Output is correct
59 Correct 1105 ms 108408 KB Output is correct
60 Correct 897 ms 109088 KB Output is correct
61 Correct 847 ms 109352 KB Output is correct
62 Correct 833 ms 110524 KB Output is correct
63 Correct 814 ms 108548 KB Output is correct
64 Correct 788 ms 107428 KB Output is correct
65 Correct 852 ms 108716 KB Output is correct
66 Correct 895 ms 109092 KB Output is correct
67 Correct 1 ms 212 KB Output is correct
68 Correct 11 ms 2152 KB Output is correct
69 Correct 11 ms 2228 KB Output is correct
70 Correct 11 ms 2252 KB Output is correct
71 Correct 771 ms 100428 KB Output is correct
72 Correct 708 ms 98372 KB Output is correct
73 Correct 946 ms 73176 KB Output is correct
74 Correct 1252 ms 116128 KB Output is correct
75 Correct 1178 ms 115344 KB Output is correct
76 Correct 1230 ms 114592 KB Output is correct
77 Correct 918 ms 115052 KB Output is correct
78 Correct 999 ms 113864 KB Output is correct
79 Correct 876 ms 115260 KB Output is correct
80 Correct 759 ms 115364 KB Output is correct
81 Correct 751 ms 114980 KB Output is correct
82 Correct 827 ms 115620 KB Output is correct
83 Correct 883 ms 114476 KB Output is correct
84 Correct 913 ms 87452 KB Output is correct
85 Correct 827 ms 64028 KB Output is correct
86 Correct 720 ms 64412 KB Output is correct
87 Correct 1155 ms 108964 KB Output is correct
88 Correct 1166 ms 109008 KB Output is correct
89 Correct 1216 ms 109976 KB Output is correct
90 Correct 1155 ms 108972 KB Output is correct
91 Correct 1159 ms 108856 KB Output is correct
92 Correct 1252 ms 112732 KB Output is correct
93 Correct 1228 ms 114048 KB Output is correct
94 Correct 1359 ms 108768 KB Output is correct
95 Correct 1427 ms 108680 KB Output is correct
96 Correct 1573 ms 108752 KB Output is correct
97 Correct 1475 ms 108644 KB Output is correct
98 Correct 1250 ms 109728 KB Output is correct
99 Correct 1165 ms 108968 KB Output is correct
100 Correct 1190 ms 109120 KB Output is correct
101 Correct 1129 ms 108344 KB Output is correct
102 Correct 906 ms 109360 KB Output is correct
103 Correct 869 ms 108900 KB Output is correct
104 Correct 938 ms 109140 KB Output is correct
105 Correct 910 ms 109712 KB Output is correct
106 Correct 850 ms 109892 KB Output is correct
107 Correct 904 ms 108612 KB Output is correct
108 Correct 917 ms 107392 KB Output is correct