# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
198319 |
2020-01-25T15:25:36 Z |
TAISA_ |
Bridges (APIO19_bridges) |
C++14 |
|
2750 ms |
9156 KB |
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int u[100000], v[100000], d[100000], dat[50000];
int t[100000], s[100000], w[100000], vis[100000], res[100000], tmp[100000];
P es[100000];
struct UnionFind {
stack<P> his;
inline void build(const int &n) { memset(dat, -1, sizeof(dat)); }
inline int find(const int &x) {
if (dat[x] < 0) {
return x;
} else {
return find(dat[x]);
}
}
inline bool unite(int u, int v, const int &f) {
u = find(u), v = find(v);
if (u == v)
return false;
if (dat[u] > dat[v])
swap(u, v);
if (f) {
his.emplace(u, dat[u]);
his.emplace(v, dat[v]);
}
dat[u] += dat[v];
dat[v] = u;
return true;
}
// bool same(int u, int v) { return find(u) == find(v); }
inline void rollback() {
while (!his.empty()) {
dat[his.top().first] = his.top().second;
his.pop();
dat[his.top().first] = his.top().second;
his.pop();
}
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
const int b = 800;
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u[i] >> v[i] >> d[i];
--u[i];
--v[i];
}
int q;
cin >> q;
memset(tmp, -1, sizeof(tmp));
priority_queue<pair<P, int>> qs;
UnionFind uf;
for (int i = 0; i < q; i++) {
cin >> t[i] >> s[i] >> w[i];
--s[i];
}
for (int i = 0; i < q; i++) {
if (t[i] == 1) {
vis[s[i]] = 1;
} else {
qs.push(make_pair(P(w[i], s[i]), i));
}
if (i % b < b - 1 && i != q - 1) {
continue;
}
for (int j = 0; j < m; j++) {
es[j] = P(d[j], j);
}
sort(es, es + m, greater<P>());
int id = 0;
uf.build(n);
int fs = (i / b) * b;
int ww, st, idx;
while (!qs.empty()) {
ww = qs.top().first.first, st = qs.top().first.second,
idx = qs.top().second;
qs.pop();
while (id < m && es[id].first >= ww) {
if (!vis[es[id].second]) {
uf.unite(u[es[id].second], v[es[id].second], 0);
}
id++;
}
for (int k = idx - 1; k >= fs; k--) {
if (t[k] == 1) {
if (tmp[s[k]] == -1) {
tmp[s[k]] = w[k];
if (w[k] >= ww) {
uf.unite(u[s[k]], v[s[k]], 1);
}
}
}
}
for (int k = idx + 1; k <= i; k++) {
if (t[k] == 1 &&
(tmp[s[k]] == -1 ? d[s[k]] : tmp[s[k]]) >= ww) {
uf.unite(u[s[k]], v[s[k]], 1);
}
}
for (int k = fs; k < idx; k++) {
if (t[k] == 1) {
tmp[s[k]] = -1;
}
}
res[idx] = -dat[uf.find(st)];
uf.rollback();
}
for (int j = i; j >= fs; j--) {
if (t[j] == 1 && vis[s[j]]) {
d[s[j]] = w[j];
vis[s[j]] = 0;
}
}
}
for (int i = 0; i < q; i++) {
if (t[i] == 2) {
cout << res[i] << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
888 KB |
Output is correct |
2 |
Correct |
3 ms |
764 KB |
Output is correct |
3 |
Correct |
45 ms |
1400 KB |
Output is correct |
4 |
Correct |
17 ms |
1272 KB |
Output is correct |
5 |
Correct |
53 ms |
1272 KB |
Output is correct |
6 |
Correct |
52 ms |
1272 KB |
Output is correct |
7 |
Correct |
56 ms |
1272 KB |
Output is correct |
8 |
Correct |
52 ms |
1272 KB |
Output is correct |
9 |
Correct |
71 ms |
1272 KB |
Output is correct |
10 |
Correct |
54 ms |
1272 KB |
Output is correct |
11 |
Correct |
53 ms |
1272 KB |
Output is correct |
12 |
Correct |
58 ms |
1272 KB |
Output is correct |
13 |
Correct |
63 ms |
1272 KB |
Output is correct |
14 |
Correct |
55 ms |
1324 KB |
Output is correct |
15 |
Correct |
58 ms |
1272 KB |
Output is correct |
16 |
Correct |
61 ms |
1244 KB |
Output is correct |
17 |
Correct |
65 ms |
1256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1638 ms |
5700 KB |
Output is correct |
2 |
Correct |
1679 ms |
5752 KB |
Output is correct |
3 |
Correct |
1677 ms |
5668 KB |
Output is correct |
4 |
Correct |
1793 ms |
5480 KB |
Output is correct |
5 |
Correct |
1770 ms |
5532 KB |
Output is correct |
6 |
Correct |
2571 ms |
5724 KB |
Output is correct |
7 |
Correct |
2572 ms |
5704 KB |
Output is correct |
8 |
Correct |
2565 ms |
5668 KB |
Output is correct |
9 |
Correct |
145 ms |
4128 KB |
Output is correct |
10 |
Correct |
1572 ms |
5740 KB |
Output is correct |
11 |
Correct |
1562 ms |
5488 KB |
Output is correct |
12 |
Correct |
1353 ms |
6632 KB |
Output is correct |
13 |
Correct |
1487 ms |
6520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1300 ms |
5844 KB |
Output is correct |
2 |
Correct |
881 ms |
4400 KB |
Output is correct |
3 |
Correct |
1440 ms |
5644 KB |
Output is correct |
4 |
Correct |
1257 ms |
5840 KB |
Output is correct |
5 |
Correct |
146 ms |
4100 KB |
Output is correct |
6 |
Correct |
1373 ms |
5792 KB |
Output is correct |
7 |
Correct |
1145 ms |
5788 KB |
Output is correct |
8 |
Correct |
1032 ms |
5868 KB |
Output is correct |
9 |
Correct |
839 ms |
6008 KB |
Output is correct |
10 |
Correct |
801 ms |
6008 KB |
Output is correct |
11 |
Correct |
849 ms |
5604 KB |
Output is correct |
12 |
Correct |
764 ms |
5616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2071 ms |
7964 KB |
Output is correct |
2 |
Correct |
149 ms |
4188 KB |
Output is correct |
3 |
Correct |
212 ms |
5040 KB |
Output is correct |
4 |
Correct |
130 ms |
5084 KB |
Output is correct |
5 |
Correct |
1817 ms |
7396 KB |
Output is correct |
6 |
Correct |
2024 ms |
8232 KB |
Output is correct |
7 |
Correct |
1867 ms |
7388 KB |
Output is correct |
8 |
Correct |
1002 ms |
6404 KB |
Output is correct |
9 |
Correct |
989 ms |
6568 KB |
Output is correct |
10 |
Correct |
992 ms |
6376 KB |
Output is correct |
11 |
Correct |
1590 ms |
7312 KB |
Output is correct |
12 |
Correct |
1492 ms |
7336 KB |
Output is correct |
13 |
Correct |
1572 ms |
7576 KB |
Output is correct |
14 |
Correct |
1527 ms |
7360 KB |
Output is correct |
15 |
Correct |
1699 ms |
7396 KB |
Output is correct |
16 |
Correct |
2040 ms |
8712 KB |
Output is correct |
17 |
Correct |
2069 ms |
8596 KB |
Output is correct |
18 |
Correct |
2058 ms |
8800 KB |
Output is correct |
19 |
Correct |
2047 ms |
8756 KB |
Output is correct |
20 |
Correct |
1731 ms |
7872 KB |
Output is correct |
21 |
Correct |
1746 ms |
7800 KB |
Output is correct |
22 |
Correct |
2017 ms |
8720 KB |
Output is correct |
23 |
Correct |
1831 ms |
6912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1638 ms |
5700 KB |
Output is correct |
2 |
Correct |
1679 ms |
5752 KB |
Output is correct |
3 |
Correct |
1677 ms |
5668 KB |
Output is correct |
4 |
Correct |
1793 ms |
5480 KB |
Output is correct |
5 |
Correct |
1770 ms |
5532 KB |
Output is correct |
6 |
Correct |
2571 ms |
5724 KB |
Output is correct |
7 |
Correct |
2572 ms |
5704 KB |
Output is correct |
8 |
Correct |
2565 ms |
5668 KB |
Output is correct |
9 |
Correct |
145 ms |
4128 KB |
Output is correct |
10 |
Correct |
1572 ms |
5740 KB |
Output is correct |
11 |
Correct |
1562 ms |
5488 KB |
Output is correct |
12 |
Correct |
1353 ms |
6632 KB |
Output is correct |
13 |
Correct |
1487 ms |
6520 KB |
Output is correct |
14 |
Correct |
1300 ms |
5844 KB |
Output is correct |
15 |
Correct |
881 ms |
4400 KB |
Output is correct |
16 |
Correct |
1440 ms |
5644 KB |
Output is correct |
17 |
Correct |
1257 ms |
5840 KB |
Output is correct |
18 |
Correct |
146 ms |
4100 KB |
Output is correct |
19 |
Correct |
1373 ms |
5792 KB |
Output is correct |
20 |
Correct |
1145 ms |
5788 KB |
Output is correct |
21 |
Correct |
1032 ms |
5868 KB |
Output is correct |
22 |
Correct |
839 ms |
6008 KB |
Output is correct |
23 |
Correct |
801 ms |
6008 KB |
Output is correct |
24 |
Correct |
849 ms |
5604 KB |
Output is correct |
25 |
Correct |
764 ms |
5616 KB |
Output is correct |
26 |
Correct |
1638 ms |
3984 KB |
Output is correct |
27 |
Correct |
2196 ms |
4072 KB |
Output is correct |
28 |
Correct |
1842 ms |
3896 KB |
Output is correct |
29 |
Correct |
1319 ms |
3844 KB |
Output is correct |
30 |
Correct |
2125 ms |
3888 KB |
Output is correct |
31 |
Correct |
2140 ms |
3924 KB |
Output is correct |
32 |
Correct |
2151 ms |
3908 KB |
Output is correct |
33 |
Correct |
1756 ms |
3928 KB |
Output is correct |
34 |
Correct |
1806 ms |
6768 KB |
Output is correct |
35 |
Correct |
1836 ms |
6580 KB |
Output is correct |
36 |
Correct |
1387 ms |
6580 KB |
Output is correct |
37 |
Correct |
1385 ms |
6652 KB |
Output is correct |
38 |
Correct |
1346 ms |
6548 KB |
Output is correct |
39 |
Correct |
1149 ms |
6632 KB |
Output is correct |
40 |
Correct |
1143 ms |
6672 KB |
Output is correct |
41 |
Correct |
1131 ms |
6724 KB |
Output is correct |
42 |
Correct |
1036 ms |
6476 KB |
Output is correct |
43 |
Correct |
1048 ms |
6300 KB |
Output is correct |
44 |
Correct |
1041 ms |
6456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
888 KB |
Output is correct |
2 |
Correct |
3 ms |
764 KB |
Output is correct |
3 |
Correct |
45 ms |
1400 KB |
Output is correct |
4 |
Correct |
17 ms |
1272 KB |
Output is correct |
5 |
Correct |
53 ms |
1272 KB |
Output is correct |
6 |
Correct |
52 ms |
1272 KB |
Output is correct |
7 |
Correct |
56 ms |
1272 KB |
Output is correct |
8 |
Correct |
52 ms |
1272 KB |
Output is correct |
9 |
Correct |
71 ms |
1272 KB |
Output is correct |
10 |
Correct |
54 ms |
1272 KB |
Output is correct |
11 |
Correct |
53 ms |
1272 KB |
Output is correct |
12 |
Correct |
58 ms |
1272 KB |
Output is correct |
13 |
Correct |
63 ms |
1272 KB |
Output is correct |
14 |
Correct |
55 ms |
1324 KB |
Output is correct |
15 |
Correct |
58 ms |
1272 KB |
Output is correct |
16 |
Correct |
61 ms |
1244 KB |
Output is correct |
17 |
Correct |
65 ms |
1256 KB |
Output is correct |
18 |
Correct |
1638 ms |
5700 KB |
Output is correct |
19 |
Correct |
1679 ms |
5752 KB |
Output is correct |
20 |
Correct |
1677 ms |
5668 KB |
Output is correct |
21 |
Correct |
1793 ms |
5480 KB |
Output is correct |
22 |
Correct |
1770 ms |
5532 KB |
Output is correct |
23 |
Correct |
2571 ms |
5724 KB |
Output is correct |
24 |
Correct |
2572 ms |
5704 KB |
Output is correct |
25 |
Correct |
2565 ms |
5668 KB |
Output is correct |
26 |
Correct |
145 ms |
4128 KB |
Output is correct |
27 |
Correct |
1572 ms |
5740 KB |
Output is correct |
28 |
Correct |
1562 ms |
5488 KB |
Output is correct |
29 |
Correct |
1353 ms |
6632 KB |
Output is correct |
30 |
Correct |
1487 ms |
6520 KB |
Output is correct |
31 |
Correct |
1300 ms |
5844 KB |
Output is correct |
32 |
Correct |
881 ms |
4400 KB |
Output is correct |
33 |
Correct |
1440 ms |
5644 KB |
Output is correct |
34 |
Correct |
1257 ms |
5840 KB |
Output is correct |
35 |
Correct |
146 ms |
4100 KB |
Output is correct |
36 |
Correct |
1373 ms |
5792 KB |
Output is correct |
37 |
Correct |
1145 ms |
5788 KB |
Output is correct |
38 |
Correct |
1032 ms |
5868 KB |
Output is correct |
39 |
Correct |
839 ms |
6008 KB |
Output is correct |
40 |
Correct |
801 ms |
6008 KB |
Output is correct |
41 |
Correct |
849 ms |
5604 KB |
Output is correct |
42 |
Correct |
764 ms |
5616 KB |
Output is correct |
43 |
Correct |
2071 ms |
7964 KB |
Output is correct |
44 |
Correct |
149 ms |
4188 KB |
Output is correct |
45 |
Correct |
212 ms |
5040 KB |
Output is correct |
46 |
Correct |
130 ms |
5084 KB |
Output is correct |
47 |
Correct |
1817 ms |
7396 KB |
Output is correct |
48 |
Correct |
2024 ms |
8232 KB |
Output is correct |
49 |
Correct |
1867 ms |
7388 KB |
Output is correct |
50 |
Correct |
1002 ms |
6404 KB |
Output is correct |
51 |
Correct |
989 ms |
6568 KB |
Output is correct |
52 |
Correct |
992 ms |
6376 KB |
Output is correct |
53 |
Correct |
1590 ms |
7312 KB |
Output is correct |
54 |
Correct |
1492 ms |
7336 KB |
Output is correct |
55 |
Correct |
1572 ms |
7576 KB |
Output is correct |
56 |
Correct |
1527 ms |
7360 KB |
Output is correct |
57 |
Correct |
1699 ms |
7396 KB |
Output is correct |
58 |
Correct |
2040 ms |
8712 KB |
Output is correct |
59 |
Correct |
2069 ms |
8596 KB |
Output is correct |
60 |
Correct |
2058 ms |
8800 KB |
Output is correct |
61 |
Correct |
2047 ms |
8756 KB |
Output is correct |
62 |
Correct |
1731 ms |
7872 KB |
Output is correct |
63 |
Correct |
1746 ms |
7800 KB |
Output is correct |
64 |
Correct |
2017 ms |
8720 KB |
Output is correct |
65 |
Correct |
1831 ms |
6912 KB |
Output is correct |
66 |
Correct |
1638 ms |
3984 KB |
Output is correct |
67 |
Correct |
2196 ms |
4072 KB |
Output is correct |
68 |
Correct |
1842 ms |
3896 KB |
Output is correct |
69 |
Correct |
1319 ms |
3844 KB |
Output is correct |
70 |
Correct |
2125 ms |
3888 KB |
Output is correct |
71 |
Correct |
2140 ms |
3924 KB |
Output is correct |
72 |
Correct |
2151 ms |
3908 KB |
Output is correct |
73 |
Correct |
1756 ms |
3928 KB |
Output is correct |
74 |
Correct |
1806 ms |
6768 KB |
Output is correct |
75 |
Correct |
1836 ms |
6580 KB |
Output is correct |
76 |
Correct |
1387 ms |
6580 KB |
Output is correct |
77 |
Correct |
1385 ms |
6652 KB |
Output is correct |
78 |
Correct |
1346 ms |
6548 KB |
Output is correct |
79 |
Correct |
1149 ms |
6632 KB |
Output is correct |
80 |
Correct |
1143 ms |
6672 KB |
Output is correct |
81 |
Correct |
1131 ms |
6724 KB |
Output is correct |
82 |
Correct |
1036 ms |
6476 KB |
Output is correct |
83 |
Correct |
1048 ms |
6300 KB |
Output is correct |
84 |
Correct |
1041 ms |
6456 KB |
Output is correct |
85 |
Correct |
2632 ms |
8856 KB |
Output is correct |
86 |
Correct |
241 ms |
5368 KB |
Output is correct |
87 |
Correct |
157 ms |
5496 KB |
Output is correct |
88 |
Correct |
2324 ms |
7568 KB |
Output is correct |
89 |
Correct |
2586 ms |
9016 KB |
Output is correct |
90 |
Correct |
2358 ms |
7452 KB |
Output is correct |
91 |
Correct |
1841 ms |
6468 KB |
Output is correct |
92 |
Correct |
1872 ms |
6704 KB |
Output is correct |
93 |
Correct |
2736 ms |
6636 KB |
Output is correct |
94 |
Correct |
2207 ms |
7844 KB |
Output is correct |
95 |
Correct |
2215 ms |
7900 KB |
Output is correct |
96 |
Correct |
2323 ms |
7592 KB |
Output is correct |
97 |
Correct |
2031 ms |
7372 KB |
Output is correct |
98 |
Correct |
2064 ms |
7028 KB |
Output is correct |
99 |
Correct |
2663 ms |
8876 KB |
Output is correct |
100 |
Correct |
2609 ms |
8892 KB |
Output is correct |
101 |
Correct |
2690 ms |
9088 KB |
Output is correct |
102 |
Correct |
2750 ms |
9156 KB |
Output is correct |
103 |
Correct |
2552 ms |
8200 KB |
Output is correct |
104 |
Correct |
2557 ms |
8048 KB |
Output is correct |
105 |
Correct |
1992 ms |
7804 KB |
Output is correct |
106 |
Correct |
1643 ms |
7436 KB |
Output is correct |
107 |
Correct |
1925 ms |
8092 KB |
Output is correct |
108 |
Correct |
2576 ms |
8556 KB |
Output is correct |
109 |
Correct |
2392 ms |
6932 KB |
Output is correct |