# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
222886 |
2020-04-14T09:59:39 Z |
atoiz |
Bridges (APIO19_bridges) |
C++14 |
|
1742 ms |
9724 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <set>
#include <functional>
#include <cassert>
using namespace std;
const int MAXN = 50007, MAXM = 100007, SPLIT = 320;
struct Edge { int from, to, w, nxt; } edges[MAXM], subEdges[SPLIT * 2 + 7];
int start[MAXN], numEdges;
bool vis[MAXN];
int N, M, Q, ans[MAXM];
vector<pair<int, int>> sortedEdges, changedEdges, tmp;
vector<tuple<int, int, int>> changes, queries;
vector<int> singleChanges[MAXM];
int changePos[MAXM];
bool changed[MAXM];
namespace dsu {
int arr[MAXN];
void reset() { fill_n(arr + 1, N, -1); }
int root(int u) { return (arr[u] < 0 ? u : arr[u] = root(arr[u])); }
void join(int u, int v)
{
u = root(u), v = root(v);
if (u == v) return;
if (arr[u] > arr[v]) swap(u, v);
arr[u] += arr[v];
arr[v] = u;
}
int sizeOf(int u) { return -arr[root(u)]; }
}
inline void addEdge(int from, int to) {
subEdges[++numEdges] = {from, to, 0, start[from]};
start[from] = numEdges;
}
int curAns;
void dfs(int u) {
curAns += dsu::sizeOf(u);
vis[u] = true;
for (int i = start[u]; i > 0; i = subEdges[i].nxt) {
int v = subEdges[i].to;
if (!vis[v]) dfs(v);
}
}
void solve()
{
dsu::reset();
for (auto change : changes) {
int edgeId, newW;
tie(edgeId, newW, ignore) = change;
singleChanges[edgeId].push_back(newW);
changed[edgeId] = true;
}
sort(queries.begin(), queries.end(), [&](tuple<int, int, int> &lhs, tuple<int, int, int> &rhs) { return get<1>(lhs) > get<1>(rhs); });
auto e_it = sortedEdges.rbegin();
auto c_it = changes.begin();
for (auto query : queries) {
int source, w, id;
tie(source, w, id) = query;
for (; e_it != sortedEdges.rend() && e_it -> first >= w; ++e_it) if (!changed[e_it -> second]) {
auto &edge = edges[e_it -> second];
dsu::join(edge.from, edge.to);
}
for (; c_it != changes.end() && get<2>(*c_it) < id; ++c_it) ++changePos[get<0>(*c_it)];
for (; c_it != changes.begin() && get<2>(*prev(c_it)) > id; --c_it) --changePos[get<0>(*prev(c_it))];
numEdges = 0;
for (auto &change : changes) {
int edgeId = get<0>(change);
int u = dsu::root(edges[edgeId].from), v = dsu::root(edges[edgeId].to);
int newW = (changePos[edgeId] ? singleChanges[edgeId][changePos[edgeId] - 1] : edges[edgeId].w);
if (newW >= w) {
addEdge(u, v);
addEdge(v, u);
}
}
curAns = 0;
dfs(dsu::root(source));
ans[id] = curAns;
vis[dsu::root(source)] = 0;
for (auto change : changes) {
int edgeId = get<0>(change);
int u = dsu::root(edges[edgeId].from), v = dsu::root(edges[edgeId].to);
start[u] = start[v] = 0;
vis[u] = vis[v] = 0;
}
}
changedEdges.clear();
for (int edgeId = 1; edgeId <= M; ++edgeId) if (changed[edgeId]) {
changedEdges.emplace_back(edges[edgeId].w = singleChanges[edgeId].back(), edgeId);
}
sort(changedEdges.begin(), changedEdges.end());
tmp.clear();
for (auto it1 = changedEdges.begin(), it2 = sortedEdges.begin(); it1 != changedEdges.end() || it2 != sortedEdges.end(); ) {
for (; it2 != sortedEdges.end() && changed[it2 -> second]; ++it2);
if (it1 != changedEdges.end() && (it2 == sortedEdges.end() || (*it1) < (*it2))) {
tmp.push_back(*(it1++));
} else if (it2 != sortedEdges.end()) {
tmp.push_back(*(it2++));
}
}
tmp.swap(sortedEdges);
for (auto change : changes) {
int edgeId, newW;
tie(edgeId, newW, ignore) = change;
singleChanges[edgeId].clear();
changePos[edgeId] = 0;
changed[edgeId] = false;
}
changes.clear();
queries.clear();
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
auto &x = edges[i];
cin >> x.from >> x.to >> x.w;
sortedEdges.emplace_back(x.w, i);
}
sort(sortedEdges.begin(), sortedEdges.end());
cin >> Q;
changes.reserve(SPLIT);
queries.reserve(Q);
for (int i = 0; i < Q; ++i) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1) changes.emplace_back(x, y, i);
else queries.emplace_back(x, y, i);
if (changes.size() == SPLIT) solve();
}
solve();
for (int i = 0; i < Q; ++i) {
if (ans[i]) cout << ans[i] << '\n';
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
66 ms |
3064 KB |
Output is correct |
4 |
Correct |
11 ms |
3072 KB |
Output is correct |
5 |
Correct |
48 ms |
3064 KB |
Output is correct |
6 |
Correct |
43 ms |
2944 KB |
Output is correct |
7 |
Correct |
50 ms |
2936 KB |
Output is correct |
8 |
Correct |
43 ms |
2944 KB |
Output is correct |
9 |
Correct |
44 ms |
2912 KB |
Output is correct |
10 |
Correct |
40 ms |
2944 KB |
Output is correct |
11 |
Correct |
39 ms |
2944 KB |
Output is correct |
12 |
Correct |
41 ms |
2944 KB |
Output is correct |
13 |
Correct |
52 ms |
2944 KB |
Output is correct |
14 |
Correct |
46 ms |
2944 KB |
Output is correct |
15 |
Correct |
53 ms |
2936 KB |
Output is correct |
16 |
Correct |
40 ms |
2816 KB |
Output is correct |
17 |
Correct |
40 ms |
2936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1080 ms |
7304 KB |
Output is correct |
2 |
Correct |
1059 ms |
7380 KB |
Output is correct |
3 |
Correct |
1117 ms |
7284 KB |
Output is correct |
4 |
Correct |
1121 ms |
7272 KB |
Output is correct |
5 |
Correct |
1149 ms |
7268 KB |
Output is correct |
6 |
Correct |
1494 ms |
7408 KB |
Output is correct |
7 |
Correct |
1447 ms |
7460 KB |
Output is correct |
8 |
Correct |
1388 ms |
7416 KB |
Output is correct |
9 |
Correct |
56 ms |
5216 KB |
Output is correct |
10 |
Correct |
1078 ms |
7316 KB |
Output is correct |
11 |
Correct |
1014 ms |
7372 KB |
Output is correct |
12 |
Correct |
1742 ms |
7084 KB |
Output is correct |
13 |
Correct |
822 ms |
7544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
876 ms |
6268 KB |
Output is correct |
2 |
Correct |
789 ms |
4728 KB |
Output is correct |
3 |
Correct |
1039 ms |
6648 KB |
Output is correct |
4 |
Correct |
895 ms |
6524 KB |
Output is correct |
5 |
Correct |
54 ms |
5240 KB |
Output is correct |
6 |
Correct |
948 ms |
6396 KB |
Output is correct |
7 |
Correct |
888 ms |
6392 KB |
Output is correct |
8 |
Correct |
819 ms |
6268 KB |
Output is correct |
9 |
Correct |
1318 ms |
6056 KB |
Output is correct |
10 |
Correct |
1155 ms |
5884 KB |
Output is correct |
11 |
Correct |
555 ms |
6524 KB |
Output is correct |
12 |
Correct |
523 ms |
6496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
9328 KB |
Output is correct |
2 |
Correct |
50 ms |
5240 KB |
Output is correct |
3 |
Correct |
57 ms |
7536 KB |
Output is correct |
4 |
Correct |
52 ms |
7536 KB |
Output is correct |
5 |
Correct |
96 ms |
9196 KB |
Output is correct |
6 |
Correct |
108 ms |
9292 KB |
Output is correct |
7 |
Correct |
89 ms |
9200 KB |
Output is correct |
8 |
Correct |
83 ms |
7284 KB |
Output is correct |
9 |
Correct |
86 ms |
7280 KB |
Output is correct |
10 |
Correct |
93 ms |
7412 KB |
Output is correct |
11 |
Correct |
99 ms |
8556 KB |
Output is correct |
12 |
Correct |
96 ms |
8560 KB |
Output is correct |
13 |
Correct |
95 ms |
8556 KB |
Output is correct |
14 |
Correct |
92 ms |
9196 KB |
Output is correct |
15 |
Correct |
87 ms |
9196 KB |
Output is correct |
16 |
Correct |
110 ms |
9172 KB |
Output is correct |
17 |
Correct |
111 ms |
9200 KB |
Output is correct |
18 |
Correct |
108 ms |
9200 KB |
Output is correct |
19 |
Correct |
117 ms |
9200 KB |
Output is correct |
20 |
Correct |
99 ms |
8812 KB |
Output is correct |
21 |
Correct |
107 ms |
8816 KB |
Output is correct |
22 |
Correct |
108 ms |
9072 KB |
Output is correct |
23 |
Correct |
77 ms |
8684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1080 ms |
7304 KB |
Output is correct |
2 |
Correct |
1059 ms |
7380 KB |
Output is correct |
3 |
Correct |
1117 ms |
7284 KB |
Output is correct |
4 |
Correct |
1121 ms |
7272 KB |
Output is correct |
5 |
Correct |
1149 ms |
7268 KB |
Output is correct |
6 |
Correct |
1494 ms |
7408 KB |
Output is correct |
7 |
Correct |
1447 ms |
7460 KB |
Output is correct |
8 |
Correct |
1388 ms |
7416 KB |
Output is correct |
9 |
Correct |
56 ms |
5216 KB |
Output is correct |
10 |
Correct |
1078 ms |
7316 KB |
Output is correct |
11 |
Correct |
1014 ms |
7372 KB |
Output is correct |
12 |
Correct |
1742 ms |
7084 KB |
Output is correct |
13 |
Correct |
822 ms |
7544 KB |
Output is correct |
14 |
Correct |
876 ms |
6268 KB |
Output is correct |
15 |
Correct |
789 ms |
4728 KB |
Output is correct |
16 |
Correct |
1039 ms |
6648 KB |
Output is correct |
17 |
Correct |
895 ms |
6524 KB |
Output is correct |
18 |
Correct |
54 ms |
5240 KB |
Output is correct |
19 |
Correct |
948 ms |
6396 KB |
Output is correct |
20 |
Correct |
888 ms |
6392 KB |
Output is correct |
21 |
Correct |
819 ms |
6268 KB |
Output is correct |
22 |
Correct |
1318 ms |
6056 KB |
Output is correct |
23 |
Correct |
1155 ms |
5884 KB |
Output is correct |
24 |
Correct |
555 ms |
6524 KB |
Output is correct |
25 |
Correct |
523 ms |
6496 KB |
Output is correct |
26 |
Correct |
1039 ms |
7528 KB |
Output is correct |
27 |
Correct |
1249 ms |
7444 KB |
Output is correct |
28 |
Correct |
1129 ms |
7548 KB |
Output is correct |
29 |
Correct |
923 ms |
7232 KB |
Output is correct |
30 |
Correct |
1282 ms |
7444 KB |
Output is correct |
31 |
Correct |
1294 ms |
7592 KB |
Output is correct |
32 |
Correct |
1256 ms |
7288 KB |
Output is correct |
33 |
Correct |
1101 ms |
7356 KB |
Output is correct |
34 |
Correct |
1119 ms |
7416 KB |
Output is correct |
35 |
Correct |
1124 ms |
7520 KB |
Output is correct |
36 |
Correct |
927 ms |
7416 KB |
Output is correct |
37 |
Correct |
946 ms |
7392 KB |
Output is correct |
38 |
Correct |
913 ms |
7376 KB |
Output is correct |
39 |
Correct |
987 ms |
6776 KB |
Output is correct |
40 |
Correct |
970 ms |
6736 KB |
Output is correct |
41 |
Correct |
965 ms |
6700 KB |
Output is correct |
42 |
Correct |
724 ms |
7544 KB |
Output is correct |
43 |
Correct |
735 ms |
7672 KB |
Output is correct |
44 |
Correct |
725 ms |
7584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
66 ms |
3064 KB |
Output is correct |
4 |
Correct |
11 ms |
3072 KB |
Output is correct |
5 |
Correct |
48 ms |
3064 KB |
Output is correct |
6 |
Correct |
43 ms |
2944 KB |
Output is correct |
7 |
Correct |
50 ms |
2936 KB |
Output is correct |
8 |
Correct |
43 ms |
2944 KB |
Output is correct |
9 |
Correct |
44 ms |
2912 KB |
Output is correct |
10 |
Correct |
40 ms |
2944 KB |
Output is correct |
11 |
Correct |
39 ms |
2944 KB |
Output is correct |
12 |
Correct |
41 ms |
2944 KB |
Output is correct |
13 |
Correct |
52 ms |
2944 KB |
Output is correct |
14 |
Correct |
46 ms |
2944 KB |
Output is correct |
15 |
Correct |
53 ms |
2936 KB |
Output is correct |
16 |
Correct |
40 ms |
2816 KB |
Output is correct |
17 |
Correct |
40 ms |
2936 KB |
Output is correct |
18 |
Correct |
1080 ms |
7304 KB |
Output is correct |
19 |
Correct |
1059 ms |
7380 KB |
Output is correct |
20 |
Correct |
1117 ms |
7284 KB |
Output is correct |
21 |
Correct |
1121 ms |
7272 KB |
Output is correct |
22 |
Correct |
1149 ms |
7268 KB |
Output is correct |
23 |
Correct |
1494 ms |
7408 KB |
Output is correct |
24 |
Correct |
1447 ms |
7460 KB |
Output is correct |
25 |
Correct |
1388 ms |
7416 KB |
Output is correct |
26 |
Correct |
56 ms |
5216 KB |
Output is correct |
27 |
Correct |
1078 ms |
7316 KB |
Output is correct |
28 |
Correct |
1014 ms |
7372 KB |
Output is correct |
29 |
Correct |
1742 ms |
7084 KB |
Output is correct |
30 |
Correct |
822 ms |
7544 KB |
Output is correct |
31 |
Correct |
876 ms |
6268 KB |
Output is correct |
32 |
Correct |
789 ms |
4728 KB |
Output is correct |
33 |
Correct |
1039 ms |
6648 KB |
Output is correct |
34 |
Correct |
895 ms |
6524 KB |
Output is correct |
35 |
Correct |
54 ms |
5240 KB |
Output is correct |
36 |
Correct |
948 ms |
6396 KB |
Output is correct |
37 |
Correct |
888 ms |
6392 KB |
Output is correct |
38 |
Correct |
819 ms |
6268 KB |
Output is correct |
39 |
Correct |
1318 ms |
6056 KB |
Output is correct |
40 |
Correct |
1155 ms |
5884 KB |
Output is correct |
41 |
Correct |
555 ms |
6524 KB |
Output is correct |
42 |
Correct |
523 ms |
6496 KB |
Output is correct |
43 |
Correct |
118 ms |
9328 KB |
Output is correct |
44 |
Correct |
50 ms |
5240 KB |
Output is correct |
45 |
Correct |
57 ms |
7536 KB |
Output is correct |
46 |
Correct |
52 ms |
7536 KB |
Output is correct |
47 |
Correct |
96 ms |
9196 KB |
Output is correct |
48 |
Correct |
108 ms |
9292 KB |
Output is correct |
49 |
Correct |
89 ms |
9200 KB |
Output is correct |
50 |
Correct |
83 ms |
7284 KB |
Output is correct |
51 |
Correct |
86 ms |
7280 KB |
Output is correct |
52 |
Correct |
93 ms |
7412 KB |
Output is correct |
53 |
Correct |
99 ms |
8556 KB |
Output is correct |
54 |
Correct |
96 ms |
8560 KB |
Output is correct |
55 |
Correct |
95 ms |
8556 KB |
Output is correct |
56 |
Correct |
92 ms |
9196 KB |
Output is correct |
57 |
Correct |
87 ms |
9196 KB |
Output is correct |
58 |
Correct |
110 ms |
9172 KB |
Output is correct |
59 |
Correct |
111 ms |
9200 KB |
Output is correct |
60 |
Correct |
108 ms |
9200 KB |
Output is correct |
61 |
Correct |
117 ms |
9200 KB |
Output is correct |
62 |
Correct |
99 ms |
8812 KB |
Output is correct |
63 |
Correct |
107 ms |
8816 KB |
Output is correct |
64 |
Correct |
108 ms |
9072 KB |
Output is correct |
65 |
Correct |
77 ms |
8684 KB |
Output is correct |
66 |
Correct |
1039 ms |
7528 KB |
Output is correct |
67 |
Correct |
1249 ms |
7444 KB |
Output is correct |
68 |
Correct |
1129 ms |
7548 KB |
Output is correct |
69 |
Correct |
923 ms |
7232 KB |
Output is correct |
70 |
Correct |
1282 ms |
7444 KB |
Output is correct |
71 |
Correct |
1294 ms |
7592 KB |
Output is correct |
72 |
Correct |
1256 ms |
7288 KB |
Output is correct |
73 |
Correct |
1101 ms |
7356 KB |
Output is correct |
74 |
Correct |
1119 ms |
7416 KB |
Output is correct |
75 |
Correct |
1124 ms |
7520 KB |
Output is correct |
76 |
Correct |
927 ms |
7416 KB |
Output is correct |
77 |
Correct |
946 ms |
7392 KB |
Output is correct |
78 |
Correct |
913 ms |
7376 KB |
Output is correct |
79 |
Correct |
987 ms |
6776 KB |
Output is correct |
80 |
Correct |
970 ms |
6736 KB |
Output is correct |
81 |
Correct |
965 ms |
6700 KB |
Output is correct |
82 |
Correct |
724 ms |
7544 KB |
Output is correct |
83 |
Correct |
735 ms |
7672 KB |
Output is correct |
84 |
Correct |
725 ms |
7584 KB |
Output is correct |
85 |
Correct |
1722 ms |
9560 KB |
Output is correct |
86 |
Correct |
169 ms |
8176 KB |
Output is correct |
87 |
Correct |
143 ms |
8172 KB |
Output is correct |
88 |
Correct |
1335 ms |
9580 KB |
Output is correct |
89 |
Correct |
1637 ms |
9588 KB |
Output is correct |
90 |
Correct |
1343 ms |
9588 KB |
Output is correct |
91 |
Correct |
1127 ms |
7416 KB |
Output is correct |
92 |
Correct |
1074 ms |
7388 KB |
Output is correct |
93 |
Correct |
1295 ms |
7544 KB |
Output is correct |
94 |
Correct |
1474 ms |
8728 KB |
Output is correct |
95 |
Correct |
1470 ms |
8700 KB |
Output is correct |
96 |
Correct |
1544 ms |
8600 KB |
Output is correct |
97 |
Correct |
1603 ms |
8692 KB |
Output is correct |
98 |
Correct |
1082 ms |
9260 KB |
Output is correct |
99 |
Correct |
1717 ms |
9460 KB |
Output is correct |
100 |
Correct |
1688 ms |
9724 KB |
Output is correct |
101 |
Correct |
1708 ms |
9668 KB |
Output is correct |
102 |
Correct |
1696 ms |
9588 KB |
Output is correct |
103 |
Correct |
1646 ms |
8780 KB |
Output is correct |
104 |
Correct |
1662 ms |
8764 KB |
Output is correct |
105 |
Correct |
1531 ms |
8816 KB |
Output is correct |
106 |
Correct |
1327 ms |
8560 KB |
Output is correct |
107 |
Correct |
1732 ms |
8180 KB |
Output is correct |
108 |
Correct |
1727 ms |
9712 KB |
Output is correct |
109 |
Correct |
1578 ms |
8624 KB |
Output is correct |