oj.uz

Submission #633520

# Submission time Handle Problem Language Result Execution time Memory
633520 2022-08-22T16:29:42 Z S920105123 Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 3239 ms 142928 KB 
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define all_of(v) (v).begin(), (v).end()
#define fi first
#define se second
const int MAXM = 100005;
const int MAXN = 505;
const int SIZE = 400;
const LL INF = (LL) 1e9 + 8763;
using namespace std;

struct Edge {
	int u, v;
	LL w;
};

struct DSU {
	// 1-based roll-back DSU
	struct Record {
		int x, y; // y is merged into x
	};
	int pa[MAXN], sz[MAXN];
	vector<Record> stk;
	void init(int n) {
		stk.clear();
		for (int i = 1; i <= n; i++) {
			pa[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x) {
		return x == pa[x] ? x : find(pa[x]);
	}
	int merge(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) {
			stk.push_back((Record){-1, -1});
			return 0;
		}
		if (sz[x] < sz[y]) swap(x, y);
		sz[x] += sz[y];
		pa[y] = x;
		stk.push_back((Record){x, y});
		return 1;
	}
	int same(int x, int y) {
		return find(x) == find(y);
	}
	void roll_back() {
		assert(!stk.empty());
		Record r = stk.back();
		stk.pop_back();
		if (r.x != -1) {
			pa[r.y] = r.y;
			sz[r.x] -= sz[r.y];
		}
	}
};

int n, m, sq;
Edge E[MAXM];
DSU D[MAXM / SIZE + 5];

int qn;
vector<int> X;

void compute(vector<int> &res) {
	int cnt = 0, pseudo = MAXM / SIZE + 4;
	D[pseudo].init(n);
	for (int i = 0; i < m; i++) {
		// stage 1
		int j, pre = i, last = pseudo;
		for (j = cnt - 1; j >= 0; j--) {
			if (D[j].same(E[i].u, E[i].v)) {
				break;
			}
			pre = j * SIZE;
			last = j;
		}
		
		// stage 2
		int op = 0;
		while (pre > 0) {
			op++;
			D[last].merge(E[pre - 1].u, E[pre - 1].v);
			if (D[last].same(E[i].u, E[i].v)) {
				break;
			}
			pre--;
		}
		res[i] = i - pre;
		for (int i = 0; i < op; i++) {
			D[last].roll_back();
		}
		
		// add E[i];
		if (i % SIZE == 0) {
			D[cnt++].init(n);
		}
		for (int j = 0; j < cnt; j++) {
			D[j].merge(E[i].u, E[i].v);
		}
	}
}

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

