oj.uz

Submission #715265

# Submission time Handle Problem Language Result Execution time Memory
715265 2023-03-26T10:02:33 Z hollwo_pelw Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 1243 ms 28472 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 505, M = 1e5 + 5;

struct edge_t {
	int u, v, w;
} ed[M];

int n, m, q, par[N], pi[N], l[M], r[M];
vector<pair<int, int>> adj[N];

void Hollwo_Pelw(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> ed[i].u >> ed[i].v >> ed[i].w;
	}
	sort(ed + 1, ed + m + 1, [&](const edge_t &x, const edge_t &y){
		return x.w < y.w;
	});

	auto add = [&](int i) {
		// cout << "add " << ed[i].u << ' ' << ed[i].v << ' ' << ed[i].w << '\n';
		adj[ed[i].u].emplace_back(ed[i].v, i);
		adj[ed[i].v].emplace_back(ed[i].u, i);
	};
	auto rem = [&](int i) {
		// cout << "del " << ed[i].u << ' ' << ed[i].v << ' ' << ed[i].w << '\n';
		adj[ed[i].u].erase(find(adj[ed[i].u].begin(), adj[ed[i].u].end(), pair{ed[i].v, i}));
		adj[ed[i].v].erase(find(adj[ed[i].v].begin(), adj[ed[i].v].end(), pair{ed[i].u, i}));
	};
	for (int i = 1; i <= m; i++) {
		int u = ed[i].u, v = ed[i].v;
		// bfs find cycle
		queue<int> q;
		q.push(u), par[u] = pi[u] = 0;
		memset(par, -1, sizeof par);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto [v, i] : adj[u]) {
				if (par[v] == -1)
					par[v] = u, pi[v] = i, q.push(v);
			}
		}
		if (par[v] != -1) {
			int j = pi[v];
			for (int s = v; s != u; s = par[s])
				j = min(j, pi[s]);
			r[j] = (ed[i].w + ed[j].w) / 2;
			l[i] = r[j] + 1, r[i] = 2e9, rem(j);
		} else {
			l[i] = 0, r[i] = 2e9;
		}
		add(i);
	}

	vector<pair<int, int>> upd;
	for (int i = 1; i <= m; i++) {
		if (l[i] <= r[i]) {
			upd.emplace_back(l[i], i), upd.emplace_back(r[i] + 1, -i);
			// cout << "ACTIVE " << l[i] << ' ' << r[i] << " -> " << i << '\n';
		}
	}
	sort(upd.begin(), upd.end());

	multiset<int> L, R;
	long long suml = 0, sumr = 0;

	cin >> q;
	for (int i = 1, j = 0, x; i <= q; i++) {
		cin >> x;
		for (; j < (int) upd.size() && upd[j].first <= x; j ++) {
			int id = upd[j].second;
			if (id < 0) {
				// cout << "REM " << id << '\n';
				id = -id;
				if (L.find(ed[id].w) != L.end()) {
					L.erase(L.find(ed[id].w)), suml -= ed[id].w;
				} else {
					R.erase(R.find(ed[id].w)), sumr -= ed[id].w;
				}
			} else {
				// cout << "ADD " << id << '\n';
				suml += ed[id].w;
				L.insert(ed[id].w);
			}
		}
		// exchange
		while (!L.empty() && *--L.end() > x) {
			int v = *--L.end();
			suml -= v, sumr += v;
			R.insert(v);
			L.erase(--L.end());
		}
		while (!R.empty() && *R.begin() <= x) {
			int v = *R.begin();
			suml += v, sumr -= v;
			L.insert(v);
			R.erase(R.begin());
		}
		// cout << "QUERY " << x << '\n';
		// cout << suml << ' ' << L.size() << '\n';
		// cout << sumr << ' ' << R.size() << '\n';
		cout << (long long) L.size() * x - suml + sumr - (long long) R.size() * x << '\n';
	}


}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1020 ms 4540 KB Output is correct
21 Correct 523 ms 6280 KB Output is correct
22 Correct 868 ms 6156 KB Output is correct
23 Correct 956 ms 6320 KB Output is correct
24 Correct 994 ms 6272 KB Output is correct
25 Correct 1000 ms 6192 KB Output is correct
26 Correct 1061 ms 6188 KB Output is correct
27 Correct 1078 ms 6312 KB Output is correct
28 Correct 1043 ms 6184 KB Output is correct
29 Correct 1033 ms 4412 KB Output is correct
30 Correct 1006 ms 6388 KB Output is correct
31 Correct 1016 ms 6132 KB Output is correct
32 Correct 1018 ms 6160 KB Output is correct
33 Correct 1043 ms 6200 KB Output is correct
34 Correct 1037 ms 4212 KB Output is correct
35 Correct 1036 ms 6260 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 941 ms 24708 KB Output is correct
5 Correct 935 ms 26428 KB Output is correct
6 Correct 959 ms 26384 KB Output is correct
7 Correct 307 ms 28228 KB Output is correct
8 Correct 289 ms 28436 KB Output is correct
9 Correct 277 ms 28396 KB Output is correct
10 Correct 910 ms 26560 KB Output is correct
11 Correct 265 ms 28472 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 188 ms 12616 KB Output is correct
21 Correct 194 ms 22464 KB Output is correct
22 Correct 192 ms 22452 KB Output is correct
23 Correct 200 ms 22312 KB Output is correct
24 Correct 199 ms 22452 KB Output is correct
25 Correct 197 ms 22352 KB Output is correct
26 Correct 191 ms 22332 KB Output is correct
27 Correct 184 ms 22348 KB Output is correct
28 Correct 193 ms 22300 KB Output is correct
29 Correct 199 ms 22324 KB Output is correct
30 Correct 201 ms 22476 KB Output is correct
31 Correct 198 ms 22196 KB Output is correct
32 Correct 186 ms 22832 KB Output is correct
33 Correct 190 ms 22232 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1020 ms 4540 KB Output is correct
21 Correct 523 ms 6280 KB Output is correct
22 Correct 868 ms 6156 KB Output is correct
23 Correct 956 ms 6320 KB Output is correct
24 Correct 994 ms 6272 KB Output is correct
25 Correct 1000 ms 6192 KB Output is correct
26 Correct 1061 ms 6188 KB Output is correct
27 Correct 1078 ms 6312 KB Output is correct
28 Correct 1043 ms 6184 KB Output is correct
29 Correct 1033 ms 4412 KB Output is correct
30 Correct 1006 ms 6388 KB Output is correct
31 Correct 1016 ms 6132 KB Output is correct
32 Correct 1018 ms 6160 KB Output is correct
33 Correct 1043 ms 6200 KB Output is correct
34 Correct 1037 ms 4212 KB Output is correct
35 Correct 1036 ms 6260 KB Output is correct
36 Correct 1044 ms 6464 KB Output is correct
37 Correct 556 ms 6512 KB Output is correct
38 Correct 885 ms 6492 KB Output is correct
39 Correct 972 ms 6432 KB Output is correct
40 Correct 1031 ms 6436 KB Output is correct
41 Correct 1029 ms 6556 KB Output is correct
42 Correct 1038 ms 6428 KB Output is correct
43 Correct 1077 ms 6460 KB Output is correct
44 Correct 1050 ms 6372 KB Output is correct
45 Correct 981 ms 4916 KB Output is correct
46 Correct 1046 ms 6312 KB Output is correct
47 Correct 1065 ms 6424 KB Output is correct
48 Correct 1112 ms 6376 KB Output is correct
49 Correct 1132 ms 6320 KB Output is correct
50 Correct 1014 ms 4780 KB Output is correct
51 Correct 1032 ms 6420 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1020 ms 4540 KB Output is correct
21 Correct 523 ms 6280 KB Output is correct
22 Correct 868 ms 6156 KB Output is correct
23 Correct 956 ms 6320 KB Output is correct
24 Correct 994 ms 6272 KB Output is correct
25 Correct 1000 ms 6192 KB Output is correct
26 Correct 1061 ms 6188 KB Output is correct
27 Correct 1078 ms 6312 KB Output is correct
28 Correct 1043 ms 6184 KB Output is correct
29 Correct 1033 ms 4412 KB Output is correct
30 Correct 1006 ms 6388 KB Output is correct
31 Correct 1016 ms 6132 KB Output is correct
32 Correct 1018 ms 6160 KB Output is correct
33 Correct 1043 ms 6200 KB Output is correct
34 Correct 1037 ms 4212 KB Output is correct
35 Correct 1036 ms 6260 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 941 ms 24708 KB Output is correct
40 Correct 935 ms 26428 KB Output is correct
41 Correct 959 ms 26384 KB Output is correct
42 Correct 307 ms 28228 KB Output is correct
43 Correct 289 ms 28436 KB Output is correct
44 Correct 277 ms 28396 KB Output is correct
45 Correct 910 ms 26560 KB Output is correct
46 Correct 265 ms 28472 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 188 ms 12616 KB Output is correct
49 Correct 194 ms 22464 KB Output is correct
50 Correct 192 ms 22452 KB Output is correct
51 Correct 200 ms 22312 KB Output is correct
52 Correct 199 ms 22452 KB Output is correct
53 Correct 197 ms 22352 KB Output is correct
54 Correct 191 ms 22332 KB Output is correct
55 Correct 184 ms 22348 KB Output is correct
56 Correct 193 ms 22300 KB Output is correct
57 Correct 199 ms 22324 KB Output is correct
58 Correct 201 ms 22476 KB Output is correct
59 Correct 198 ms 22196 KB Output is correct
60 Correct 186 ms 22832 KB Output is correct
61 Correct 190 ms 22232 KB Output is correct
62 Correct 1044 ms 6464 KB Output is correct
63 Correct 556 ms 6512 KB Output is correct
64 Correct 885 ms 6492 KB Output is correct
65 Correct 972 ms 6432 KB Output is correct
66 Correct 1031 ms 6436 KB Output is correct
67 Correct 1029 ms 6556 KB Output is correct
68 Correct 1038 ms 6428 KB Output is correct
69 Correct 1077 ms 6460 KB Output is correct
70 Correct 1050 ms 6372 KB Output is correct
71 Correct 981 ms 4916 KB Output is correct
72 Correct 1046 ms 6312 KB Output is correct
73 Correct 1065 ms 6424 KB Output is correct
74 Correct 1112 ms 6376 KB Output is correct
75 Correct 1132 ms 6320 KB Output is correct
76 Correct 1014 ms 4780 KB Output is correct
77 Correct 1032 ms 6420 KB Output is correct
78 Correct 1234 ms 25440 KB Output is correct
79 Correct 707 ms 27440 KB Output is correct
80 Correct 1059 ms 26584 KB Output is correct
81 Correct 1161 ms 26524 KB Output is correct
82 Correct 1240 ms 25568 KB Output is correct
83 Correct 1208 ms 25480 KB Output is correct
84 Correct 1243 ms 25612 KB Output is correct
85 Correct 1229 ms 25548 KB Output is correct
86 Correct 1210 ms 25468 KB Output is correct
87 Correct 1151 ms 25696 KB Output is correct
88 Correct 1229 ms 25552 KB Output is correct
89 Correct 1221 ms 25476 KB Output is correct
90 Correct 1213 ms 25600 KB Output is correct
91 Correct 1231 ms 25304 KB Output is correct
92 Correct 1155 ms 26684 KB Output is correct
93 Correct 1193 ms 26540 KB Output is correct