oj.uz

Submission #369807

# Submission time Handle Problem Language Result Execution time Memory
369807 2021-02-22T13:01:18 Z pavement Bridges (APIO19_bridges) C++17
100 / 100
 2991 ms 8652 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const int k = 600;
int N, M, Q, unusedidx, qbufidx, ubufidx, considx, cons2idx, t, a, b, r, s, w, rb, uidx, idx, idx2, sa, sb, lb, link[100005], sz[100005], U[100005], V[100005], W[100005], lt[100005], out[100005], cons[100005], cons2[100005];
bitset<100005> used;
ii unused[100005];
iii qbuf[100005], ubuf[100005];
stack<tuple<int, int, int, int, int> > rbst; 

int find(int x) {
	if (x == link[x]) return x;
	return find(link[x]);
}
 
void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (sz[b] > sz[a]) swap(a, b);
	rbst.emplace(a, b, sz[a], sz[b], link[b]);
	sz[a] += sz[b];
	link[b] = a;
}
 
void rollback() {
	assert(!rbst.empty());
	tie(a, b, sa, sb, lb) = rbst.top();
	rbst.pop();
	sz[a] = sa;
	sz[b] = sb;
	link[b] = lb;
}
 
inline void read(int &v) {
    v = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    for (; ch >= '0' && ch <= '9'; ch = getchar_unlocked())
        v = (v << 1) + (v << 3) + (ch & 15);
}
 
void proc() {
	uidx = unusedidx = 0;
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	while (!rbst.empty()) rbst.pop();
	used.reset();
	for (int j = 0; j < ubufidx; j++) used[g0(ubuf[j])] = 1;
	for (int j = 1; j <= M; j++)
		if (!used[j]) unused[unusedidx++] = mp(W[j], j);
	sort(unused, unused + unusedidx, greater<ii>());
	sort(qbuf, qbuf + qbufidx, greater<iii>());
	for (int j = 0; j < qbufidx; j++) {
		tie(w, s, idx) = qbuf[j];
		while (uidx < unusedidx && unused[uidx].first >= w) {
			if (find(U[unused[uidx].second]) != find(V[unused[uidx].second])) unite(U[unused[uidx].second], V[unused[uidx].second]);
			uidx++;
		}
		considx = cons2idx = 0;
		for (int k = 0; k < ubufidx; k++) {
			tie(b, r, idx2) = ubuf[k];
			if (idx > idx2) {
				lt[b] = r;
				cons[considx++] = b;
			} else {
				if (lt[b]) continue;
				cons2[cons2idx++] = b;
			}
		}
		rb = 0;
		for (int k = 0; k < considx; k++) {
			if (lt[cons[k]] >= w && find(U[cons[k]]) != find(V[cons[k]])) {
				unite(U[cons[k]], V[cons[k]]);
				rb++;
			}
		}
		for (int k = 0; k < considx; k++)
			lt[cons[k]] = 0;
		for (int k = 0; k < cons2idx; k++) {
			if (W[cons2[k]] >= w && find(U[cons2[k]]) != find(V[cons2[k]])) {
				unite(U[cons2[k]], V[cons2[k]]);
				rb++;
			}
		}
		out[idx] = sz[find(s)];
		while (rb--) rollback();
	}
	for (int j = 0; j < ubufidx; j++) W[g0(ubuf[j])] = g1(ubuf[j]);
	qbufidx = ubufidx = 0;
}

main() {
	read(N);
	read(M);
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= M; i++) {
		read(U[i]);
		read(V[i]);
		read(W[i]);
	}
	read(Q);
	for (int i = 1; i <= Q; i++) {
		read(t);
		if (t == 1) {
			read(b);
			read(r);
			ubuf[ubufidx++] = mt(b, r, i);
		} else {
			read(s);
			read(w);
			qbuf[qbufidx++] = mt(w, s, i);
		}
		if (qbufidx + ubufidx == k) proc();
	}
	proc();
	for (int i = 1; i <= Q; i++)
		if (out[i]) printf("%d\n", out[i]);
}