	cin >> n >> m;
	sq = (int)(sqrt(m) + 0.5);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		E[i] = (Edge){u, v, w};
	}
	sort(E, E + m, [&] (Edge e1, Edge e2) {
		return e1.w < e2.w;
	});
	cin >> qn;
	X.resize(qn);
	for (int i = 0; i < qn; i++) {
		cin >> X[i];
	}
		
	// compute
	vector<int> L(m), R(m);
	compute(L);
	reverse(E, E + m);
	compute(R);
	reverse(E, E + m);
	reverse(all_of(R));
		
	// make answer
	vector<PII> ev;
	for (int i = 0; i < m; i++) {
		int l = i - L[i] - 1, r = i + R[i] + 1, wl, wr;
		if (l < 0) {
			wl = -INF;
		}
		else {
			wl = (E[i].w + E[l].w) / 2 + 1;
		}
		if (r >= m) {
			wr = INF;
		}
		else {
			wr = (E[i].w + E[r].w) / 2;
		}
		
		int pl = lower_bound(all_of(X), wl) - X.begin();
		int pr = upper_bound(all_of(X), wr) - X.begin();
		ev.push_back(PII(pl, ~i));
		ev.push_back(PII(pr, i));
	}
	
	// sweep
	int ptr = 0;
	vector<int> all, active(m);
	vector<LL> ans(qn, 0);
	sort(all_of(ev));
	for (int i = 0; i < qn; i++) {
		while (ev[ptr].fi <= i) {
			int id = ev[ptr].se;
			if (ev[ptr].se < 0) {
				// insert
				id = ~id;
				assert(active[id] == 0);
				active[id] = 1;
				all.push_back(id);
			}
			else {
				assert(active[id] == 1);
				active[id] = 0;
			}
			ptr++;
		}
		
		// calc
		int j = 0;
		while (j < all.size()) {
			if (!active[all[j]]) {
				swap(all[j], all.back());
				all.pop_back();
				continue;
			}
			ans[i] += abs(E[all[j]].w - X[i]);
			j++;
		}
		assert(all.size() == n - 1);
	}
	for (int i = 0; i < qn; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:181:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |   while (j < all.size()) {
      |          ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from reconstruction.cpp:1:
reconstruction.cpp:190:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  190 |   assert(all.size() == n - 1);
      |          ~~~~~~~~~~~^~~~~~~~

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1344 KB Output is correct
9 Correct 1 ms 1340 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1344 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 1 ms 1344 KB Output is correct
14 Correct 1 ms 1340 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1236 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1980 ms 112228 KB Output is correct
21 Correct 1193 ms 112228 KB Output is correct
22 Correct 1303 ms 112596 KB Output is correct
23 Correct 1452 ms 112224 KB Output is correct
24 Correct 1729 ms 112324 KB Output is correct
25 Correct 1897 ms 112328 KB Output is correct
26 Correct 1985 ms 112200 KB Output is correct
27 Correct 1945 ms 112352 KB Output is correct
28 Correct 1921 ms 112260 KB Output is correct
29 Correct 1974 ms 112416 KB Output is correct
30 Correct 1994 ms 112344 KB Output is correct
31 Correct 1970 ms 112248 KB Output is correct
32 Correct 1949 ms 112332 KB Output is correct
33 Correct 1970 ms 112336 KB Output is correct
34 Correct 1972 ms 112368 KB Output is correct
35 Correct 1950 ms 112360 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 3041 ms 140708 KB Output is correct
5 Correct 2987 ms 140828 KB Output is correct
6 Correct 2991 ms 140708 KB Output is correct
7 Correct 1894 ms 142772 KB Output is correct
8 Correct 1655 ms 142928 KB Output is correct
9 Correct 1592 ms 142708 KB Output is correct
10 Correct 2840 ms 140688 KB Output is correct
11 Correct 1632 ms 142500 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1344 KB Output is correct
9 Correct 1 ms 1340 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1344 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 1 ms 1344 KB Output is correct
14 Correct 1 ms 1340 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1236 KB Output is correct
19 Correct 1 ms 1340 KB Output is correct
20 Correct 1327 ms 33136 KB Output is correct
21 Correct 1301 ms 33168 KB Output is correct
22 Correct 1312 ms 33140 KB Output is correct
23 Correct 1315 ms 33140 KB Output is correct
24 Correct 1315 ms 33120 KB Output is correct
25 Correct 1307 ms 33080 KB Output is correct
26 Correct 1299 ms 33016 KB Output is correct
27 Correct 1312 ms 33184 KB Output is correct
28 Correct 1304 ms 33232 KB Output is correct
29 Correct 1303 ms 33012 KB Output is correct
30 Correct 1327 ms 32976 KB Output is correct
31 Correct 1303 ms 32844 KB Output is correct
32 Correct 1300 ms 33484 KB Output is correct
33 Correct 1295 ms 32576 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1344 KB Output is correct
9 Correct 1 ms 1340 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1344 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 1 ms 1344 KB Output is correct
14 Correct 1 ms 1340 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1236 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1980 ms 112228 KB Output is correct
21 Correct 1193 ms 112228 KB Output is correct
22 Correct 1303 ms 112596 KB Output is correct
23 Correct 1452 ms 112224 KB Output is correct
24 Correct 1729 ms 112324 KB Output is correct
25 Correct 1897 ms 112328 KB Output is correct
26 Correct 1985 ms 112200 KB Output is correct
27 Correct 1945 ms 112352 KB Output is correct
28 Correct 1921 ms 112260 KB Output is correct
29 Correct 1974 ms 112416 KB Output is correct
30 Correct 1994 ms 112344 KB Output is correct
31 Correct 1970 ms 112248 KB Output is correct
32 Correct 1949 ms 112332 KB Output is correct
33 Correct 1970 ms 112336 KB Output is correct
34 Correct 1972 ms 112368 KB Output is correct
35 Correct 1950 ms 112360 KB Output is correct
36 Correct 1942 ms 112728 KB Output is correct
37 Correct 1144 ms 112624 KB Output is correct
38 Correct 1259 ms 112652 KB Output is correct
39 Correct 1456 ms 112548 KB Output is correct
40 Correct 1682 ms 112400 KB Output is correct
41 Correct 1846 ms 112516 KB Output is correct
42 Correct 1907 ms 112564 KB Output is correct
43 Correct 1925 ms 112560 KB Output is correct
44 Correct 1957 ms 112508 KB Output is correct
45 Correct 1919 ms 112560 KB Output is correct
46 Correct 1941 ms 112628 KB Output is correct
47 Correct 1949 ms 112676 KB Output is correct
48 Correct 1918 ms 112452 KB Output is correct
49 Correct 1946 ms 112548 KB Output is correct
50 Correct 1920 ms 112896 KB Output is correct
51 Correct 1938 ms 112580 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1344 KB Output is correct
9 Correct 1 ms 1340 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1344 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 1 ms 1344 KB Output is correct
14 Correct 1 ms 1340 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1236 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1980 ms 112228 KB Output is correct
21 Correct 1193 ms 112228 KB Output is correct
22 Correct 1303 ms 112596 KB Output is correct
23 Correct 1452 ms 112224 KB Output is correct
24 Correct 1729 ms 112324 KB Output is correct
25 Correct 1897 ms 112328 KB Output is correct
26 Correct 1985 ms 112200 KB Output is correct
27 Correct 1945 ms 112352 KB Output is correct
28 Correct 1921 ms 112260 KB Output is correct
29 Correct 1974 ms 112416 KB Output is correct
30 Correct 1994 ms 112344 KB Output is correct
31 Correct 1970 ms 112248 KB Output is correct
32 Correct 1949 ms 112332 KB Output is correct
33 Correct 1970 ms 112336 KB Output is correct
34 Correct 1972 ms 112368 KB Output is correct
35 Correct 1950 ms 112360 KB Output is correct
36 Correct 1 ms 1236 KB Output is correct
37 Correct 1 ms 1236 KB Output is correct
38 Correct 1 ms 1236 KB Output is correct
39 Correct 3041 ms 140708 KB Output is correct
40 Correct 2987 ms 140828 KB Output is correct
41 Correct 2991 ms 140708 KB Output is correct
42 Correct 1894 ms 142772 KB Output is correct
43 Correct 1655 ms 142928 KB Output is correct
44 Correct 1592 ms 142708 KB Output is correct
45 Correct 2840 ms 140688 KB Output is correct
46 Correct 1632 ms 142500 KB Output is correct
47 Correct 1 ms 1340 KB Output is correct
48 Correct 1327 ms 33136 KB Output is correct
49 Correct 1301 ms 33168 KB Output is correct
50 Correct 1312 ms 33140 KB Output is correct
51 Correct 1315 ms 33140 KB Output is correct
52 Correct 1315 ms 33120 KB Output is correct
53 Correct 1307 ms 33080 KB Output is correct
54 Correct 1299 ms 33016 KB Output is correct
55 Correct 1312 ms 33184 KB Output is correct
56 Correct 1304 ms 33232 KB Output is correct
57 Correct 1303 ms 33012 KB Output is correct
58 Correct 1327 ms 32976 KB Output is correct
59 Correct 1303 ms 32844 KB Output is correct
60 Correct 1300 ms 33484 KB Output is correct
61 Correct 1295 ms 32576 KB Output is correct
62 Correct 1942 ms 112728 KB Output is correct
63 Correct 1144 ms 112624 KB Output is correct
64 Correct 1259 ms 112652 KB Output is correct
65 Correct 1456 ms 112548 KB Output is correct
66 Correct 1682 ms 112400 KB Output is correct
67 Correct 1846 ms 112516 KB Output is correct
68 Correct 1907 ms 112564 KB Output is correct
69 Correct 1925 ms 112560 KB Output is correct
70 Correct 1957 ms 112508 KB Output is correct
71 Correct 1919 ms 112560 KB Output is correct
72 Correct 1941 ms 112628 KB Output is correct
73 Correct 1949 ms 112676 KB Output is correct
74 Correct 1918 ms 112452 KB Output is correct
75 Correct 1946 ms 112548 KB Output is correct
76 Correct 1920 ms 112896 KB Output is correct
77 Correct 1938 ms 112580 KB Output is correct
78 Correct 3239 ms 138232 KB Output is correct
79 Correct 2440 ms 140092 KB Output is correct
80 Correct 2549 ms 139128 KB Output is correct
81 Correct 2750 ms 138832 KB Output is correct
82 Correct 2983 ms 137668 KB Output is correct
83 Correct 3129 ms 137060 KB Output is correct
84 Correct 3216 ms 136968 KB Output is correct
85 Correct 3186 ms 137008 KB Output is correct
86 Correct 3181 ms 136448 KB Output is correct
87 Correct 3164 ms 138216 KB Output is correct
88 Correct 3225 ms 135872 KB Output is correct
89 Correct 3192 ms 135764 KB Output is correct
90 Correct 3165 ms 135728 KB Output is correct
91 Correct 3186 ms 135180 KB Output is correct
92 Correct 3166 ms 138192 KB Output is correct
93 Correct 3181 ms 135776 KB Output is correct