# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
126705 |
2019-07-08T09:41:52 Z |
keko37 |
Bridges (APIO19_bridges) |
C++14 |
|
2626 ms |
11300 KB |
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int SIZ = 650;
int n, m, q, br, cnt;
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] == cnt) return;
bio[x] = cnt;
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]));
}
cnt++;
br = 0; lim = qv[ind];
dfs(nadi(qx[ind]));
sol[ind] = br;
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:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<tmp.size(); i++) {
~^~~~~~~~~~~
bridges.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (p < st.size() && st[p].first <= tmp[i].first) {
~~^~~~~~~~~~~
bridges.cpp:97: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 |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
74 ms |
3196 KB |
Output is correct |
4 |
Correct |
22 ms |
3064 KB |
Output is correct |
5 |
Correct |
31 ms |
3064 KB |
Output is correct |
6 |
Correct |
30 ms |
3064 KB |
Output is correct |
7 |
Correct |
29 ms |
3192 KB |
Output is correct |
8 |
Correct |
29 ms |
3064 KB |
Output is correct |
9 |
Correct |
30 ms |
3064 KB |
Output is correct |
10 |
Correct |
28 ms |
3064 KB |
Output is correct |
11 |
Correct |
27 ms |
3192 KB |
Output is correct |
12 |
Correct |
27 ms |
3064 KB |
Output is correct |
13 |
Correct |
37 ms |
3192 KB |
Output is correct |
14 |
Correct |
35 ms |
3052 KB |
Output is correct |
15 |
Correct |
30 ms |
3064 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 |
1911 ms |
8892 KB |
Output is correct |
2 |
Correct |
1912 ms |
9028 KB |
Output is correct |
3 |
Correct |
1880 ms |
8764 KB |
Output is correct |
4 |
Correct |
1808 ms |
8988 KB |
Output is correct |
5 |
Correct |
1851 ms |
8740 KB |
Output is correct |
6 |
Correct |
1972 ms |
7776 KB |
Output is correct |
7 |
Correct |
1836 ms |
7744 KB |
Output is correct |
8 |
Correct |
1789 ms |
8088 KB |
Output is correct |
9 |
Correct |
47 ms |
4728 KB |
Output is correct |
10 |
Correct |
1767 ms |
8888 KB |
Output is correct |
11 |
Correct |
1679 ms |
8820 KB |
Output is correct |
12 |
Correct |
872 ms |
7840 KB |
Output is correct |
13 |
Correct |
1200 ms |
7932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1725 ms |
7572 KB |
Output is correct |
2 |
Correct |
1325 ms |
5616 KB |
Output is correct |
3 |
Correct |
1672 ms |
7560 KB |
Output is correct |
4 |
Correct |
1674 ms |
7608 KB |
Output is correct |
5 |
Correct |
51 ms |
4652 KB |
Output is correct |
6 |
Correct |
1646 ms |
7456 KB |
Output is correct |
7 |
Correct |
1609 ms |
7444 KB |
Output is correct |
8 |
Correct |
1629 ms |
7392 KB |
Output is correct |
9 |
Correct |
652 ms |
7164 KB |
Output is correct |
10 |
Correct |
659 ms |
7032 KB |
Output is correct |
11 |
Correct |
986 ms |
7664 KB |
Output is correct |
12 |
Correct |
996 ms |
7736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
940 ms |
8588 KB |
Output is correct |
2 |
Correct |
47 ms |
4728 KB |
Output is correct |
3 |
Correct |
113 ms |
6768 KB |
Output is correct |
4 |
Correct |
75 ms |
6768 KB |
Output is correct |
5 |
Correct |
666 ms |
8696 KB |
Output is correct |
6 |
Correct |
967 ms |
8696 KB |
Output is correct |
7 |
Correct |
644 ms |
8568 KB |
Output is correct |
8 |
Correct |
523 ms |
7136 KB |
Output is correct |
9 |
Correct |
512 ms |
7160 KB |
Output is correct |
10 |
Correct |
522 ms |
7184 KB |
Output is correct |
11 |
Correct |
874 ms |
7916 KB |
Output is correct |
12 |
Correct |
871 ms |
7796 KB |
Output is correct |
13 |
Correct |
888 ms |
8056 KB |
Output is correct |
14 |
Correct |
636 ms |
8672 KB |
Output is correct |
15 |
Correct |
647 ms |
8692 KB |
Output is correct |
16 |
Correct |
1099 ms |
8696 KB |
Output is correct |
17 |
Correct |
1177 ms |
8700 KB |
Output is correct |
18 |
Correct |
1061 ms |
8840 KB |
Output is correct |
19 |
Correct |
1069 ms |
8564 KB |
Output is correct |
20 |
Correct |
1020 ms |
8268 KB |
Output is correct |
21 |
Correct |
1006 ms |
8360 KB |
Output is correct |
22 |
Correct |
1020 ms |
8732 KB |
Output is correct |
23 |
Correct |
831 ms |
8136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1911 ms |
8892 KB |
Output is correct |
2 |
Correct |
1912 ms |
9028 KB |
Output is correct |
3 |
Correct |
1880 ms |
8764 KB |
Output is correct |
4 |
Correct |
1808 ms |
8988 KB |
Output is correct |
5 |
Correct |
1851 ms |
8740 KB |
Output is correct |
6 |
Correct |
1972 ms |
7776 KB |
Output is correct |
7 |
Correct |
1836 ms |
7744 KB |
Output is correct |
8 |
Correct |
1789 ms |
8088 KB |
Output is correct |
9 |
Correct |
47 ms |
4728 KB |
Output is correct |
10 |
Correct |
1767 ms |
8888 KB |
Output is correct |
11 |
Correct |
1679 ms |
8820 KB |
Output is correct |
12 |
Correct |
872 ms |
7840 KB |
Output is correct |
13 |
Correct |
1200 ms |
7932 KB |
Output is correct |
14 |
Correct |
1725 ms |
7572 KB |
Output is correct |
15 |
Correct |
1325 ms |
5616 KB |
Output is correct |
16 |
Correct |
1672 ms |
7560 KB |
Output is correct |
17 |
Correct |
1674 ms |
7608 KB |
Output is correct |
18 |
Correct |
51 ms |
4652 KB |
Output is correct |
19 |
Correct |
1646 ms |
7456 KB |
Output is correct |
20 |
Correct |
1609 ms |
7444 KB |
Output is correct |
21 |
Correct |
1629 ms |
7392 KB |
Output is correct |
22 |
Correct |
652 ms |
7164 KB |
Output is correct |
23 |
Correct |
659 ms |
7032 KB |
Output is correct |
24 |
Correct |
986 ms |
7664 KB |
Output is correct |
25 |
Correct |
996 ms |
7736 KB |
Output is correct |
26 |
Correct |
1871 ms |
8664 KB |
Output is correct |
27 |
Correct |
2041 ms |
8904 KB |
Output is correct |
28 |
Correct |
2058 ms |
8964 KB |
Output is correct |
29 |
Correct |
1903 ms |
8860 KB |
Output is correct |
30 |
Correct |
2238 ms |
8852 KB |
Output is correct |
31 |
Correct |
2249 ms |
8888 KB |
Output is correct |
32 |
Correct |
2185 ms |
8976 KB |
Output is correct |
33 |
Correct |
2103 ms |
8924 KB |
Output is correct |
34 |
Correct |
2101 ms |
8728 KB |
Output is correct |
35 |
Correct |
2081 ms |
8864 KB |
Output is correct |
36 |
Correct |
1998 ms |
8820 KB |
Output is correct |
37 |
Correct |
1950 ms |
8748 KB |
Output is correct |
38 |
Correct |
1962 ms |
8812 KB |
Output is correct |
39 |
Correct |
945 ms |
8260 KB |
Output is correct |
40 |
Correct |
928 ms |
8212 KB |
Output is correct |
41 |
Correct |
941 ms |
8208 KB |
Output is correct |
42 |
Correct |
1193 ms |
8884 KB |
Output is correct |
43 |
Correct |
1196 ms |
9052 KB |
Output is correct |
44 |
Correct |
1183 ms |
9084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
74 ms |
3196 KB |
Output is correct |
4 |
Correct |
22 ms |
3064 KB |
Output is correct |
5 |
Correct |
31 ms |
3064 KB |
Output is correct |
6 |
Correct |
30 ms |
3064 KB |
Output is correct |
7 |
Correct |
29 ms |
3192 KB |
Output is correct |
8 |
Correct |
29 ms |
3064 KB |
Output is correct |
9 |
Correct |
30 ms |
3064 KB |
Output is correct |
10 |
Correct |
28 ms |
3064 KB |
Output is correct |
11 |
Correct |
27 ms |
3192 KB |
Output is correct |
12 |
Correct |
27 ms |
3064 KB |
Output is correct |
13 |
Correct |
37 ms |
3192 KB |
Output is correct |
14 |
Correct |
35 ms |
3052 KB |
Output is correct |
15 |
Correct |
30 ms |
3064 KB |
Output is correct |
16 |
Correct |
29 ms |
2936 KB |
Output is correct |
17 |
Correct |
29 ms |
2936 KB |
Output is correct |
18 |
Correct |
1911 ms |
8892 KB |
Output is correct |
19 |
Correct |
1912 ms |
9028 KB |
Output is correct |
20 |
Correct |
1880 ms |
8764 KB |
Output is correct |
21 |
Correct |
1808 ms |
8988 KB |
Output is correct |
22 |
Correct |
1851 ms |
8740 KB |
Output is correct |
23 |
Correct |
1972 ms |
7776 KB |
Output is correct |
24 |
Correct |
1836 ms |
7744 KB |
Output is correct |
25 |
Correct |
1789 ms |
8088 KB |
Output is correct |
26 |
Correct |
47 ms |
4728 KB |
Output is correct |
27 |
Correct |
1767 ms |
8888 KB |
Output is correct |
28 |
Correct |
1679 ms |
8820 KB |
Output is correct |
29 |
Correct |
872 ms |
7840 KB |
Output is correct |
30 |
Correct |
1200 ms |
7932 KB |
Output is correct |
31 |
Correct |
1725 ms |
7572 KB |
Output is correct |
32 |
Correct |
1325 ms |
5616 KB |
Output is correct |
33 |
Correct |
1672 ms |
7560 KB |
Output is correct |
34 |
Correct |
1674 ms |
7608 KB |
Output is correct |
35 |
Correct |
51 ms |
4652 KB |
Output is correct |
36 |
Correct |
1646 ms |
7456 KB |
Output is correct |
37 |
Correct |
1609 ms |
7444 KB |
Output is correct |
38 |
Correct |
1629 ms |
7392 KB |
Output is correct |
39 |
Correct |
652 ms |
7164 KB |
Output is correct |
40 |
Correct |
659 ms |
7032 KB |
Output is correct |
41 |
Correct |
986 ms |
7664 KB |
Output is correct |
42 |
Correct |
996 ms |
7736 KB |
Output is correct |
43 |
Correct |
940 ms |
8588 KB |
Output is correct |
44 |
Correct |
47 ms |
4728 KB |
Output is correct |
45 |
Correct |
113 ms |
6768 KB |
Output is correct |
46 |
Correct |
75 ms |
6768 KB |
Output is correct |
47 |
Correct |
666 ms |
8696 KB |
Output is correct |
48 |
Correct |
967 ms |
8696 KB |
Output is correct |
49 |
Correct |
644 ms |
8568 KB |
Output is correct |
50 |
Correct |
523 ms |
7136 KB |
Output is correct |
51 |
Correct |
512 ms |
7160 KB |
Output is correct |
52 |
Correct |
522 ms |
7184 KB |
Output is correct |
53 |
Correct |
874 ms |
7916 KB |
Output is correct |
54 |
Correct |
871 ms |
7796 KB |
Output is correct |
55 |
Correct |
888 ms |
8056 KB |
Output is correct |
56 |
Correct |
636 ms |
8672 KB |
Output is correct |
57 |
Correct |
647 ms |
8692 KB |
Output is correct |
58 |
Correct |
1099 ms |
8696 KB |
Output is correct |
59 |
Correct |
1177 ms |
8700 KB |
Output is correct |
60 |
Correct |
1061 ms |
8840 KB |
Output is correct |
61 |
Correct |
1069 ms |
8564 KB |
Output is correct |
62 |
Correct |
1020 ms |
8268 KB |
Output is correct |
63 |
Correct |
1006 ms |
8360 KB |
Output is correct |
64 |
Correct |
1020 ms |
8732 KB |
Output is correct |
65 |
Correct |
831 ms |
8136 KB |
Output is correct |
66 |
Correct |
1871 ms |
8664 KB |
Output is correct |
67 |
Correct |
2041 ms |
8904 KB |
Output is correct |
68 |
Correct |
2058 ms |
8964 KB |
Output is correct |
69 |
Correct |
1903 ms |
8860 KB |
Output is correct |
70 |
Correct |
2238 ms |
8852 KB |
Output is correct |
71 |
Correct |
2249 ms |
8888 KB |
Output is correct |
72 |
Correct |
2185 ms |
8976 KB |
Output is correct |
73 |
Correct |
2103 ms |
8924 KB |
Output is correct |
74 |
Correct |
2101 ms |
8728 KB |
Output is correct |
75 |
Correct |
2081 ms |
8864 KB |
Output is correct |
76 |
Correct |
1998 ms |
8820 KB |
Output is correct |
77 |
Correct |
1950 ms |
8748 KB |
Output is correct |
78 |
Correct |
1962 ms |
8812 KB |
Output is correct |
79 |
Correct |
945 ms |
8260 KB |
Output is correct |
80 |
Correct |
928 ms |
8212 KB |
Output is correct |
81 |
Correct |
941 ms |
8208 KB |
Output is correct |
82 |
Correct |
1193 ms |
8884 KB |
Output is correct |
83 |
Correct |
1196 ms |
9052 KB |
Output is correct |
84 |
Correct |
1183 ms |
9084 KB |
Output is correct |
85 |
Correct |
2467 ms |
11292 KB |
Output is correct |
86 |
Correct |
224 ms |
8048 KB |
Output is correct |
87 |
Correct |
192 ms |
8144 KB |
Output is correct |
88 |
Correct |
1967 ms |
11300 KB |
Output is correct |
89 |
Correct |
2461 ms |
11116 KB |
Output is correct |
90 |
Correct |
1840 ms |
9924 KB |
Output is correct |
91 |
Correct |
2087 ms |
8988 KB |
Output is correct |
92 |
Correct |
2055 ms |
8980 KB |
Output is correct |
93 |
Correct |
1995 ms |
8092 KB |
Output is correct |
94 |
Correct |
2392 ms |
10676 KB |
Output is correct |
95 |
Correct |
2367 ms |
10500 KB |
Output is correct |
96 |
Correct |
1952 ms |
9068 KB |
Output is correct |
97 |
Correct |
1035 ms |
9676 KB |
Output is correct |
98 |
Correct |
1280 ms |
10144 KB |
Output is correct |
99 |
Correct |
2621 ms |
11260 KB |
Output is correct |
100 |
Correct |
2552 ms |
11144 KB |
Output is correct |
101 |
Correct |
2611 ms |
11280 KB |
Output is correct |
102 |
Correct |
2626 ms |
11052 KB |
Output is correct |
103 |
Correct |
2068 ms |
9116 KB |
Output is correct |
104 |
Correct |
2104 ms |
9300 KB |
Output is correct |
105 |
Correct |
1517 ms |
9596 KB |
Output is correct |
106 |
Correct |
1196 ms |
9780 KB |
Output is correct |
107 |
Correct |
1356 ms |
8940 KB |
Output is correct |
108 |
Correct |
2233 ms |
9324 KB |
Output is correct |
109 |
Correct |
2001 ms |
8844 KB |
Output is correct |