oj.uz

답안 #936867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936867 2024-03-03T00:19:48 Z IOrtroiii Two Currencies (JOI23_currencies) C++14
100 / 100
 472 ms 45072 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Fenwick {
	vector<T> f;
	Fenwick(int N = 0): f(N) {
	}

	void add(int x, T v) {
		for (; x < int(f.size()); x |= (x + 1)) f[x] += v;
	}

	T get(int x) {
		T ans{};
		for (; x >= 0; x = (x & (x + 1)) - 1) ans += f[x];
		return ans;
	} 
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int N, M, Q; cin >> N >> M >> Q;
	vector<vector<int>> adj(N);
	vector<array<int, 2>> E(N - 1);
	for (int i = 0; i + 1 < N; ++i) {
		cin >> E[i][0] >> E[i][1]; --E[i][0], --E[i][1];
		adj[E[i][0]].push_back(E[i][1]);
		adj[E[i][1]].push_back(E[i][0]);
	}

	vector<int> par(N, -1);
	vector<int> sz(N);
	vector<int> depth(N);
	function<void(int)> dfs = [&](int v) {
		sz[v] = 1;
		for (int u : adj[v]) {
			par[u] = v;
			adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
			depth[u] = depth[v] + 1;
			dfs(u);
			sz[v] += sz[u];
		}
	};

	dfs(0);
	int timer = 0;
	vector<int> top(N);
	vector<int> tin(N);
	vector<int> tout(N);
	function<void(int, int)> hld = [&](int v, int t) {
		tin[v] = timer++;
		top[v] = t;
		int nv = -1;
		for (int u : adj[v]) {
			if (nv == -1 || sz[u] > sz[nv]) nv = u;
		}

		if (nv >= 0) hld(nv, t);
		for (int u : adj[v]) {
			if (u != nv) hld(u, u);
		}
		tout[v] = timer;
	};

	hld(0, 0);
	auto get_lca = [&](int v, int u) {
		while (top[v] != top[u]) {
			if (depth[top[v]] > depth[top[u]]) {
				v = par[top[v]];
			} else {
				u = par[top[u]];
			}
		}
		return depth[v] <= depth[u] ? v : u;
	};

	for (int i = 0; i < N - 1; ++i) {
		if (depth[E[i][0]] > depth[E[i][1]]) {
			swap(E[i][0], E[i][1]);
		}
	}
	vector<pair<int, int>> cpts(M);
	for (int i = 0; i < M; ++i) {
		int k, c; cin >> k >> c;
		cpts[i] = {c, E[k - 1][1]};
	}

	sort(cpts.begin(), cpts.end());
	Fenwick<int> f(N);
	for (auto [c, v] : cpts) {
		f.add(tin[v], +1);
		f.add(tout[v], -1);
	}

	vector<int> from(Q);
	vector<int> to(Q);
	vector<int> lca(Q);
	vector<int> cnt(Q);
	vector<int> gold(Q);
	vector<int> ans(Q);
	vector<int64_t> silver(Q);
	vector<int> lo(Q, -1);
	vector<int> hi(Q, M - 1);

	for (int q = 0; q < Q; ++q) {
		cin >> from[q] >> to[q]; --from[q], --to[q];
		lca[q] = get_lca(from[q], to[q]);
		cnt[q] = f.get(tin[from[q]]) + f.get(tin[to[q]]) - 2 * f.get(tin[lca[q]]);
		cin >> gold[q] >> silver[q];
		ans[q] = gold[q] - cnt[q];
	}

	vector<vector<int>> queries(M);
	while (true) {
		bool done = true;
		for (int q = 0; q < Q; ++q) if (lo[q] < hi[q]) {
			done = false;
			int md = (lo[q] + hi[q] + 1) / 2;
			queries[md].push_back(q);
		}

		if (done) break;
		Fenwick<int> fcnt(N);
		Fenwick<int64_t> fsum(N);
		for (int md = 0; md < M; ++md) {
			auto [c, v] = cpts[md];
			fcnt.add(tin[v], +1);
			fcnt.add(tout[v], -1);
			fsum.add(tin[v], +c);
			fsum.add(tout[v], -c);

			for (int q : queries[md]) {
				int64_t sum = fsum.get(tin[from[q]]) + fsum.get(tin[to[q]]) - 2 * fsum.get(tin[lca[q]]);
				int cnt0 = fcnt.get(tin[from[q]]) + fcnt.get(tin[to[q]]) - 2 * fcnt.get(tin[lca[q]]);
				if (sum <= silver[q]) {
					lo[q] = md;
					ans[q] = gold[q] - (cnt[q] - cnt0);
				} else {
					hi[q] = md - 1;
				}
			}
		}
		for (int i = 0; i < M; ++i) queries[i].clear();
	}

	for (int q = 0; q < Q; ++q) {
		cout << max(ans[q], -1) << '\n';
	}
	return 0;
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:93:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |  for (auto [c, v] : cpts) {
      |            ^
currencies.cpp:129:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |    auto [c, v] = cpts[md];
      |         ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 904 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 5 ms 860 KB Output is correct
12 Correct 5 ms 860 KB Output is correct
13 Correct 5 ms 1196 KB Output is correct
14 Correct 5 ms 1112 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 5 ms 860 KB Output is correct
17 Correct 6 ms 860 KB Output is correct
18 Correct 6 ms 884 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 4 ms 860 KB Output is correct
22 Correct 4 ms 856 KB Output is correct
23 Correct 4 ms 860 KB Output is correct
24 Correct 4 ms 860 KB Output is correct
25 Correct 4 ms 860 KB Output is correct
26 Correct 4 ms 856 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 4 ms 860 KB Output is correct
29 Correct 4 ms 860 KB Output is correct
30 Correct 5 ms 928 KB Output is correct
31 Correct 5 ms 860 KB Output is correct
32 Correct 5 ms 980 KB Output is correct
33 Correct 4 ms 1116 KB Output is correct
34 Correct 5 ms 1232 KB Output is correct
35 Correct 5 ms 1116 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 317 ms 27108 KB Output is correct
6 Correct 343 ms 29672 KB Output is correct
7 Correct 318 ms 28368 KB Output is correct
8 Correct 247 ms 24712 KB Output is correct
9 Correct 255 ms 24288 KB Output is correct
10 Correct 396 ms 33332 KB Output is correct
11 Correct 393 ms 33332 KB Output is correct
12 Correct 420 ms 33592 KB Output is correct
13 Correct 401 ms 33324 KB Output is correct
14 Correct 400 ms 33844 KB Output is correct
15 Correct 414 ms 44020 KB Output is correct
16 Correct 472 ms 44564 KB Output is correct
17 Correct 406 ms 43408 KB Output is correct
18 Correct 409 ms 33580 KB Output is correct
19 Correct 431 ms 33928 KB Output is correct
20 Correct 417 ms 33880 KB Output is correct
21 Correct 356 ms 33816 KB Output is correct
22 Correct 347 ms 33960 KB Output is correct
23 Correct 349 ms 34068 KB Output is correct
24 Correct 335 ms 33972 KB Output is correct
25 Correct 334 ms 33704 KB Output is correct
26 Correct 339 ms 33760 KB Output is correct
27 Correct 328 ms 33676 KB Output is correct
28 Correct 258 ms 33844 KB Output is correct
29 Correct 254 ms 32696 KB Output is correct
30 Correct 330 ms 32372 KB Output is correct
31 Correct 281 ms 32056 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 5 ms 1116 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 4 ms 1112 KB Output is correct
5 Correct 242 ms 36512 KB Output is correct
6 Correct 250 ms 35468 KB Output is correct
7 Correct 307 ms 32408 KB Output is correct
8 Correct 416 ms 45048 KB Output is correct
9 Correct 397 ms 44800 KB Output is correct
10 Correct 419 ms 44844 KB Output is correct
11 Correct 342 ms 44796 KB Output is correct
12 Correct 356 ms 45072 KB Output is correct
13 Correct 326 ms 44788 KB Output is correct
14 Correct 275 ms 44608 KB Output is correct
15 Correct 277 ms 44124 KB Output is correct
16 Correct 315 ms 44580 KB Output is correct
17 Correct 308 ms 44592 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 904 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 5 ms 860 KB Output is correct
12 Correct 5 ms 860 KB Output is correct
13 Correct 5 ms 1196 KB Output is correct
14 Correct 5 ms 1112 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 5 ms 860 KB Output is correct
17 Correct 6 ms 860 KB Output is correct
18 Correct 6 ms 884 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 4 ms 860 KB Output is correct
22 Correct 4 ms 856 KB Output is correct
23 Correct 4 ms 860 KB Output is correct
24 Correct 4 ms 860 KB Output is correct
25 Correct 4 ms 860 KB Output is correct
26 Correct 4 ms 856 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 4 ms 860 KB Output is correct
29 Correct 4 ms 860 KB Output is correct
30 Correct 5 ms 928 KB Output is correct
31 Correct 5 ms 860 KB Output is correct
32 Correct 5 ms 980 KB Output is correct
33 Correct 4 ms 1116 KB Output is correct
34 Correct 5 ms 1232 KB Output is correct
35 Correct 5 ms 1116 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 5 ms 860 KB Output is correct
38 Correct 5 ms 860 KB Output is correct
39 Correct 5 ms 860 KB Output is correct
40 Correct 317 ms 27108 KB Output is correct
41 Correct 343 ms 29672 KB Output is correct
42 Correct 318 ms 28368 KB Output is correct
43 Correct 247 ms 24712 KB Output is correct
44 Correct 255 ms 24288 KB Output is correct
45 Correct 396 ms 33332 KB Output is correct
46 Correct 393 ms 33332 KB Output is correct
47 Correct 420 ms 33592 KB Output is correct
48 Correct 401 ms 33324 KB Output is correct
49 Correct 400 ms 33844 KB Output is correct
50 Correct 414 ms 44020 KB Output is correct
51 Correct 472 ms 44564 KB Output is correct
52 Correct 406 ms 43408 KB Output is correct
53 Correct 409 ms 33580 KB Output is correct
54 Correct 431 ms 33928 KB Output is correct
55 Correct 417 ms 33880 KB Output is correct
56 Correct 356 ms 33816 KB Output is correct
57 Correct 347 ms 33960 KB Output is correct
58 Correct 349 ms 34068 KB Output is correct
59 Correct 335 ms 33972 KB Output is correct
60 Correct 334 ms 33704 KB Output is correct
61 Correct 339 ms 33760 KB Output is correct
62 Correct 328 ms 33676 KB Output is correct
63 Correct 258 ms 33844 KB Output is correct
64 Correct 254 ms 32696 KB Output is correct
65 Correct 330 ms 32372 KB Output is correct
66 Correct 281 ms 32056 KB Output is correct
67 Correct 1 ms 344 KB Output is correct
68 Correct 5 ms 1116 KB Output is correct
69 Correct 4 ms 1116 KB Output is correct
70 Correct 4 ms 1112 KB Output is correct
71 Correct 242 ms 36512 KB Output is correct
72 Correct 250 ms 35468 KB Output is correct
73 Correct 307 ms 32408 KB Output is correct
74 Correct 416 ms 45048 KB Output is correct
75 Correct 397 ms 44800 KB Output is correct
76 Correct 419 ms 44844 KB Output is correct
77 Correct 342 ms 44796 KB Output is correct
78 Correct 356 ms 45072 KB Output is correct
79 Correct 326 ms 44788 KB Output is correct
80 Correct 275 ms 44608 KB Output is correct
81 Correct 277 ms 44124 KB Output is correct
82 Correct 315 ms 44580 KB Output is correct
83 Correct 308 ms 44592 KB Output is correct
84 Correct 320 ms 25744 KB Output is correct
85 Correct 322 ms 23736 KB Output is correct
86 Correct 256 ms 22328 KB Output is correct
87 Correct 427 ms 33196 KB Output is correct
88 Correct 425 ms 33336 KB Output is correct
89 Correct 425 ms 33328 KB Output is correct
90 Correct 455 ms 33336 KB Output is correct
91 Correct 428 ms 33472 KB Output is correct
92 Correct 437 ms 40776 KB Output is correct
93 Correct 434 ms 43052 KB Output is correct
94 Correct 462 ms 33588 KB Output is correct
95 Correct 445 ms 33580 KB Output is correct
96 Correct 461 ms 33792 KB Output is correct
97 Correct 460 ms 33708 KB Output is correct
98 Correct 409 ms 33816 KB Output is correct
99 Correct 371 ms 33460 KB Output is correct
100 Correct 416 ms 33804 KB Output is correct
101 Correct 400 ms 33928 KB Output is correct
102 Correct 359 ms 34096 KB Output is correct
103 Correct 362 ms 34236 KB Output is correct
104 Correct 385 ms 34096 KB Output is correct
105 Correct 271 ms 31280 KB Output is correct
106 Correct 271 ms 33840 KB Output is correct
107 Correct 322 ms 31284 KB Output is correct
108 Correct 280 ms 31544 KB Output is correct