# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
198023 |
2020-01-24T14:00:34 Z |
QCFium |
Bridges (APIO19_bridges) |
C++14 |
|
2386 ms |
11884 KB |
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
int64_t rs64() {
long long n;
scanf("%lld", &n);
return n;
}
struct UnionFind {
std::vector<int> data;
std::vector<int> size;
std::vector<std::vector<std::pair<int, int> > > hens;
UnionFind (int n) : data(n, -1), size(n, 0), hens(n) {}
void add_hen(int start, int end, int index) { hens[start].push_back({index, end}); }
int root(int i) { return data[i] < 0 ? i : data[i] = root(data[i]); }
bool unite(int i, int j) {
i = root(i);
j = root(j);
if (i == j) return false;
if (-data[i] + size[i] > -data[j] + size[j]) std::swap(i, j);
// i->j
for (auto k : hens[i]) hens[j].push_back(k);
hens[i].clear();
size[j] += size[i];
data[j] += data[i];
data[i] = j;
return true;
}
int get_size(int i) { return -data[root(i)]; }
};
int main() {
int n = ri(), m = ri();
struct Hen {
int a;
int b;
int cost;
int id;
};
std::vector<Hen> hens(m);
for (int i = 0; i < m; i++) hens[i].a = ri() - 1, hens[i].b = ri() - 1, hens[i].cost = ri(), hens[i].id = i;
struct Query {
int type;
int index;
int cost;
int id;
};
int q = ri();
std::vector<Query> qs(q);
for (int i = 0; i < q; i++) qs[i].type = ri() - 1, qs[i].index = ri() - 1, qs[i].cost = ri(), qs[i].id = i;
#define BLOCK 800
std::vector<bool> changing(m);
std::vector<int> cost(m);
std::vector<int> h_start(m), h_end(m);
for (int i = 0; i < m; i++) cost[hens[i].id] = hens[i].cost, h_start[hens[i].id] = hens[i].a, h_end[hens[i].id] = hens[i].b;
std::vector<int> ch_rollback;
std::vector<bool> used(n);
std::vector<int> used_rollback;
std::vector<int> res(q);
for (int i = 0; i < q; i += BLOCK) {
auto hens_copy = hens;
std::sort(hens_copy.begin(), hens_copy.end(), [] (auto &i, auto &j) { return i.cost > j.cost; });
std::vector<Query> local;
for (int j = i; j < q && j < i + BLOCK; j++) {
local.push_back(qs[j]);
if (!qs[j].type) ch_rollback.push_back(qs[j].index), changing[qs[j].index] = true;
}
std::sort(local.begin(), local.end(), [] (auto &i, auto &j) { return i.cost > j.cost; });
UnionFind uni(n);
for (int j = 0; j < m; j++) if (changing[j]) uni.add_hen(h_start[j], h_end[j], j), uni.add_hen(h_end[j], h_start[j], j);
int head = 0;
for (auto j : local) {
if (!j.type) continue;
static std::vector<std::pair<int, int> > rollback;
for (int k = i; k < j.id; k++) if (!qs[k].type) rollback.push_back({qs[k].index, cost[qs[k].index]}), cost[qs[k].index] = qs[k].cost;
while (head < m && hens_copy[head].cost >= j.cost) {
if (!changing[hens_copy[head].id]) uni.unite(hens_copy[head].a, hens_copy[head].b);
head++;
}
auto use = [&] (int i) { used_rollback.push_back(i); used[i] = true; return i; };
std::queue<int> que;
que.push(use(uni.root(j.index)));
int cur = 0;
while (que.size()) {
int k = que.front();
que.pop();
cur += -uni.data[k];
for (auto l : uni.hens[k]) {
if (cost[l.first] < j.cost) continue;
int target = uni.root(l.second);
if (!used[target]) {
use(target);
que.push(target);
}
}
}
res[j.id] = cur;
for (auto k : used_rollback) used[k] = false;
used_rollback.clear();
for (; rollback.size(); rollback.pop_back()) cost[rollback.back().first] = rollback.back().second;
}
for (int j = i; j < q && j < i + BLOCK; j++) {
if (!qs[j].type) {
cost[qs[j].index] = qs[j].cost;
hens[qs[j].index].cost = qs[j].cost;
}
}
for (auto i : ch_rollback) changing[i] = false;
ch_rollback.clear();
}
for (int i = 0; i < q; i++) if (qs[i].type) printf("%d\n", res[i]);
return 0;
}
Compilation message
bridges.cpp: In function 'int ri()':
bridges.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
bridges.cpp: In function 'int64_t rs64()':
bridges.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
38 ms |
672 KB |
Output is correct |
4 |
Correct |
10 ms |
504 KB |
Output is correct |
5 |
Correct |
26 ms |
648 KB |
Output is correct |
6 |
Correct |
23 ms |
632 KB |
Output is correct |
7 |
Correct |
26 ms |
644 KB |
Output is correct |
8 |
Correct |
24 ms |
504 KB |
Output is correct |
9 |
Correct |
30 ms |
624 KB |
Output is correct |
10 |
Correct |
22 ms |
632 KB |
Output is correct |
11 |
Correct |
22 ms |
632 KB |
Output is correct |
12 |
Correct |
22 ms |
508 KB |
Output is correct |
13 |
Correct |
27 ms |
632 KB |
Output is correct |
14 |
Correct |
25 ms |
632 KB |
Output is correct |
15 |
Correct |
25 ms |
632 KB |
Output is correct |
16 |
Correct |
25 ms |
644 KB |
Output is correct |
17 |
Correct |
24 ms |
728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1062 ms |
6184 KB |
Output is correct |
2 |
Correct |
1062 ms |
6172 KB |
Output is correct |
3 |
Correct |
1068 ms |
6224 KB |
Output is correct |
4 |
Correct |
1055 ms |
6252 KB |
Output is correct |
5 |
Correct |
1207 ms |
6308 KB |
Output is correct |
6 |
Correct |
1951 ms |
6336 KB |
Output is correct |
7 |
Correct |
1791 ms |
6336 KB |
Output is correct |
8 |
Correct |
1668 ms |
6408 KB |
Output is correct |
9 |
Correct |
87 ms |
2524 KB |
Output is correct |
10 |
Correct |
1335 ms |
6328 KB |
Output is correct |
11 |
Correct |
1174 ms |
6372 KB |
Output is correct |
12 |
Correct |
1230 ms |
6220 KB |
Output is correct |
13 |
Correct |
1284 ms |
6564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
904 ms |
4992 KB |
Output is correct |
2 |
Correct |
845 ms |
3280 KB |
Output is correct |
3 |
Correct |
1439 ms |
5000 KB |
Output is correct |
4 |
Correct |
1066 ms |
5116 KB |
Output is correct |
5 |
Correct |
84 ms |
2488 KB |
Output is correct |
6 |
Correct |
1018 ms |
5028 KB |
Output is correct |
7 |
Correct |
954 ms |
5160 KB |
Output is correct |
8 |
Correct |
906 ms |
5164 KB |
Output is correct |
9 |
Correct |
823 ms |
4968 KB |
Output is correct |
10 |
Correct |
782 ms |
4992 KB |
Output is correct |
11 |
Correct |
857 ms |
5136 KB |
Output is correct |
12 |
Correct |
809 ms |
4988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1952 ms |
8552 KB |
Output is correct |
2 |
Correct |
84 ms |
2492 KB |
Output is correct |
3 |
Correct |
179 ms |
4928 KB |
Output is correct |
4 |
Correct |
90 ms |
4984 KB |
Output is correct |
5 |
Correct |
1234 ms |
8384 KB |
Output is correct |
6 |
Correct |
1920 ms |
8328 KB |
Output is correct |
7 |
Correct |
1235 ms |
8392 KB |
Output is correct |
8 |
Correct |
1113 ms |
6172 KB |
Output is correct |
9 |
Correct |
1124 ms |
6284 KB |
Output is correct |
10 |
Correct |
1121 ms |
6252 KB |
Output is correct |
11 |
Correct |
1649 ms |
7248 KB |
Output is correct |
12 |
Correct |
1607 ms |
7352 KB |
Output is correct |
13 |
Correct |
1667 ms |
7320 KB |
Output is correct |
14 |
Correct |
1140 ms |
8376 KB |
Output is correct |
15 |
Correct |
1193 ms |
8380 KB |
Output is correct |
16 |
Correct |
2028 ms |
8316 KB |
Output is correct |
17 |
Correct |
2053 ms |
8292 KB |
Output is correct |
18 |
Correct |
2009 ms |
8484 KB |
Output is correct |
19 |
Correct |
2036 ms |
8492 KB |
Output is correct |
20 |
Correct |
1769 ms |
7496 KB |
Output is correct |
21 |
Correct |
1799 ms |
7748 KB |
Output is correct |
22 |
Correct |
1958 ms |
8220 KB |
Output is correct |
23 |
Correct |
1261 ms |
7368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1062 ms |
6184 KB |
Output is correct |
2 |
Correct |
1062 ms |
6172 KB |
Output is correct |
3 |
Correct |
1068 ms |
6224 KB |
Output is correct |
4 |
Correct |
1055 ms |
6252 KB |
Output is correct |
5 |
Correct |
1207 ms |
6308 KB |
Output is correct |
6 |
Correct |
1951 ms |
6336 KB |
Output is correct |
7 |
Correct |
1791 ms |
6336 KB |
Output is correct |
8 |
Correct |
1668 ms |
6408 KB |
Output is correct |
9 |
Correct |
87 ms |
2524 KB |
Output is correct |
10 |
Correct |
1335 ms |
6328 KB |
Output is correct |
11 |
Correct |
1174 ms |
6372 KB |
Output is correct |
12 |
Correct |
1230 ms |
6220 KB |
Output is correct |
13 |
Correct |
1284 ms |
6564 KB |
Output is correct |
14 |
Correct |
904 ms |
4992 KB |
Output is correct |
15 |
Correct |
845 ms |
3280 KB |
Output is correct |
16 |
Correct |
1439 ms |
5000 KB |
Output is correct |
17 |
Correct |
1066 ms |
5116 KB |
Output is correct |
18 |
Correct |
84 ms |
2488 KB |
Output is correct |
19 |
Correct |
1018 ms |
5028 KB |
Output is correct |
20 |
Correct |
954 ms |
5160 KB |
Output is correct |
21 |
Correct |
906 ms |
5164 KB |
Output is correct |
22 |
Correct |
823 ms |
4968 KB |
Output is correct |
23 |
Correct |
782 ms |
4992 KB |
Output is correct |
24 |
Correct |
857 ms |
5136 KB |
Output is correct |
25 |
Correct |
809 ms |
4988 KB |
Output is correct |
26 |
Correct |
1366 ms |
6468 KB |
Output is correct |
27 |
Correct |
1797 ms |
6320 KB |
Output is correct |
28 |
Correct |
1435 ms |
6464 KB |
Output is correct |
29 |
Correct |
1281 ms |
6260 KB |
Output is correct |
30 |
Correct |
1574 ms |
6400 KB |
Output is correct |
31 |
Correct |
1647 ms |
6320 KB |
Output is correct |
32 |
Correct |
1643 ms |
6480 KB |
Output is correct |
33 |
Correct |
1287 ms |
6304 KB |
Output is correct |
34 |
Correct |
1300 ms |
6332 KB |
Output is correct |
35 |
Correct |
1320 ms |
6496 KB |
Output is correct |
36 |
Correct |
1098 ms |
6176 KB |
Output is correct |
37 |
Correct |
1089 ms |
6160 KB |
Output is correct |
38 |
Correct |
1086 ms |
6284 KB |
Output is correct |
39 |
Correct |
991 ms |
6276 KB |
Output is correct |
40 |
Correct |
999 ms |
6232 KB |
Output is correct |
41 |
Correct |
1006 ms |
6388 KB |
Output is correct |
42 |
Correct |
992 ms |
6164 KB |
Output is correct |
43 |
Correct |
1004 ms |
6264 KB |
Output is correct |
44 |
Correct |
992 ms |
6284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
38 ms |
672 KB |
Output is correct |
4 |
Correct |
10 ms |
504 KB |
Output is correct |
5 |
Correct |
26 ms |
648 KB |
Output is correct |
6 |
Correct |
23 ms |
632 KB |
Output is correct |
7 |
Correct |
26 ms |
644 KB |
Output is correct |
8 |
Correct |
24 ms |
504 KB |
Output is correct |
9 |
Correct |
30 ms |
624 KB |
Output is correct |
10 |
Correct |
22 ms |
632 KB |
Output is correct |
11 |
Correct |
22 ms |
632 KB |
Output is correct |
12 |
Correct |
22 ms |
508 KB |
Output is correct |
13 |
Correct |
27 ms |
632 KB |
Output is correct |
14 |
Correct |
25 ms |
632 KB |
Output is correct |
15 |
Correct |
25 ms |
632 KB |
Output is correct |
16 |
Correct |
25 ms |
644 KB |
Output is correct |
17 |
Correct |
24 ms |
728 KB |
Output is correct |
18 |
Correct |
1062 ms |
6184 KB |
Output is correct |
19 |
Correct |
1062 ms |
6172 KB |
Output is correct |
20 |
Correct |
1068 ms |
6224 KB |
Output is correct |
21 |
Correct |
1055 ms |
6252 KB |
Output is correct |
22 |
Correct |
1207 ms |
6308 KB |
Output is correct |
23 |
Correct |
1951 ms |
6336 KB |
Output is correct |
24 |
Correct |
1791 ms |
6336 KB |
Output is correct |
25 |
Correct |
1668 ms |
6408 KB |
Output is correct |
26 |
Correct |
87 ms |
2524 KB |
Output is correct |
27 |
Correct |
1335 ms |
6328 KB |
Output is correct |
28 |
Correct |
1174 ms |
6372 KB |
Output is correct |
29 |
Correct |
1230 ms |
6220 KB |
Output is correct |
30 |
Correct |
1284 ms |
6564 KB |
Output is correct |
31 |
Correct |
904 ms |
4992 KB |
Output is correct |
32 |
Correct |
845 ms |
3280 KB |
Output is correct |
33 |
Correct |
1439 ms |
5000 KB |
Output is correct |
34 |
Correct |
1066 ms |
5116 KB |
Output is correct |
35 |
Correct |
84 ms |
2488 KB |
Output is correct |
36 |
Correct |
1018 ms |
5028 KB |
Output is correct |
37 |
Correct |
954 ms |
5160 KB |
Output is correct |
38 |
Correct |
906 ms |
5164 KB |
Output is correct |
39 |
Correct |
823 ms |
4968 KB |
Output is correct |
40 |
Correct |
782 ms |
4992 KB |
Output is correct |
41 |
Correct |
857 ms |
5136 KB |
Output is correct |
42 |
Correct |
809 ms |
4988 KB |
Output is correct |
43 |
Correct |
1952 ms |
8552 KB |
Output is correct |
44 |
Correct |
84 ms |
2492 KB |
Output is correct |
45 |
Correct |
179 ms |
4928 KB |
Output is correct |
46 |
Correct |
90 ms |
4984 KB |
Output is correct |
47 |
Correct |
1234 ms |
8384 KB |
Output is correct |
48 |
Correct |
1920 ms |
8328 KB |
Output is correct |
49 |
Correct |
1235 ms |
8392 KB |
Output is correct |
50 |
Correct |
1113 ms |
6172 KB |
Output is correct |
51 |
Correct |
1124 ms |
6284 KB |
Output is correct |
52 |
Correct |
1121 ms |
6252 KB |
Output is correct |
53 |
Correct |
1649 ms |
7248 KB |
Output is correct |
54 |
Correct |
1607 ms |
7352 KB |
Output is correct |
55 |
Correct |
1667 ms |
7320 KB |
Output is correct |
56 |
Correct |
1140 ms |
8376 KB |
Output is correct |
57 |
Correct |
1193 ms |
8380 KB |
Output is correct |
58 |
Correct |
2028 ms |
8316 KB |
Output is correct |
59 |
Correct |
2053 ms |
8292 KB |
Output is correct |
60 |
Correct |
2009 ms |
8484 KB |
Output is correct |
61 |
Correct |
2036 ms |
8492 KB |
Output is correct |
62 |
Correct |
1769 ms |
7496 KB |
Output is correct |
63 |
Correct |
1799 ms |
7748 KB |
Output is correct |
64 |
Correct |
1958 ms |
8220 KB |
Output is correct |
65 |
Correct |
1261 ms |
7368 KB |
Output is correct |
66 |
Correct |
1366 ms |
6468 KB |
Output is correct |
67 |
Correct |
1797 ms |
6320 KB |
Output is correct |
68 |
Correct |
1435 ms |
6464 KB |
Output is correct |
69 |
Correct |
1281 ms |
6260 KB |
Output is correct |
70 |
Correct |
1574 ms |
6400 KB |
Output is correct |
71 |
Correct |
1647 ms |
6320 KB |
Output is correct |
72 |
Correct |
1643 ms |
6480 KB |
Output is correct |
73 |
Correct |
1287 ms |
6304 KB |
Output is correct |
74 |
Correct |
1300 ms |
6332 KB |
Output is correct |
75 |
Correct |
1320 ms |
6496 KB |
Output is correct |
76 |
Correct |
1098 ms |
6176 KB |
Output is correct |
77 |
Correct |
1089 ms |
6160 KB |
Output is correct |
78 |
Correct |
1086 ms |
6284 KB |
Output is correct |
79 |
Correct |
991 ms |
6276 KB |
Output is correct |
80 |
Correct |
999 ms |
6232 KB |
Output is correct |
81 |
Correct |
1006 ms |
6388 KB |
Output is correct |
82 |
Correct |
992 ms |
6164 KB |
Output is correct |
83 |
Correct |
1004 ms |
6264 KB |
Output is correct |
84 |
Correct |
992 ms |
6284 KB |
Output is correct |
85 |
Correct |
2386 ms |
8524 KB |
Output is correct |
86 |
Correct |
211 ms |
4960 KB |
Output is correct |
87 |
Correct |
119 ms |
4960 KB |
Output is correct |
88 |
Correct |
1611 ms |
8476 KB |
Output is correct |
89 |
Correct |
2366 ms |
8720 KB |
Output is correct |
90 |
Correct |
1635 ms |
8544 KB |
Output is correct |
91 |
Correct |
1097 ms |
6164 KB |
Output is correct |
92 |
Correct |
1090 ms |
7572 KB |
Output is correct |
93 |
Correct |
1279 ms |
7704 KB |
Output is correct |
94 |
Correct |
1881 ms |
8780 KB |
Output is correct |
95 |
Correct |
1625 ms |
8812 KB |
Output is correct |
96 |
Correct |
1839 ms |
8888 KB |
Output is correct |
97 |
Correct |
1390 ms |
9824 KB |
Output is correct |
98 |
Correct |
1416 ms |
9916 KB |
Output is correct |
99 |
Correct |
2345 ms |
9868 KB |
Output is correct |
100 |
Correct |
2141 ms |
9928 KB |
Output is correct |
101 |
Correct |
2325 ms |
11164 KB |
Output is correct |
102 |
Correct |
2073 ms |
10972 KB |
Output is correct |
103 |
Correct |
2029 ms |
10380 KB |
Output is correct |
104 |
Correct |
2044 ms |
10344 KB |
Output is correct |
105 |
Correct |
1939 ms |
10380 KB |
Output is correct |
106 |
Correct |
1764 ms |
10688 KB |
Output is correct |
107 |
Correct |
1870 ms |
11012 KB |
Output is correct |
108 |
Correct |
2360 ms |
11884 KB |
Output is correct |
109 |
Correct |
1501 ms |
9660 KB |
Output is correct |