Compilation message

bridges.cpp:117:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 | main() {
      |      ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 21 ms 620 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 20 ms 748 KB Output is correct
6 Correct 17 ms 640 KB Output is correct
7 Correct 26 ms 492 KB Output is correct
8 Correct 24 ms 620 KB Output is correct
9 Correct 27 ms 492 KB Output is correct
10 Correct 25 ms 620 KB Output is correct
11 Correct 24 ms 620 KB Output is correct
12 Correct 27 ms 620 KB Output is correct
13 Correct 28 ms 620 KB Output is correct
14 Correct 27 ms 632 KB Output is correct
15 Correct 29 ms 620 KB Output is correct
16 Correct 30 ms 492 KB Output is correct
17 Correct 27 ms 492 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1704 ms 4084 KB Output is correct
2 Correct 1670 ms 4304 KB Output is correct
3 Correct 1658 ms 3936 KB Output is correct
4 Correct 1752 ms 4076 KB Output is correct
5 Correct 1702 ms 4208 KB Output is correct
6 Correct 2201 ms 4308 KB Output is correct
7 Correct 2192 ms 4488 KB Output is correct
8 Correct 2187 ms 4368 KB Output is correct
9 Correct 23 ms 1516 KB Output is correct
10 Correct 1431 ms 4316 KB Output is correct
11 Correct 1516 ms 4144 KB Output is correct
12 Correct 1492 ms 4392 KB Output is correct
13 Correct 1578 ms 4052 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1185 ms 3232 KB Output is correct
2 Correct 697 ms 2028 KB Output is correct
3 Correct 1361 ms 3412 KB Output is correct
4 Correct 1173 ms 3280 KB Output is correct
5 Correct 21 ms 1516 KB Output is correct
6 Correct 1291 ms 3504 KB Output is correct
7 Correct 1130 ms 3384 KB Output is correct
8 Correct 1035 ms 3412 KB Output is correct
9 Correct 907 ms 3428 KB Output is correct
10 Correct 865 ms 3496 KB Output is correct
11 Correct 932 ms 3136 KB Output is correct
12 Correct 855 ms 3204 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2482 ms 5376 KB Output is correct
2 Correct 21 ms 1644 KB Output is correct
3 Correct 213 ms 3180 KB Output is correct
4 Correct 124 ms 3052 KB Output is correct
5 Correct 2304 ms 5484 KB Output is correct
6 Correct 2380 ms 5480 KB Output is correct
7 Correct 2392 ms 5356 KB Output is correct
8 Correct 1219 ms 4036 KB Output is correct
9 Correct 1244 ms 4092 KB Output is correct
10 Correct 1237 ms 4160 KB Output is correct
11 Correct 1938 ms 4612 KB Output is correct
12 Correct 1915 ms 4624 KB Output is correct
13 Correct 1932 ms 5044 KB Output is correct
14 Correct 2016 ms 5328 KB Output is correct
15 Correct 2229 ms 5228 KB Output is correct
16 Correct 2486 ms 5216 KB Output is correct
17 Correct 2551 ms 5196 KB Output is correct
18 Correct 2589 ms 5260 KB Output is correct
19 Correct 2603 ms 5160 KB Output is correct
20 Correct 2165 ms 4996 KB Output is correct
21 Correct 2110 ms 5012 KB Output is correct
22 Correct 2403 ms 5312 KB Output is correct
23 Correct 2303 ms 4864 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1704 ms 4084 KB Output is correct
2 Correct 1670 ms 4304 KB Output is correct
3 Correct 1658 ms 3936 KB Output is correct
4 Correct 1752 ms 4076 KB Output is correct
5 Correct 1702 ms 4208 KB Output is correct
6 Correct 2201 ms 4308 KB Output is correct
7 Correct 2192 ms 4488 KB Output is correct
8 Correct 2187 ms 4368 KB Output is correct
9 Correct 23 ms 1516 KB Output is correct
10 Correct 1431 ms 4316 KB Output is correct
11 Correct 1516 ms 4144 KB Output is correct
12 Correct 1492 ms 4392 KB Output is correct
13 Correct 1578 ms 4052 KB Output is correct
14 Correct 1185 ms 3232 KB Output is correct
15 Correct 697 ms 2028 KB Output is correct
16 Correct 1361 ms 3412 KB Output is correct
17 Correct 1173 ms 3280 KB Output is correct
18 Correct 21 ms 1516 KB Output is correct
19 Correct 1291 ms 3504 KB Output is correct
20 Correct 1130 ms 3384 KB Output is correct
21 Correct 1035 ms 3412 KB Output is correct
22 Correct 907 ms 3428 KB Output is correct
23 Correct 865 ms 3496 KB Output is correct
24 Correct 932 ms 3136 KB Output is correct
25 Correct 855 ms 3204 KB Output is correct
26 Correct 1688 ms 3948 KB Output is correct
27 Correct 2015 ms 4084 KB Output is correct
28 Correct 1824 ms 4088 KB Output is correct
29 Correct 1538 ms 4028 KB Output is correct
30 Correct 1957 ms 4104 KB Output is correct
31 Correct 1988 ms 4084 KB Output is correct
32 Correct 1969 ms 4048 KB Output is correct
33 Correct 1765 ms 4144 KB Output is correct
34 Correct 1743 ms 4128 KB Output is correct
35 Correct 1747 ms 4036 KB Output is correct
36 Correct 1515 ms 4156 KB Output is correct
37 Correct 1536 ms 4224 KB Output is correct
38 Correct 1498 ms 4168 KB Output is correct
39 Correct 1329 ms 4104 KB Output is correct
40 Correct 1290 ms 4232 KB Output is correct
41 Correct 1308 ms 4076 KB Output is correct
42 Correct 1264 ms 3956 KB Output is correct
43 Correct 1278 ms 4196 KB Output is correct
44 Correct 1315 ms 3880 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 21 ms 620 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 20 ms 748 KB Output is correct
6 Correct 17 ms 640 KB Output is correct
7 Correct 26 ms 492 KB Output is correct
8 Correct 24 ms 620 KB Output is correct
9 Correct 27 ms 492 KB Output is correct
10 Correct 25 ms 620 KB Output is correct
11 Correct 24 ms 620 KB Output is correct
12 Correct 27 ms 620 KB Output is correct
13 Correct 28 ms 620 KB Output is correct
14 Correct 27 ms 632 KB Output is correct
15 Correct 29 ms 620 KB Output is correct
16 Correct 30 ms 492 KB Output is correct
17 Correct 27 ms 492 KB Output is correct
18 Correct 1704 ms 4084 KB Output is correct
19 Correct 1670 ms 4304 KB Output is correct
20 Correct 1658 ms 3936 KB Output is correct
21 Correct 1752 ms 4076 KB Output is correct
22 Correct 1702 ms 4208 KB Output is correct
23 Correct 2201 ms 4308 KB Output is correct
24 Correct 2192 ms 4488 KB Output is correct
25 Correct 2187 ms 4368 KB Output is correct
26 Correct 23 ms 1516 KB Output is correct
27 Correct 1431 ms 4316 KB Output is correct
28 Correct 1516 ms 4144 KB Output is correct
29 Correct 1492 ms 4392 KB Output is correct
30 Correct 1578 ms 4052 KB Output is correct
31 Correct 1185 ms 3232 KB Output is correct
32 Correct 697 ms 2028 KB Output is correct
33 Correct 1361 ms 3412 KB Output is correct
34 Correct 1173 ms 3280 KB Output is correct
35 Correct 21 ms 1516 KB Output is correct
36 Correct 1291 ms 3504 KB Output is correct
37 Correct 1130 ms 3384 KB Output is correct
38 Correct 1035 ms 3412 KB Output is correct
39 Correct 907 ms 3428 KB Output is correct
40 Correct 865 ms 3496 KB Output is correct
41 Correct 932 ms 3136 KB Output is correct
42 Correct 855 ms 3204 KB Output is correct
43 Correct 2482 ms 5376 KB Output is correct
44 Correct 21 ms 1644 KB Output is correct
45 Correct 213 ms 3180 KB Output is correct
46 Correct 124 ms 3052 KB Output is correct
47 Correct 2304 ms 5484 KB Output is correct
48 Correct 2380 ms 5480 KB Output is correct
49 Correct 2392 ms 5356 KB Output is correct
50 Correct 1219 ms 4036 KB Output is correct
51 Correct 1244 ms 4092 KB Output is correct
52 Correct 1237 ms 4160 KB Output is correct
53 Correct 1938 ms 4612 KB Output is correct
54 Correct 1915 ms 4624 KB Output is correct
55 Correct 1932 ms 5044 KB Output is correct
56 Correct 2016 ms 5328 KB Output is correct
57 Correct 2229 ms 5228 KB Output is correct
58 Correct 2486 ms 5216 KB Output is correct
59 Correct 2551 ms 5196 KB Output is correct
60 Correct 2589 ms 5260 KB Output is correct
61 Correct 2603 ms 5160 KB Output is correct
62 Correct 2165 ms 4996 KB Output is correct
63 Correct 2110 ms 5012 KB Output is correct
64 Correct 2403 ms 5312 KB Output is correct
65 Correct 2303 ms 4864 KB Output is correct
66 Correct 1688 ms 3948 KB Output is correct
67 Correct 2015 ms 4084 KB Output is correct
68 Correct 1824 ms 4088 KB Output is correct
69 Correct 1538 ms 4028 KB Output is correct
70 Correct 1957 ms 4104 KB Output is correct
71 Correct 1988 ms 4084 KB Output is correct
72 Correct 1969 ms 4048 KB Output is correct
73 Correct 1765 ms 4144 KB Output is correct
74 Correct 1743 ms 4128 KB Output is correct
75 Correct 1747 ms 4036 KB Output is correct
76 Correct 1515 ms 4156 KB Output is correct
77 Correct 1536 ms 4224 KB Output is correct
78 Correct 1498 ms 4168 KB Output is correct
79 Correct 1329 ms 4104 KB Output is correct
80 Correct 1290 ms 4232 KB Output is correct
81 Correct 1308 ms 4076 KB Output is correct
82 Correct 1264 ms 3956 KB Output is correct
83 Correct 1278 ms 4196 KB Output is correct
84 Correct 1315 ms 3880 KB Output is correct
85 Correct 2763 ms 8576 KB Output is correct
86 Correct 232 ms 4772 KB Output is correct
87 Correct 138 ms 4844 KB Output is correct
88 Correct 2756 ms 7040 KB Output is correct
89 Correct 2772 ms 8620 KB Output is correct
90 Correct 2750 ms 7148 KB Output is correct
91 Correct 1806 ms 6424 KB Output is correct
92 Correct 1777 ms 6272 KB Output is correct
93 Correct 2253 ms 6380 KB Output is correct
94 Correct 2263 ms 7332 KB Output is correct
95 Correct 2240 ms 7468 KB Output is correct
96 Correct 2318 ms 7404 KB Output is correct
97 Correct 2513 ms 7080 KB Output is correct
98 Correct 2561 ms 6752 KB Output is correct
99 Correct 2789 ms 8588 KB Output is correct
100 Correct 2796 ms 8560 KB Output is correct
101 Correct 2936 ms 8620 KB Output is correct
102 Correct 2991 ms 8652 KB Output is correct
103 Correct 2627 ms 7548 KB Output is correct
104 Correct 2615 ms 7924 KB Output is correct
105 Correct 2280 ms 7392 KB Output is correct
106 Correct 1930 ms 7276 KB Output is correct
107 Correct 2227 ms 7700 KB Output is correct
108 Correct 2680 ms 8116 KB Output is correct
109 Correct 2543 ms 6156 KB Output is correct