# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
126699 |
2019-07-08T09:32:01 Z |
keko37 |
Bridges (APIO19_bridges) |
C++14 |
|
2605 ms |
14744 KB |
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int SIZ = 650;
int n, m, q, br;
int tip[MAXN], qx[MAXN], qv[MAXN];
int a[MAXN], b[MAXN], w[MAXN], sol[MAXN];
int par[MAXN], siz[MAXN], na[MAXN], nb[MAXN], novi[MAXN], bio[MAXN];
bool ok[MAXN];
vector < pair <int, int> > upiti, st, tmp, fin;
vector <int> curr, magic, visited;
vector <pair <int, int> > v[MAXN];
void load () {
cin >> n >> m;
for (int i=1; i<=m; i++) {
cin >> a[i] >> b[i] >> w[i];
st.push_back(make_pair(w[i], i));
}
st.push_back(make_pair(0, 0));
sort(st.begin(), st.end());
cin >> q;
for (int i=1; i<=q; i++) {
cin >> tip[i] >> qx[i] >> qv[i];
}
}
int nadi (int x) {
if (x == par[x]) return x;
return par[x] = nadi(par[x]);
}
void spoji (int x, int y) {
x = nadi(x); y = nadi(y);
if (x == y) return;
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
}
int lim;
void dfs (int x) {
if (bio[x]) return;
bio[x] = 1;
visited.push_back(x);
br += siz[x];
for (auto sus : v[x]) {
if (sus.second >= lim) dfs(sus.first);
}
}
void obradi_upit (int ind) {
for (auto e : magic) novi[e] = w[e];
for (auto i : curr) {
if (i >= ind) break;
novi[qx[i]] = qv[i];
}
for (auto e : magic) {
na[e] = nadi(a[e]);
nb[e] = nadi(b[e]);
//cout << "edge " << e << " " << na[e] << " " << nb[e] << " " << novi[e] << endl;
}
for (auto e : magic) {
v[na[e]].push_back(make_pair(nb[e], novi[e]));
v[nb[e]].push_back(make_pair(na[e], novi[e]));
}
visited.clear();
br = 0; lim = qv[ind];
dfs(nadi(qx[ind]));
sol[ind] = br;
for (auto x : visited) {
bio[x] = 0;
}
for (auto e : magic) {
v[na[e]].clear();
v[nb[e]].clear();
}
}
void update () {
for (auto i : curr) {
w[qx[i]] = qv[i];
}
tmp.clear(); fin.clear();
for (auto e : magic) tmp.push_back(make_pair(w[e], e));
sort(tmp.begin(), tmp.end());
int p = 0;
for (int i=0; i<tmp.size(); i++) {
while (p < st.size() && st[p].first <= tmp[i].first) {
if (ok[st[p].second] == 0) {
fin.push_back(st[p]);
}
p++;
}
fin.push_back(tmp[i]);
}
for (int i=p; i<st.size(); i++) {
if (ok[st[i].second] == 0) fin.push_back(st[i]);
}
swap(st, fin);
}
void obradi_bucket (int ll, int rr) {
for (int i=1; i<=n; i++) {
par[i] = i; siz[i] = 1;
}
upiti.clear(); curr.clear(); magic.clear();
for (int i = ll; i <= rr; i++) {
if (tip[i] == 1) {
ok[qx[i]] = 1;
magic.push_back(qx[i]);
curr.push_back(i);
} else {
upiti.push_back(make_pair(qv[i], i));
}
}
sort(magic.begin(), magic.end());
magic.erase(unique(magic.begin(), magic.end()), magic.end());
sort(upiti.begin(), upiti.end());
int p = (int)st.size() - 1;
for (int i = (int)upiti.size()-1; i >= 0; i--) {
int ind = upiti[i].second;
//cout << "sad na upitu " << ind << " " << qv[ind] << endl;
while (st[p].first >= qv[ind]) {
if (ok[st[p].second] == 0) spoji(a[st[p].second], b[st[p].second]);
p--;
}
//cout << "sad cu ga obradit" << endl;
obradi_upit(ind);
}
update();
//for (auto par : st) cout << par.first << " " << par.second << endl;
for (auto i : curr) ok[qx[i]] = 0;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
load();
for (int i=1; i<=q; i += SIZ) {
obradi_bucket(i, min(i + SIZ - 1, q));
}
for (int i=1; i<=q; i++) {
if (tip[i] == 2) cout << sol[i] << '\n';
}
return 0;
}
Compilation message
bridges.cpp: In function 'void update()':
bridges.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<tmp.size(); i++) {
~^~~~~~~~~~~
bridges.cpp:93:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (p < st.size() && st[p].first <= tmp[i].first) {
~~^~~~~~~~~~~
bridges.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=p; i<st.size(); i++) {
~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2808 KB |
Output is correct |
3 |
Correct |
72 ms |
3192 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
30 ms |
2936 KB |
Output is correct |
6 |
Correct |
28 ms |
2936 KB |
Output is correct |
7 |
Correct |
29 ms |
2936 KB |
Output is correct |
8 |
Correct |
29 ms |
2936 KB |
Output is correct |
9 |
Correct |
31 ms |
2940 KB |
Output is correct |
10 |
Correct |
28 ms |
2936 KB |
Output is correct |
11 |
Correct |
27 ms |
2936 KB |
Output is correct |
12 |
Correct |
27 ms |
2936 KB |
Output is correct |
13 |
Correct |
37 ms |
3064 KB |
Output is correct |
14 |
Correct |
35 ms |
2936 KB |
Output is correct |
15 |
Correct |
30 ms |
2936 KB |
Output is correct |
16 |
Correct |
29 ms |
2936 KB |
Output is correct |
17 |
Correct |
29 ms |
2936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1887 ms |
8636 KB |
Output is correct |
2 |
Correct |
1920 ms |
11384 KB |
Output is correct |
3 |
Correct |
1893 ms |
11500 KB |
Output is correct |
4 |
Correct |
1840 ms |
11380 KB |
Output is correct |
5 |
Correct |
1797 ms |
11512 KB |
Output is correct |
6 |
Correct |
2063 ms |
10308 KB |
Output is correct |
7 |
Correct |
1883 ms |
10232 KB |
Output is correct |
8 |
Correct |
1834 ms |
10256 KB |
Output is correct |
9 |
Correct |
49 ms |
5884 KB |
Output is correct |
10 |
Correct |
1902 ms |
10252 KB |
Output is correct |
11 |
Correct |
1755 ms |
10252 KB |
Output is correct |
12 |
Correct |
862 ms |
10104 KB |
Output is correct |
13 |
Correct |
1160 ms |
10428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1716 ms |
7220 KB |
Output is correct |
2 |
Correct |
1332 ms |
6968 KB |
Output is correct |
3 |
Correct |
1744 ms |
9724 KB |
Output is correct |
4 |
Correct |
1718 ms |
9760 KB |
Output is correct |
5 |
Correct |
48 ms |
6008 KB |
Output is correct |
6 |
Correct |
1600 ms |
9712 KB |
Output is correct |
7 |
Correct |
1637 ms |
9596 KB |
Output is correct |
8 |
Correct |
1637 ms |
9472 KB |
Output is correct |
9 |
Correct |
671 ms |
9024 KB |
Output is correct |
10 |
Correct |
662 ms |
9128 KB |
Output is correct |
11 |
Correct |
976 ms |
9600 KB |
Output is correct |
12 |
Correct |
994 ms |
9768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
965 ms |
8284 KB |
Output is correct |
2 |
Correct |
47 ms |
5880 KB |
Output is correct |
3 |
Correct |
110 ms |
8044 KB |
Output is correct |
4 |
Correct |
75 ms |
7848 KB |
Output is correct |
5 |
Correct |
652 ms |
9748 KB |
Output is correct |
6 |
Correct |
958 ms |
9456 KB |
Output is correct |
7 |
Correct |
656 ms |
9816 KB |
Output is correct |
8 |
Correct |
532 ms |
8120 KB |
Output is correct |
9 |
Correct |
510 ms |
8192 KB |
Output is correct |
10 |
Correct |
514 ms |
8196 KB |
Output is correct |
11 |
Correct |
895 ms |
8828 KB |
Output is correct |
12 |
Correct |
858 ms |
8684 KB |
Output is correct |
13 |
Correct |
902 ms |
9084 KB |
Output is correct |
14 |
Correct |
594 ms |
9860 KB |
Output is correct |
15 |
Correct |
636 ms |
9816 KB |
Output is correct |
16 |
Correct |
1097 ms |
9592 KB |
Output is correct |
17 |
Correct |
1102 ms |
9328 KB |
Output is correct |
18 |
Correct |
1092 ms |
9544 KB |
Output is correct |
19 |
Correct |
1097 ms |
9472 KB |
Output is correct |
20 |
Correct |
1008 ms |
9228 KB |
Output is correct |
21 |
Correct |
1018 ms |
9172 KB |
Output is correct |
22 |
Correct |
1053 ms |
9472 KB |
Output is correct |
23 |
Correct |
831 ms |
9184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1887 ms |
8636 KB |
Output is correct |
2 |
Correct |
1920 ms |
11384 KB |
Output is correct |
3 |
Correct |
1893 ms |
11500 KB |
Output is correct |
4 |
Correct |
1840 ms |
11380 KB |
Output is correct |
5 |
Correct |
1797 ms |
11512 KB |
Output is correct |
6 |
Correct |
2063 ms |
10308 KB |
Output is correct |
7 |
Correct |
1883 ms |
10232 KB |
Output is correct |
8 |
Correct |
1834 ms |
10256 KB |
Output is correct |
9 |
Correct |
49 ms |
5884 KB |
Output is correct |
10 |
Correct |
1902 ms |
10252 KB |
Output is correct |
11 |
Correct |
1755 ms |
10252 KB |
Output is correct |
12 |
Correct |
862 ms |
10104 KB |
Output is correct |
13 |
Correct |
1160 ms |
10428 KB |
Output is correct |
14 |
Correct |
1716 ms |
7220 KB |
Output is correct |
15 |
Correct |
1332 ms |
6968 KB |
Output is correct |
16 |
Correct |
1744 ms |
9724 KB |
Output is correct |
17 |
Correct |
1718 ms |
9760 KB |
Output is correct |
18 |
Correct |
48 ms |
6008 KB |
Output is correct |
19 |
Correct |
1600 ms |
9712 KB |
Output is correct |
20 |
Correct |
1637 ms |
9596 KB |
Output is correct |
21 |
Correct |
1637 ms |
9472 KB |
Output is correct |
22 |
Correct |
671 ms |
9024 KB |
Output is correct |
23 |
Correct |
662 ms |
9128 KB |
Output is correct |
24 |
Correct |
976 ms |
9600 KB |
Output is correct |
25 |
Correct |
994 ms |
9768 KB |
Output is correct |
26 |
Correct |
1946 ms |
11116 KB |
Output is correct |
27 |
Correct |
2069 ms |
11296 KB |
Output is correct |
28 |
Correct |
2106 ms |
11384 KB |
Output is correct |
29 |
Correct |
1916 ms |
11392 KB |
Output is correct |
30 |
Correct |
2241 ms |
11444 KB |
Output is correct |
31 |
Correct |
2230 ms |
11336 KB |
Output is correct |
32 |
Correct |
2199 ms |
11228 KB |
Output is correct |
33 |
Correct |
2093 ms |
11320 KB |
Output is correct |
34 |
Correct |
2080 ms |
11368 KB |
Output is correct |
35 |
Correct |
2148 ms |
11284 KB |
Output is correct |
36 |
Correct |
1952 ms |
11372 KB |
Output is correct |
37 |
Correct |
2019 ms |
11252 KB |
Output is correct |
38 |
Correct |
1958 ms |
11348 KB |
Output is correct |
39 |
Correct |
924 ms |
10744 KB |
Output is correct |
40 |
Correct |
925 ms |
10740 KB |
Output is correct |
41 |
Correct |
924 ms |
10756 KB |
Output is correct |
42 |
Correct |
1205 ms |
11256 KB |
Output is correct |
43 |
Correct |
1231 ms |
11288 KB |
Output is correct |
44 |
Correct |
1186 ms |
11388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2808 KB |
Output is correct |
3 |
Correct |
72 ms |
3192 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
30 ms |
2936 KB |
Output is correct |
6 |
Correct |
28 ms |
2936 KB |
Output is correct |
7 |
Correct |
29 ms |
2936 KB |
Output is correct |
8 |
Correct |
29 ms |
2936 KB |
Output is correct |
9 |
Correct |
31 ms |
2940 KB |
Output is correct |
10 |
Correct |
28 ms |
2936 KB |
Output is correct |
11 |
Correct |
27 ms |
2936 KB |
Output is correct |
12 |
Correct |
27 ms |
2936 KB |
Output is correct |
13 |
Correct |
37 ms |
3064 KB |
Output is correct |
14 |
Correct |
35 ms |
2936 KB |
Output is correct |
15 |
Correct |
30 ms |
2936 KB |
Output is correct |
16 |
Correct |
29 ms |
2936 KB |
Output is correct |
17 |
Correct |
29 ms |
2936 KB |
Output is correct |
18 |
Correct |
1887 ms |
8636 KB |
Output is correct |
19 |
Correct |
1920 ms |
11384 KB |
Output is correct |
20 |
Correct |
1893 ms |
11500 KB |
Output is correct |
21 |
Correct |
1840 ms |
11380 KB |
Output is correct |
22 |
Correct |
1797 ms |
11512 KB |
Output is correct |
23 |
Correct |
2063 ms |
10308 KB |
Output is correct |
24 |
Correct |
1883 ms |
10232 KB |
Output is correct |
25 |
Correct |
1834 ms |
10256 KB |
Output is correct |
26 |
Correct |
49 ms |
5884 KB |
Output is correct |
27 |
Correct |
1902 ms |
10252 KB |
Output is correct |
28 |
Correct |
1755 ms |
10252 KB |
Output is correct |
29 |
Correct |
862 ms |
10104 KB |
Output is correct |
30 |
Correct |
1160 ms |
10428 KB |
Output is correct |
31 |
Correct |
1716 ms |
7220 KB |
Output is correct |
32 |
Correct |
1332 ms |
6968 KB |
Output is correct |
33 |
Correct |
1744 ms |
9724 KB |
Output is correct |
34 |
Correct |
1718 ms |
9760 KB |
Output is correct |
35 |
Correct |
48 ms |
6008 KB |
Output is correct |
36 |
Correct |
1600 ms |
9712 KB |
Output is correct |
37 |
Correct |
1637 ms |
9596 KB |
Output is correct |
38 |
Correct |
1637 ms |
9472 KB |
Output is correct |
39 |
Correct |
671 ms |
9024 KB |
Output is correct |
40 |
Correct |
662 ms |
9128 KB |
Output is correct |
41 |
Correct |
976 ms |
9600 KB |
Output is correct |
42 |
Correct |
994 ms |
9768 KB |
Output is correct |
43 |
Correct |
965 ms |
8284 KB |
Output is correct |
44 |
Correct |
47 ms |
5880 KB |
Output is correct |
45 |
Correct |
110 ms |
8044 KB |
Output is correct |
46 |
Correct |
75 ms |
7848 KB |
Output is correct |
47 |
Correct |
652 ms |
9748 KB |
Output is correct |
48 |
Correct |
958 ms |
9456 KB |
Output is correct |
49 |
Correct |
656 ms |
9816 KB |
Output is correct |
50 |
Correct |
532 ms |
8120 KB |
Output is correct |
51 |
Correct |
510 ms |
8192 KB |
Output is correct |
52 |
Correct |
514 ms |
8196 KB |
Output is correct |
53 |
Correct |
895 ms |
8828 KB |
Output is correct |
54 |
Correct |
858 ms |
8684 KB |
Output is correct |
55 |
Correct |
902 ms |
9084 KB |
Output is correct |
56 |
Correct |
594 ms |
9860 KB |
Output is correct |
57 |
Correct |
636 ms |
9816 KB |
Output is correct |
58 |
Correct |
1097 ms |
9592 KB |
Output is correct |
59 |
Correct |
1102 ms |
9328 KB |
Output is correct |
60 |
Correct |
1092 ms |
9544 KB |
Output is correct |
61 |
Correct |
1097 ms |
9472 KB |
Output is correct |
62 |
Correct |
1008 ms |
9228 KB |
Output is correct |
63 |
Correct |
1018 ms |
9172 KB |
Output is correct |
64 |
Correct |
1053 ms |
9472 KB |
Output is correct |
65 |
Correct |
831 ms |
9184 KB |
Output is correct |
66 |
Correct |
1946 ms |
11116 KB |
Output is correct |
67 |
Correct |
2069 ms |
11296 KB |
Output is correct |
68 |
Correct |
2106 ms |
11384 KB |
Output is correct |
69 |
Correct |
1916 ms |
11392 KB |
Output is correct |
70 |
Correct |
2241 ms |
11444 KB |
Output is correct |
71 |
Correct |
2230 ms |
11336 KB |
Output is correct |
72 |
Correct |
2199 ms |
11228 KB |
Output is correct |
73 |
Correct |
2093 ms |
11320 KB |
Output is correct |
74 |
Correct |
2080 ms |
11368 KB |
Output is correct |
75 |
Correct |
2148 ms |
11284 KB |
Output is correct |
76 |
Correct |
1952 ms |
11372 KB |
Output is correct |
77 |
Correct |
2019 ms |
11252 KB |
Output is correct |
78 |
Correct |
1958 ms |
11348 KB |
Output is correct |
79 |
Correct |
924 ms |
10744 KB |
Output is correct |
80 |
Correct |
925 ms |
10740 KB |
Output is correct |
81 |
Correct |
924 ms |
10756 KB |
Output is correct |
82 |
Correct |
1205 ms |
11256 KB |
Output is correct |
83 |
Correct |
1231 ms |
11288 KB |
Output is correct |
84 |
Correct |
1186 ms |
11388 KB |
Output is correct |
85 |
Correct |
2455 ms |
14632 KB |
Output is correct |
86 |
Correct |
226 ms |
9456 KB |
Output is correct |
87 |
Correct |
182 ms |
9584 KB |
Output is correct |
88 |
Correct |
1963 ms |
13172 KB |
Output is correct |
89 |
Correct |
2475 ms |
14544 KB |
Output is correct |
90 |
Correct |
1854 ms |
12020 KB |
Output is correct |
91 |
Correct |
2054 ms |
11320 KB |
Output is correct |
92 |
Correct |
2023 ms |
11512 KB |
Output is correct |
93 |
Correct |
2064 ms |
10488 KB |
Output is correct |
94 |
Correct |
2388 ms |
13300 KB |
Output is correct |
95 |
Correct |
2378 ms |
13408 KB |
Output is correct |
96 |
Correct |
1970 ms |
11892 KB |
Output is correct |
97 |
Correct |
1038 ms |
11376 KB |
Output is correct |
98 |
Correct |
1304 ms |
11980 KB |
Output is correct |
99 |
Correct |
2573 ms |
14520 KB |
Output is correct |
100 |
Correct |
2556 ms |
14548 KB |
Output is correct |
101 |
Correct |
2595 ms |
14744 KB |
Output is correct |
102 |
Correct |
2605 ms |
14652 KB |
Output is correct |
103 |
Correct |
2065 ms |
12012 KB |
Output is correct |
104 |
Correct |
2120 ms |
12072 KB |
Output is correct |
105 |
Correct |
1557 ms |
12540 KB |
Output is correct |
106 |
Correct |
1169 ms |
12568 KB |
Output is correct |
107 |
Correct |
1320 ms |
11700 KB |
Output is correct |
108 |
Correct |
2261 ms |
12444 KB |
Output is correct |
109 |
Correct |
1935 ms |
10336 KB |
Output is correct |