# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
528028 |
2022-02-19T03:15:14 Z |
Olympia |
Bridges (APIO19_bridges) |
C++17 |
|
2477 ms |
19116 KB |
#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#include <stack>
//
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
using namespace std;
struct Updates{
int parentInd;
int prev_parent;
int compInd;
int prev_comp;
};
class DisjointSetUnion {
private:
vector<int> parent;
vector<int> compSize;
int n;
int connectedComponents;
stack<Updates> myStack;
public:
int cntr = 0;
int getConnectedComponents() const {
return connectedComponents;
}
int getNeighbors(int x) {
return compSize[find_head(x)];
}
public:
void resz(int sz) {
n = sz;
connectedComponents = sz;
parent.resize(sz), compSize.resize(sz);
for (int i = 0; i < n; i++) {
parent[i] = i, compSize[i] = 1;
}
}
int find_head(int x) const {
int cur = x;
while (cur != parent[cur]) {
cur = parent[cur];
}
return cur;
}
void join0(int x, int y) {
x = find_head(x);
y = find_head(y);
if (x == y) {
return;
}
if (compSize[x] > compSize[y]) {
swap(x, y);
}
parent[x] = y;
compSize[y] += compSize[x];
connectedComponents--;
}
void join1(int x, int y) {
x = find_head(x);
y = find_head(y);
if (x == y) {
return;
}
if (compSize[x] > compSize[y]) {
swap(x, y);
}
myStack.push({x, parent[x], y, compSize[y]}), cntr++;
parent[x] = y;
compSize[y] += compSize[x];
connectedComponents--;
}
void revert(int x) {
while (x--) {
Updates u = myStack.top();
myStack.pop();
parent[u.parentInd] = u.prev_parent;
compSize[u.compInd] = u.prev_comp;
connectedComponents++;
}
}
bool comp(int x, int y) {
return (find_head(x) == find_head(y));
}
};
class Query {
public:
int w;
int x;
int type;
int q;
Query(int w, int x, int type, int q) {
this->w = w, this->x = x, this->type = type, this->q = q;
}
bool operator<(const Query myQuery) const {
if (myQuery.w != w) return (myQuery.w < w);
if (myQuery.x != x) return (myQuery.x < x);
if (myQuery.type != type) return (myQuery.type < type);
return false;
}
};
bool comp_index(Query a, Query b) {
return (a.q < b.q);
}
void compress(vector<pair<pair<int, int>, int>> &edges, vector<vector<Query>> &blocks) {
vector<int> w;
for (auto &p: edges) w.push_back(p.second);
for (auto &v: blocks) for (auto &q: v) w.push_back(q.w);
sort(w.begin(), w.end());
int prev = -1;
int cntr = 0;
map<int,int> myMap;
for (int i = 0; i < w.size(); i++) {
if (w[i] != prev) {
prev = w[i];
myMap[w[i]] = cntr++;
}
}
for (int i = 0; i < edges.size(); i++) {
edges[i].second = myMap[edges[i].second];
}
for (int i = 0; i < blocks.size(); i++) {
for (int j = 0; j < blocks[i].size(); j++) {
blocks[i][j].w = myMap[blocks[i][j].w];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<pair<pair<int, int>, int>> edges;
for (int i = 0; i < M; i++) {
int x, y, z;
cin >> x >> y >> z;
x--, y--;
edges.push_back({{x, y}, z});
}
int Q;
cin >> Q;
vector<vector<Query>> blocks;
blocks.emplace_back();
for (int i = 0; i < Q; i++) {
if (blocks.back().size() > 1200) {
blocks.emplace_back();
}
int t, w, x;
cin >> t >> x >> w;
t--;
x--;
blocks.back().emplace_back(Query(w, x, t, i));
}
compress(edges, blocks);
vector<int> default_edges(M);
for (int i = 0; i < M; i++) {
default_edges[i] = edges[i].second;
}
vector<pair<int, int>> myVec;
int total = 0;
for (auto &v: blocks) {
DisjointSetUnion dsu;
dsu.resz(N);
vector<int> uncertain;
int cnt[M];
for (int i = 0; i < M; i++) {
cnt[i] = 0;
}
for (Query& q: v) {
if (!q.type) {
uncertain.push_back(q.x);
cnt[q.x]++;
}
}
stack<pair<int,int>> myStack;
vector<int> mnt[v.size()];
for (int i = 0; i < v.size(); i++) {
if (!v[i].type) {
default_edges[v[i].x] = v[i].w;
myStack.push({v[i].x, v[i].w});
} else {
for (int j: uncertain) {
if (default_edges[j] >= v[i].w) {
mnt[i].push_back(j);
}
}
}
}
while (!myStack.empty()) {
default_edges[myStack.top().first] = myStack.top().second;
myStack.pop();
}
vector<int> e[M + Q];
for (int i = 0; i < M; i++) {
if (!cnt[i]) {
e[default_edges[i]].push_back(i);
}
}
sort (v.begin(), v.end());
int prev = M + Q;
for (int ind = 0; ind < v.size(); ind++) {
Query q = v[ind];
if (!q.type) {
continue;
}
for (int i = q.w; i < prev; i++) {
for (int j: e[i]) {
dsu.join0(edges[j].first.first, edges[j].first.second);
}
}
prev = q.w;
dsu.cntr = 0;
for (int x: mnt[v[ind].q - total]) {
dsu.join1(edges[x].first.first, edges[x].first.second);
}
myVec.emplace_back(q.q, dsu.getNeighbors(q.x));
dsu.revert(dsu.cntr);
}
sort(v.begin(), v.end(), comp_index);
for (Query &q: v) {
if (!q.type) {
default_edges[q.x] = q.w;
}
}
total += v.size();
}
sort(myVec.begin(), myVec.end());
for (auto &p: myVec) {
cout << p.second << '\n';
}
}
Compilation message
bridges.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
16 | #pragma GCC optimization ("O3")
|
bridges.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
17 | #pragma GCC optimization ("unroll-loops")
|
bridges.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
18 | #pragma GCC optimization ("Ofast")
|
bridges.cpp: In function 'void compress(std::vector<std::pair<std::pair<int, int>, int> >&, std::vector<std::vector<Query> >&)':
bridges.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int i = 0; i < w.size(); i++) {
| ~~^~~~~~~~~~
bridges.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
bridges.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Query> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (int i = 0; i < blocks.size(); i++) {
| ~~^~~~~~~~~~~~~~~
bridges.cpp:149:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for (int j = 0; j < blocks[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:204:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
204 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
bridges.cpp:228:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | for (int ind = 0; ind < v.size(); ind++) {
| ~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
42 ms |
2116 KB |
Output is correct |
4 |
Correct |
9 ms |
1356 KB |
Output is correct |
5 |
Correct |
40 ms |
2252 KB |
Output is correct |
6 |
Correct |
30 ms |
2308 KB |
Output is correct |
7 |
Correct |
38 ms |
2328 KB |
Output is correct |
8 |
Correct |
46 ms |
2160 KB |
Output is correct |
9 |
Correct |
55 ms |
3364 KB |
Output is correct |
10 |
Correct |
49 ms |
2160 KB |
Output is correct |
11 |
Correct |
48 ms |
2060 KB |
Output is correct |
12 |
Correct |
54 ms |
2372 KB |
Output is correct |
13 |
Correct |
51 ms |
2184 KB |
Output is correct |
14 |
Correct |
50 ms |
2076 KB |
Output is correct |
15 |
Correct |
51 ms |
2116 KB |
Output is correct |
16 |
Correct |
44 ms |
2812 KB |
Output is correct |
17 |
Correct |
45 ms |
2448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1645 ms |
14296 KB |
Output is correct |
2 |
Correct |
1672 ms |
14224 KB |
Output is correct |
3 |
Correct |
1592 ms |
14188 KB |
Output is correct |
4 |
Correct |
1734 ms |
14196 KB |
Output is correct |
5 |
Correct |
1722 ms |
14188 KB |
Output is correct |
6 |
Correct |
2401 ms |
13648 KB |
Output is correct |
7 |
Correct |
2448 ms |
13960 KB |
Output is correct |
8 |
Correct |
2391 ms |
14296 KB |
Output is correct |
9 |
Correct |
126 ms |
10352 KB |
Output is correct |
10 |
Correct |
1125 ms |
11156 KB |
Output is correct |
11 |
Correct |
1039 ms |
10624 KB |
Output is correct |
12 |
Correct |
1331 ms |
13872 KB |
Output is correct |
13 |
Correct |
1390 ms |
14284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1296 ms |
12700 KB |
Output is correct |
2 |
Correct |
1016 ms |
9896 KB |
Output is correct |
3 |
Correct |
1549 ms |
11812 KB |
Output is correct |
4 |
Correct |
1433 ms |
12724 KB |
Output is correct |
5 |
Correct |
113 ms |
10420 KB |
Output is correct |
6 |
Correct |
1513 ms |
12944 KB |
Output is correct |
7 |
Correct |
1198 ms |
12948 KB |
Output is correct |
8 |
Correct |
1050 ms |
12824 KB |
Output is correct |
9 |
Correct |
880 ms |
13080 KB |
Output is correct |
10 |
Correct |
788 ms |
12708 KB |
Output is correct |
11 |
Correct |
953 ms |
12916 KB |
Output is correct |
12 |
Correct |
825 ms |
12816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1831 ms |
19116 KB |
Output is correct |
2 |
Correct |
130 ms |
10356 KB |
Output is correct |
3 |
Correct |
208 ms |
11216 KB |
Output is correct |
4 |
Correct |
63 ms |
7072 KB |
Output is correct |
5 |
Correct |
481 ms |
12944 KB |
Output is correct |
6 |
Correct |
1930 ms |
18976 KB |
Output is correct |
7 |
Correct |
517 ms |
12872 KB |
Output is correct |
8 |
Correct |
958 ms |
14544 KB |
Output is correct |
9 |
Correct |
921 ms |
14440 KB |
Output is correct |
10 |
Correct |
843 ms |
14492 KB |
Output is correct |
11 |
Correct |
1410 ms |
16708 KB |
Output is correct |
12 |
Correct |
1488 ms |
16848 KB |
Output is correct |
13 |
Correct |
1285 ms |
16792 KB |
Output is correct |
14 |
Correct |
444 ms |
13096 KB |
Output is correct |
15 |
Correct |
452 ms |
13036 KB |
Output is correct |
16 |
Correct |
1819 ms |
18912 KB |
Output is correct |
17 |
Correct |
1767 ms |
18912 KB |
Output is correct |
18 |
Correct |
1997 ms |
18940 KB |
Output is correct |
19 |
Correct |
2037 ms |
18932 KB |
Output is correct |
20 |
Correct |
1418 ms |
17600 KB |
Output is correct |
21 |
Correct |
1337 ms |
17428 KB |
Output is correct |
22 |
Correct |
1842 ms |
18700 KB |
Output is correct |
23 |
Correct |
447 ms |
12016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1645 ms |
14296 KB |
Output is correct |
2 |
Correct |
1672 ms |
14224 KB |
Output is correct |
3 |
Correct |
1592 ms |
14188 KB |
Output is correct |
4 |
Correct |
1734 ms |
14196 KB |
Output is correct |
5 |
Correct |
1722 ms |
14188 KB |
Output is correct |
6 |
Correct |
2401 ms |
13648 KB |
Output is correct |
7 |
Correct |
2448 ms |
13960 KB |
Output is correct |
8 |
Correct |
2391 ms |
14296 KB |
Output is correct |
9 |
Correct |
126 ms |
10352 KB |
Output is correct |
10 |
Correct |
1125 ms |
11156 KB |
Output is correct |
11 |
Correct |
1039 ms |
10624 KB |
Output is correct |
12 |
Correct |
1331 ms |
13872 KB |
Output is correct |
13 |
Correct |
1390 ms |
14284 KB |
Output is correct |
14 |
Correct |
1296 ms |
12700 KB |
Output is correct |
15 |
Correct |
1016 ms |
9896 KB |
Output is correct |
16 |
Correct |
1549 ms |
11812 KB |
Output is correct |
17 |
Correct |
1433 ms |
12724 KB |
Output is correct |
18 |
Correct |
113 ms |
10420 KB |
Output is correct |
19 |
Correct |
1513 ms |
12944 KB |
Output is correct |
20 |
Correct |
1198 ms |
12948 KB |
Output is correct |
21 |
Correct |
1050 ms |
12824 KB |
Output is correct |
22 |
Correct |
880 ms |
13080 KB |
Output is correct |
23 |
Correct |
788 ms |
12708 KB |
Output is correct |
24 |
Correct |
953 ms |
12916 KB |
Output is correct |
25 |
Correct |
825 ms |
12816 KB |
Output is correct |
26 |
Correct |
1684 ms |
14260 KB |
Output is correct |
27 |
Correct |
2066 ms |
13248 KB |
Output is correct |
28 |
Correct |
1702 ms |
14300 KB |
Output is correct |
29 |
Correct |
1228 ms |
14224 KB |
Output is correct |
30 |
Correct |
1969 ms |
13732 KB |
Output is correct |
31 |
Correct |
2033 ms |
13616 KB |
Output is correct |
32 |
Correct |
1927 ms |
13688 KB |
Output is correct |
33 |
Correct |
1612 ms |
14260 KB |
Output is correct |
34 |
Correct |
1721 ms |
14300 KB |
Output is correct |
35 |
Correct |
1649 ms |
14212 KB |
Output is correct |
36 |
Correct |
1297 ms |
14284 KB |
Output is correct |
37 |
Correct |
1257 ms |
14196 KB |
Output is correct |
38 |
Correct |
1219 ms |
14304 KB |
Output is correct |
39 |
Correct |
1036 ms |
14280 KB |
Output is correct |
40 |
Correct |
1032 ms |
14292 KB |
Output is correct |
41 |
Correct |
954 ms |
14500 KB |
Output is correct |
42 |
Correct |
966 ms |
14336 KB |
Output is correct |
43 |
Correct |
958 ms |
14280 KB |
Output is correct |
44 |
Correct |
941 ms |
14216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
42 ms |
2116 KB |
Output is correct |
4 |
Correct |
9 ms |
1356 KB |
Output is correct |
5 |
Correct |
40 ms |
2252 KB |
Output is correct |
6 |
Correct |
30 ms |
2308 KB |
Output is correct |
7 |
Correct |
38 ms |
2328 KB |
Output is correct |
8 |
Correct |
46 ms |
2160 KB |
Output is correct |
9 |
Correct |
55 ms |
3364 KB |
Output is correct |
10 |
Correct |
49 ms |
2160 KB |
Output is correct |
11 |
Correct |
48 ms |
2060 KB |
Output is correct |
12 |
Correct |
54 ms |
2372 KB |
Output is correct |
13 |
Correct |
51 ms |
2184 KB |
Output is correct |
14 |
Correct |
50 ms |
2076 KB |
Output is correct |
15 |
Correct |
51 ms |
2116 KB |
Output is correct |
16 |
Correct |
44 ms |
2812 KB |
Output is correct |
17 |
Correct |
45 ms |
2448 KB |
Output is correct |
18 |
Correct |
1645 ms |
14296 KB |
Output is correct |
19 |
Correct |
1672 ms |
14224 KB |
Output is correct |
20 |
Correct |
1592 ms |
14188 KB |
Output is correct |
21 |
Correct |
1734 ms |
14196 KB |
Output is correct |
22 |
Correct |
1722 ms |
14188 KB |
Output is correct |
23 |
Correct |
2401 ms |
13648 KB |
Output is correct |
24 |
Correct |
2448 ms |
13960 KB |
Output is correct |
25 |
Correct |
2391 ms |
14296 KB |
Output is correct |
26 |
Correct |
126 ms |
10352 KB |
Output is correct |
27 |
Correct |
1125 ms |
11156 KB |
Output is correct |
28 |
Correct |
1039 ms |
10624 KB |
Output is correct |
29 |
Correct |
1331 ms |
13872 KB |
Output is correct |
30 |
Correct |
1390 ms |
14284 KB |
Output is correct |
31 |
Correct |
1296 ms |
12700 KB |
Output is correct |
32 |
Correct |
1016 ms |
9896 KB |
Output is correct |
33 |
Correct |
1549 ms |
11812 KB |
Output is correct |
34 |
Correct |
1433 ms |
12724 KB |
Output is correct |
35 |
Correct |
113 ms |
10420 KB |
Output is correct |
36 |
Correct |
1513 ms |
12944 KB |
Output is correct |
37 |
Correct |
1198 ms |
12948 KB |
Output is correct |
38 |
Correct |
1050 ms |
12824 KB |
Output is correct |
39 |
Correct |
880 ms |
13080 KB |
Output is correct |
40 |
Correct |
788 ms |
12708 KB |
Output is correct |
41 |
Correct |
953 ms |
12916 KB |
Output is correct |
42 |
Correct |
825 ms |
12816 KB |
Output is correct |
43 |
Correct |
1831 ms |
19116 KB |
Output is correct |
44 |
Correct |
130 ms |
10356 KB |
Output is correct |
45 |
Correct |
208 ms |
11216 KB |
Output is correct |
46 |
Correct |
63 ms |
7072 KB |
Output is correct |
47 |
Correct |
481 ms |
12944 KB |
Output is correct |
48 |
Correct |
1930 ms |
18976 KB |
Output is correct |
49 |
Correct |
517 ms |
12872 KB |
Output is correct |
50 |
Correct |
958 ms |
14544 KB |
Output is correct |
51 |
Correct |
921 ms |
14440 KB |
Output is correct |
52 |
Correct |
843 ms |
14492 KB |
Output is correct |
53 |
Correct |
1410 ms |
16708 KB |
Output is correct |
54 |
Correct |
1488 ms |
16848 KB |
Output is correct |
55 |
Correct |
1285 ms |
16792 KB |
Output is correct |
56 |
Correct |
444 ms |
13096 KB |
Output is correct |
57 |
Correct |
452 ms |
13036 KB |
Output is correct |
58 |
Correct |
1819 ms |
18912 KB |
Output is correct |
59 |
Correct |
1767 ms |
18912 KB |
Output is correct |
60 |
Correct |
1997 ms |
18940 KB |
Output is correct |
61 |
Correct |
2037 ms |
18932 KB |
Output is correct |
62 |
Correct |
1418 ms |
17600 KB |
Output is correct |
63 |
Correct |
1337 ms |
17428 KB |
Output is correct |
64 |
Correct |
1842 ms |
18700 KB |
Output is correct |
65 |
Correct |
447 ms |
12016 KB |
Output is correct |
66 |
Correct |
1684 ms |
14260 KB |
Output is correct |
67 |
Correct |
2066 ms |
13248 KB |
Output is correct |
68 |
Correct |
1702 ms |
14300 KB |
Output is correct |
69 |
Correct |
1228 ms |
14224 KB |
Output is correct |
70 |
Correct |
1969 ms |
13732 KB |
Output is correct |
71 |
Correct |
2033 ms |
13616 KB |
Output is correct |
72 |
Correct |
1927 ms |
13688 KB |
Output is correct |
73 |
Correct |
1612 ms |
14260 KB |
Output is correct |
74 |
Correct |
1721 ms |
14300 KB |
Output is correct |
75 |
Correct |
1649 ms |
14212 KB |
Output is correct |
76 |
Correct |
1297 ms |
14284 KB |
Output is correct |
77 |
Correct |
1257 ms |
14196 KB |
Output is correct |
78 |
Correct |
1219 ms |
14304 KB |
Output is correct |
79 |
Correct |
1036 ms |
14280 KB |
Output is correct |
80 |
Correct |
1032 ms |
14292 KB |
Output is correct |
81 |
Correct |
954 ms |
14500 KB |
Output is correct |
82 |
Correct |
966 ms |
14336 KB |
Output is correct |
83 |
Correct |
958 ms |
14280 KB |
Output is correct |
84 |
Correct |
941 ms |
14216 KB |
Output is correct |
85 |
Correct |
2325 ms |
18600 KB |
Output is correct |
86 |
Correct |
233 ms |
11216 KB |
Output is correct |
87 |
Correct |
118 ms |
9364 KB |
Output is correct |
88 |
Correct |
982 ms |
13236 KB |
Output is correct |
89 |
Correct |
2278 ms |
18600 KB |
Output is correct |
90 |
Correct |
964 ms |
13260 KB |
Output is correct |
91 |
Correct |
1662 ms |
14296 KB |
Output is correct |
92 |
Correct |
1648 ms |
14308 KB |
Output is correct |
93 |
Correct |
2342 ms |
14412 KB |
Output is correct |
94 |
Correct |
1983 ms |
16392 KB |
Output is correct |
95 |
Correct |
1931 ms |
16488 KB |
Output is correct |
96 |
Correct |
2284 ms |
16644 KB |
Output is correct |
97 |
Correct |
607 ms |
13328 KB |
Output is correct |
98 |
Correct |
685 ms |
11636 KB |
Output is correct |
99 |
Correct |
2298 ms |
18460 KB |
Output is correct |
100 |
Correct |
2277 ms |
18424 KB |
Output is correct |
101 |
Correct |
2464 ms |
18448 KB |
Output is correct |
102 |
Correct |
2378 ms |
18600 KB |
Output is correct |
103 |
Correct |
2477 ms |
17388 KB |
Output is correct |
104 |
Correct |
2450 ms |
17352 KB |
Output is correct |
105 |
Correct |
1825 ms |
17168 KB |
Output is correct |
106 |
Correct |
1514 ms |
16396 KB |
Output is correct |
107 |
Correct |
1666 ms |
17536 KB |
Output is correct |
108 |
Correct |
2432 ms |
18444 KB |
Output is correct |
109 |
Correct |
1276 ms |
13264 KB |
Output is correct |