# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
677923 |
2023-01-04T16:30:09 Z |
FedShat |
Bridges (APIO19_bridges) |
C++17 |
|
2660 ms |
12160 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;
template<class T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
#ifdef __APPLE__
#include "../../debug.h"
#else
#define debug(...) 42
#endif
struct DSU {
vector<int> p, sz;
vector<array<int, 4>> rb; // v, u, p[v], sz[u]
DSU(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.resize(n, 1);
}
int get(int v) {
if (p[v] == v) {
return v;
}
return get(p[v]);
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v) {
return;
}
if (sz[u] < sz[v]) {
swap(u, v);
}
rb.push_back({v, u, p[v], sz[u]});
p[v] = u;
sz[u] += sz[v];
}
// void print() {
// for (int i = 0; i < (int) p.size(); ++i) {
// cout << p[i] + 1 << " " << i + 1 << "\n";
// }
// }
void rollback(int x) {
while ((int) rb.size() > x) {
auto [v, u, pv, szu] = rb.back();
rb.pop_back();
p[v] = pv;
sz[u] = szu;
}
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#endif
int n, m;
cin >> n >> m;
vector<array<int, 3>> ed(m);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u;
--v;
ed[i] = {w, u, v};
}
int q;
cin >> q;
vector<array<int, 3>> qq;
for (int i = 0; i < q; ++i) {
int t, u, w;
cin >> t >> u >> w;
--u;
qq.push_back({t, u, w});
}
constexpr int K = 1100;
vector<int> ans(q, -1);
for (int i = 0; i < q; i += K) {
vector<bool> bad(m);
vector<int> rebra;
rebra.reserve(K);
auto edd = ed;
vector<array<int, 4>> ev;
ev.reserve(K + m);
for (int j = i; j < min(q, i + K); ++j) {
auto [t, u, w] = qq[j];
if (t == 1) {
bad[u] = 1;
edd[u][0] = w;
rebra.push_back(j);
} else {
ev.push_back({w, 0, u, j});
}
}
sort(rebra.begin(), rebra.end(), [&](int i, int j) {
return qq[i][1] < qq[j][1] || (qq[i][1] == qq[j][1] && i < j);
});
// for (int i : rebra) {
// cout << qq[i][1] + 1 << " " << qq[i][2] << "\n";
// }
for (int j = 0; j < m; ++j) {
auto [w, u, v] = ed[j];
if (!bad[j]) {
ev.push_back({w, 1, u, v});
}
}
sort(ev.rbegin(), ev.rend());
DSU d(n);
for (auto [w, t, u, v] : ev) {
if (t == 0) {
int kek = d.rb.size();
// if (v == 11) {
// cout << "huy\n";
// }
for (int k = 0; k < (int) rebra.size();) {
int bebra = k;
int ves = -1;
while (bebra < (int) rebra.size() && qq[rebra[bebra]][1] == qq[rebra[k]][1]) {
if (rebra[bebra] < v) {
ves = qq[rebra[bebra]][2];
}
++bebra;
}
int nomer = qq[rebra[k]][1];
if (ves == -1) {
ves = ed[nomer][0];
}
// debug(d.sz[d.get(u)]);
if (w <= ves) {
// if (v == 11) {
// d.print();
// }
d.unite(ed[nomer][1], ed[nomer][2]);
}
k = bebra;
}
ans[v] = d.sz[d.get(u)];
d.rollback(kek);
} else {
d.unite(u, v);
}
}
ed = edd;
}
for (int i : ans) {
if (i != -1) {
cout << i << "\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
43 ms |
716 KB |
Output is correct |
4 |
Correct |
4 ms |
716 KB |
Output is correct |
5 |
Correct |
19 ms |
724 KB |
Output is correct |
6 |
Correct |
18 ms |
732 KB |
Output is correct |
7 |
Correct |
19 ms |
596 KB |
Output is correct |
8 |
Correct |
20 ms |
724 KB |
Output is correct |
9 |
Correct |
21 ms |
648 KB |
Output is correct |
10 |
Correct |
21 ms |
732 KB |
Output is correct |
11 |
Correct |
21 ms |
724 KB |
Output is correct |
12 |
Correct |
21 ms |
712 KB |
Output is correct |
13 |
Correct |
25 ms |
720 KB |
Output is correct |
14 |
Correct |
24 ms |
688 KB |
Output is correct |
15 |
Correct |
23 ms |
724 KB |
Output is correct |
16 |
Correct |
24 ms |
652 KB |
Output is correct |
17 |
Correct |
22 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1280 ms |
9000 KB |
Output is correct |
2 |
Correct |
1308 ms |
8812 KB |
Output is correct |
3 |
Correct |
1285 ms |
8816 KB |
Output is correct |
4 |
Correct |
1307 ms |
9108 KB |
Output is correct |
5 |
Correct |
1346 ms |
8948 KB |
Output is correct |
6 |
Correct |
1813 ms |
8680 KB |
Output is correct |
7 |
Correct |
1866 ms |
8736 KB |
Output is correct |
8 |
Correct |
1788 ms |
8880 KB |
Output is correct |
9 |
Correct |
33 ms |
3388 KB |
Output is correct |
10 |
Correct |
1366 ms |
7804 KB |
Output is correct |
11 |
Correct |
1352 ms |
7792 KB |
Output is correct |
12 |
Correct |
1111 ms |
8584 KB |
Output is correct |
13 |
Correct |
1066 ms |
8916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
944 ms |
6840 KB |
Output is correct |
2 |
Correct |
708 ms |
4208 KB |
Output is correct |
3 |
Correct |
1115 ms |
6696 KB |
Output is correct |
4 |
Correct |
929 ms |
6976 KB |
Output is correct |
5 |
Correct |
38 ms |
3388 KB |
Output is correct |
6 |
Correct |
1075 ms |
6864 KB |
Output is correct |
7 |
Correct |
870 ms |
6872 KB |
Output is correct |
8 |
Correct |
784 ms |
6756 KB |
Output is correct |
9 |
Correct |
620 ms |
6988 KB |
Output is correct |
10 |
Correct |
588 ms |
6896 KB |
Output is correct |
11 |
Correct |
628 ms |
6836 KB |
Output is correct |
12 |
Correct |
570 ms |
6728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1501 ms |
11956 KB |
Output is correct |
2 |
Correct |
33 ms |
3392 KB |
Output is correct |
3 |
Correct |
158 ms |
6276 KB |
Output is correct |
4 |
Correct |
186 ms |
6408 KB |
Output is correct |
5 |
Correct |
1766 ms |
10516 KB |
Output is correct |
6 |
Correct |
1409 ms |
12060 KB |
Output is correct |
7 |
Correct |
1749 ms |
10400 KB |
Output is correct |
8 |
Correct |
727 ms |
8972 KB |
Output is correct |
9 |
Correct |
696 ms |
9036 KB |
Output is correct |
10 |
Correct |
715 ms |
8724 KB |
Output is correct |
11 |
Correct |
1086 ms |
10532 KB |
Output is correct |
12 |
Correct |
1074 ms |
10448 KB |
Output is correct |
13 |
Correct |
1096 ms |
10316 KB |
Output is correct |
14 |
Correct |
1870 ms |
10464 KB |
Output is correct |
15 |
Correct |
1817 ms |
10384 KB |
Output is correct |
16 |
Correct |
1548 ms |
11916 KB |
Output is correct |
17 |
Correct |
1684 ms |
11844 KB |
Output is correct |
18 |
Correct |
1603 ms |
11940 KB |
Output is correct |
19 |
Correct |
1575 ms |
11952 KB |
Output is correct |
20 |
Correct |
1278 ms |
10744 KB |
Output is correct |
21 |
Correct |
1409 ms |
10668 KB |
Output is correct |
22 |
Correct |
1521 ms |
11520 KB |
Output is correct |
23 |
Correct |
1697 ms |
9276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1280 ms |
9000 KB |
Output is correct |
2 |
Correct |
1308 ms |
8812 KB |
Output is correct |
3 |
Correct |
1285 ms |
8816 KB |
Output is correct |
4 |
Correct |
1307 ms |
9108 KB |
Output is correct |
5 |
Correct |
1346 ms |
8948 KB |
Output is correct |
6 |
Correct |
1813 ms |
8680 KB |
Output is correct |
7 |
Correct |
1866 ms |
8736 KB |
Output is correct |
8 |
Correct |
1788 ms |
8880 KB |
Output is correct |
9 |
Correct |
33 ms |
3388 KB |
Output is correct |
10 |
Correct |
1366 ms |
7804 KB |
Output is correct |
11 |
Correct |
1352 ms |
7792 KB |
Output is correct |
12 |
Correct |
1111 ms |
8584 KB |
Output is correct |
13 |
Correct |
1066 ms |
8916 KB |
Output is correct |
14 |
Correct |
944 ms |
6840 KB |
Output is correct |
15 |
Correct |
708 ms |
4208 KB |
Output is correct |
16 |
Correct |
1115 ms |
6696 KB |
Output is correct |
17 |
Correct |
929 ms |
6976 KB |
Output is correct |
18 |
Correct |
38 ms |
3388 KB |
Output is correct |
19 |
Correct |
1075 ms |
6864 KB |
Output is correct |
20 |
Correct |
870 ms |
6872 KB |
Output is correct |
21 |
Correct |
784 ms |
6756 KB |
Output is correct |
22 |
Correct |
620 ms |
6988 KB |
Output is correct |
23 |
Correct |
588 ms |
6896 KB |
Output is correct |
24 |
Correct |
628 ms |
6836 KB |
Output is correct |
25 |
Correct |
570 ms |
6728 KB |
Output is correct |
26 |
Correct |
1366 ms |
8956 KB |
Output is correct |
27 |
Correct |
1735 ms |
8792 KB |
Output is correct |
28 |
Correct |
1401 ms |
8860 KB |
Output is correct |
29 |
Correct |
1128 ms |
8980 KB |
Output is correct |
30 |
Correct |
1659 ms |
8784 KB |
Output is correct |
31 |
Correct |
2273 ms |
8668 KB |
Output is correct |
32 |
Correct |
1990 ms |
8888 KB |
Output is correct |
33 |
Correct |
1560 ms |
9048 KB |
Output is correct |
34 |
Correct |
1429 ms |
8968 KB |
Output is correct |
35 |
Correct |
1463 ms |
8948 KB |
Output is correct |
36 |
Correct |
1174 ms |
8884 KB |
Output is correct |
37 |
Correct |
1127 ms |
8884 KB |
Output is correct |
38 |
Correct |
1316 ms |
8952 KB |
Output is correct |
39 |
Correct |
1028 ms |
8952 KB |
Output is correct |
40 |
Correct |
1077 ms |
8800 KB |
Output is correct |
41 |
Correct |
1045 ms |
8820 KB |
Output is correct |
42 |
Correct |
1054 ms |
8784 KB |
Output is correct |
43 |
Correct |
1097 ms |
8760 KB |
Output is correct |
44 |
Correct |
910 ms |
8792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
43 ms |
716 KB |
Output is correct |
4 |
Correct |
4 ms |
716 KB |
Output is correct |
5 |
Correct |
19 ms |
724 KB |
Output is correct |
6 |
Correct |
18 ms |
732 KB |
Output is correct |
7 |
Correct |
19 ms |
596 KB |
Output is correct |
8 |
Correct |
20 ms |
724 KB |
Output is correct |
9 |
Correct |
21 ms |
648 KB |
Output is correct |
10 |
Correct |
21 ms |
732 KB |
Output is correct |
11 |
Correct |
21 ms |
724 KB |
Output is correct |
12 |
Correct |
21 ms |
712 KB |
Output is correct |
13 |
Correct |
25 ms |
720 KB |
Output is correct |
14 |
Correct |
24 ms |
688 KB |
Output is correct |
15 |
Correct |
23 ms |
724 KB |
Output is correct |
16 |
Correct |
24 ms |
652 KB |
Output is correct |
17 |
Correct |
22 ms |
596 KB |
Output is correct |
18 |
Correct |
1280 ms |
9000 KB |
Output is correct |
19 |
Correct |
1308 ms |
8812 KB |
Output is correct |
20 |
Correct |
1285 ms |
8816 KB |
Output is correct |
21 |
Correct |
1307 ms |
9108 KB |
Output is correct |
22 |
Correct |
1346 ms |
8948 KB |
Output is correct |
23 |
Correct |
1813 ms |
8680 KB |
Output is correct |
24 |
Correct |
1866 ms |
8736 KB |
Output is correct |
25 |
Correct |
1788 ms |
8880 KB |
Output is correct |
26 |
Correct |
33 ms |
3388 KB |
Output is correct |
27 |
Correct |
1366 ms |
7804 KB |
Output is correct |
28 |
Correct |
1352 ms |
7792 KB |
Output is correct |
29 |
Correct |
1111 ms |
8584 KB |
Output is correct |
30 |
Correct |
1066 ms |
8916 KB |
Output is correct |
31 |
Correct |
944 ms |
6840 KB |
Output is correct |
32 |
Correct |
708 ms |
4208 KB |
Output is correct |
33 |
Correct |
1115 ms |
6696 KB |
Output is correct |
34 |
Correct |
929 ms |
6976 KB |
Output is correct |
35 |
Correct |
38 ms |
3388 KB |
Output is correct |
36 |
Correct |
1075 ms |
6864 KB |
Output is correct |
37 |
Correct |
870 ms |
6872 KB |
Output is correct |
38 |
Correct |
784 ms |
6756 KB |
Output is correct |
39 |
Correct |
620 ms |
6988 KB |
Output is correct |
40 |
Correct |
588 ms |
6896 KB |
Output is correct |
41 |
Correct |
628 ms |
6836 KB |
Output is correct |
42 |
Correct |
570 ms |
6728 KB |
Output is correct |
43 |
Correct |
1501 ms |
11956 KB |
Output is correct |
44 |
Correct |
33 ms |
3392 KB |
Output is correct |
45 |
Correct |
158 ms |
6276 KB |
Output is correct |
46 |
Correct |
186 ms |
6408 KB |
Output is correct |
47 |
Correct |
1766 ms |
10516 KB |
Output is correct |
48 |
Correct |
1409 ms |
12060 KB |
Output is correct |
49 |
Correct |
1749 ms |
10400 KB |
Output is correct |
50 |
Correct |
727 ms |
8972 KB |
Output is correct |
51 |
Correct |
696 ms |
9036 KB |
Output is correct |
52 |
Correct |
715 ms |
8724 KB |
Output is correct |
53 |
Correct |
1086 ms |
10532 KB |
Output is correct |
54 |
Correct |
1074 ms |
10448 KB |
Output is correct |
55 |
Correct |
1096 ms |
10316 KB |
Output is correct |
56 |
Correct |
1870 ms |
10464 KB |
Output is correct |
57 |
Correct |
1817 ms |
10384 KB |
Output is correct |
58 |
Correct |
1548 ms |
11916 KB |
Output is correct |
59 |
Correct |
1684 ms |
11844 KB |
Output is correct |
60 |
Correct |
1603 ms |
11940 KB |
Output is correct |
61 |
Correct |
1575 ms |
11952 KB |
Output is correct |
62 |
Correct |
1278 ms |
10744 KB |
Output is correct |
63 |
Correct |
1409 ms |
10668 KB |
Output is correct |
64 |
Correct |
1521 ms |
11520 KB |
Output is correct |
65 |
Correct |
1697 ms |
9276 KB |
Output is correct |
66 |
Correct |
1366 ms |
8956 KB |
Output is correct |
67 |
Correct |
1735 ms |
8792 KB |
Output is correct |
68 |
Correct |
1401 ms |
8860 KB |
Output is correct |
69 |
Correct |
1128 ms |
8980 KB |
Output is correct |
70 |
Correct |
1659 ms |
8784 KB |
Output is correct |
71 |
Correct |
2273 ms |
8668 KB |
Output is correct |
72 |
Correct |
1990 ms |
8888 KB |
Output is correct |
73 |
Correct |
1560 ms |
9048 KB |
Output is correct |
74 |
Correct |
1429 ms |
8968 KB |
Output is correct |
75 |
Correct |
1463 ms |
8948 KB |
Output is correct |
76 |
Correct |
1174 ms |
8884 KB |
Output is correct |
77 |
Correct |
1127 ms |
8884 KB |
Output is correct |
78 |
Correct |
1316 ms |
8952 KB |
Output is correct |
79 |
Correct |
1028 ms |
8952 KB |
Output is correct |
80 |
Correct |
1077 ms |
8800 KB |
Output is correct |
81 |
Correct |
1045 ms |
8820 KB |
Output is correct |
82 |
Correct |
1054 ms |
8784 KB |
Output is correct |
83 |
Correct |
1097 ms |
8760 KB |
Output is correct |
84 |
Correct |
910 ms |
8792 KB |
Output is correct |
85 |
Correct |
2194 ms |
11844 KB |
Output is correct |
86 |
Correct |
208 ms |
6284 KB |
Output is correct |
87 |
Correct |
270 ms |
6476 KB |
Output is correct |
88 |
Correct |
2660 ms |
10384 KB |
Output is correct |
89 |
Correct |
2088 ms |
12056 KB |
Output is correct |
90 |
Correct |
2495 ms |
10436 KB |
Output is correct |
91 |
Correct |
1390 ms |
8748 KB |
Output is correct |
92 |
Correct |
1391 ms |
8912 KB |
Output is correct |
93 |
Correct |
1990 ms |
8876 KB |
Output is correct |
94 |
Correct |
1725 ms |
10524 KB |
Output is correct |
95 |
Correct |
1741 ms |
10640 KB |
Output is correct |
96 |
Correct |
1993 ms |
10368 KB |
Output is correct |
97 |
Correct |
1883 ms |
10548 KB |
Output is correct |
98 |
Correct |
1969 ms |
10376 KB |
Output is correct |
99 |
Correct |
2027 ms |
11856 KB |
Output is correct |
100 |
Correct |
2032 ms |
11828 KB |
Output is correct |
101 |
Correct |
2057 ms |
12160 KB |
Output is correct |
102 |
Correct |
2052 ms |
12048 KB |
Output is correct |
103 |
Correct |
2151 ms |
10812 KB |
Output is correct |
104 |
Correct |
2136 ms |
10984 KB |
Output is correct |
105 |
Correct |
1550 ms |
10904 KB |
Output is correct |
106 |
Correct |
1263 ms |
10472 KB |
Output is correct |
107 |
Correct |
1453 ms |
11040 KB |
Output is correct |
108 |
Correct |
2028 ms |
11636 KB |
Output is correct |
109 |
Correct |
2080 ms |
9348 KB |
Output is correct |