# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
444922 |
2021-07-15T21:05:10 Z |
JovanB |
Bridges (APIO19_bridges) |
C++17 |
|
2863 ms |
328556 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 50000;
const int M = 100000;
const int K = 700;
int ea[M+5];
int eb[M+5];
int ec[M+5];
bool changed[M+5];
int qt[M+5];
int qa[M+5];
int qb[M+5];
struct DSU{
int n;
int par[N+5];
int sz[N+5];
void init(int _n){
n = _n;
for(int i=1; i<=n; i++){
par[i] = i;
sz[i] = 1;
}
}
struct op{
int a, b, sza, szb;
};
stack <op> st;
int root(int x){ return (x == par[x] ? x : root(par[x])); }
void povezi(int a, int b){
a = root(a);
b = root(b);
st.push({a, b, sz[a], sz[b]});
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
par[b] = a;
}
void rollback(){
op o = st.top();
st.pop();
int a = o.a;
int b = o.b;
sz[a] = o.sza;
sz[b] = o.szb;
par[a] = a;
par[b] = b;
}
} dsu;
int sol[M+5];
const int INF = 1000000007;
vector <int> ima[M+5];
int gde[M+5];
set <pair <int, int>> unerased;
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m;
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> ea[i] >> eb[i] >> ec[i];
unerased.insert({ec[i], i});
}
int qrs;
cin >> qrs;
int qq = 0;
for(int ql=1; ql<=qrs; ql+=K){
int qr = min(qrs, ql+K-1);
dsu.init(n);
vector <pair <int, pair <int, int>>> dvec;
vector <int> ch;
for(int i=ql; i<=qr; i++){
cin >> qt[i] >> qa[i] >> qb[i];
if(qt[i] == 1){
if(!changed[qa[i]]){
ch.push_back(qa[i]);
unerased.erase({ec[qa[i]], qa[i]});
}
changed[qa[i]] = 1;
}
else{
qq++;
gde[i] = qq;
dvec.push_back({qb[i], {qq, qa[i]}});
}
}
sort(dvec.begin(), dvec.end());
vector <pair <int, pair <int, int>>> vec;
int j = 0;
for(auto c : unerased){
while(j < dvec.size() && c.first >= dvec[j].first){
vec.push_back(dvec[j]);
j++;
}
vec.push_back({c.first, {INF, c.second}});
}
while(j < dvec.size()){
vec.push_back(dvec[j]);
j++;
}
reverse(vec.begin(), vec.end());
for(int i=ql; i<=qr; i++){
if(qt[i] == 1) ec[qa[i]] = qb[i];
else{
for(auto c : ch){
if(ec[c] >= qb[i]) ima[gde[i]].push_back(c);
}
}
}
for(auto x : vec){
if(x.second.first == INF) dsu.povezi(ea[x.second.second], eb[x.second.second]);
else{
int ind = x.second.first;
int p = x.second.second;
for(auto c : ima[ind]) dsu.povezi(ea[c], eb[c]);
sol[ind] = dsu.sz[dsu.root(p)];
for(auto c : ima[ind]) dsu.rollback();
}
}
for(auto c : ch){
changed[c] = 0;
unerased.insert({ec[c], c});
}
for(int i=ql; i<=qr; i++) if(gde[i]) ima[gde[i]].clear();
}
for(int i=1; i<=qq; i++) cout << sol[i] << "\n";
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | while(j < dvec.size() && c.first >= dvec[j].first){
| ~~^~~~~~~~~~~~~
bridges.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | while(j < dvec.size()){
| ~~^~~~~~~~~~~~~
bridges.cpp:131:26: warning: unused variable 'c' [-Wunused-variable]
131 | for(auto c : ima[ind]) dsu.rollback();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
49 ms |
7152 KB |
Output is correct |
4 |
Correct |
6 ms |
2892 KB |
Output is correct |
5 |
Correct |
19 ms |
4388 KB |
Output is correct |
6 |
Correct |
17 ms |
4396 KB |
Output is correct |
7 |
Correct |
18 ms |
4432 KB |
Output is correct |
8 |
Correct |
20 ms |
4172 KB |
Output is correct |
9 |
Correct |
22 ms |
5452 KB |
Output is correct |
10 |
Correct |
19 ms |
4340 KB |
Output is correct |
11 |
Correct |
20 ms |
4296 KB |
Output is correct |
12 |
Correct |
25 ms |
4720 KB |
Output is correct |
13 |
Correct |
26 ms |
5012 KB |
Output is correct |
14 |
Correct |
24 ms |
4684 KB |
Output is correct |
15 |
Correct |
24 ms |
4472 KB |
Output is correct |
16 |
Correct |
20 ms |
4812 KB |
Output is correct |
17 |
Correct |
20 ms |
4784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1606 ms |
176656 KB |
Output is correct |
2 |
Correct |
1598 ms |
176328 KB |
Output is correct |
3 |
Correct |
1567 ms |
176576 KB |
Output is correct |
4 |
Correct |
1725 ms |
176372 KB |
Output is correct |
5 |
Correct |
1714 ms |
176680 KB |
Output is correct |
6 |
Correct |
2133 ms |
225964 KB |
Output is correct |
7 |
Correct |
2151 ms |
226324 KB |
Output is correct |
8 |
Correct |
2245 ms |
226084 KB |
Output is correct |
9 |
Correct |
44 ms |
4804 KB |
Output is correct |
10 |
Correct |
1377 ms |
200892 KB |
Output is correct |
11 |
Correct |
1297 ms |
185364 KB |
Output is correct |
12 |
Correct |
1301 ms |
167508 KB |
Output is correct |
13 |
Correct |
1284 ms |
164508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1082 ms |
134976 KB |
Output is correct |
2 |
Correct |
829 ms |
99584 KB |
Output is correct |
3 |
Correct |
1282 ms |
159716 KB |
Output is correct |
4 |
Correct |
1098 ms |
134504 KB |
Output is correct |
5 |
Correct |
44 ms |
4772 KB |
Output is correct |
6 |
Correct |
1271 ms |
150772 KB |
Output is correct |
7 |
Correct |
1018 ms |
127764 KB |
Output is correct |
8 |
Correct |
873 ms |
115548 KB |
Output is correct |
9 |
Correct |
715 ms |
108140 KB |
Output is correct |
10 |
Correct |
654 ms |
100572 KB |
Output is correct |
11 |
Correct |
778 ms |
106196 KB |
Output is correct |
12 |
Correct |
756 ms |
98696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1992 ms |
247004 KB |
Output is correct |
2 |
Correct |
45 ms |
4776 KB |
Output is correct |
3 |
Correct |
279 ms |
34692 KB |
Output is correct |
4 |
Correct |
154 ms |
34676 KB |
Output is correct |
5 |
Correct |
1433 ms |
246900 KB |
Output is correct |
6 |
Correct |
2020 ms |
246908 KB |
Output is correct |
7 |
Correct |
1554 ms |
247004 KB |
Output is correct |
8 |
Correct |
790 ms |
126008 KB |
Output is correct |
9 |
Correct |
765 ms |
125996 KB |
Output is correct |
10 |
Correct |
792 ms |
126180 KB |
Output is correct |
11 |
Correct |
1447 ms |
186720 KB |
Output is correct |
12 |
Correct |
1444 ms |
186936 KB |
Output is correct |
13 |
Correct |
1457 ms |
186872 KB |
Output is correct |
14 |
Correct |
1373 ms |
247052 KB |
Output is correct |
15 |
Correct |
1498 ms |
246900 KB |
Output is correct |
16 |
Correct |
2085 ms |
245776 KB |
Output is correct |
17 |
Correct |
2161 ms |
245672 KB |
Output is correct |
18 |
Correct |
2075 ms |
245496 KB |
Output is correct |
19 |
Correct |
2053 ms |
244960 KB |
Output is correct |
20 |
Correct |
1711 ms |
206912 KB |
Output is correct |
21 |
Correct |
1750 ms |
206916 KB |
Output is correct |
22 |
Correct |
1873 ms |
235160 KB |
Output is correct |
23 |
Correct |
1389 ms |
199276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1606 ms |
176656 KB |
Output is correct |
2 |
Correct |
1598 ms |
176328 KB |
Output is correct |
3 |
Correct |
1567 ms |
176576 KB |
Output is correct |
4 |
Correct |
1725 ms |
176372 KB |
Output is correct |
5 |
Correct |
1714 ms |
176680 KB |
Output is correct |
6 |
Correct |
2133 ms |
225964 KB |
Output is correct |
7 |
Correct |
2151 ms |
226324 KB |
Output is correct |
8 |
Correct |
2245 ms |
226084 KB |
Output is correct |
9 |
Correct |
44 ms |
4804 KB |
Output is correct |
10 |
Correct |
1377 ms |
200892 KB |
Output is correct |
11 |
Correct |
1297 ms |
185364 KB |
Output is correct |
12 |
Correct |
1301 ms |
167508 KB |
Output is correct |
13 |
Correct |
1284 ms |
164508 KB |
Output is correct |
14 |
Correct |
1082 ms |
134976 KB |
Output is correct |
15 |
Correct |
829 ms |
99584 KB |
Output is correct |
16 |
Correct |
1282 ms |
159716 KB |
Output is correct |
17 |
Correct |
1098 ms |
134504 KB |
Output is correct |
18 |
Correct |
44 ms |
4772 KB |
Output is correct |
19 |
Correct |
1271 ms |
150772 KB |
Output is correct |
20 |
Correct |
1018 ms |
127764 KB |
Output is correct |
21 |
Correct |
873 ms |
115548 KB |
Output is correct |
22 |
Correct |
715 ms |
108140 KB |
Output is correct |
23 |
Correct |
654 ms |
100572 KB |
Output is correct |
24 |
Correct |
778 ms |
106196 KB |
Output is correct |
25 |
Correct |
756 ms |
98696 KB |
Output is correct |
26 |
Correct |
1596 ms |
176260 KB |
Output is correct |
27 |
Correct |
1782 ms |
201840 KB |
Output is correct |
28 |
Correct |
1661 ms |
175204 KB |
Output is correct |
29 |
Correct |
1157 ms |
142116 KB |
Output is correct |
30 |
Correct |
1777 ms |
189880 KB |
Output is correct |
31 |
Correct |
1874 ms |
192156 KB |
Output is correct |
32 |
Correct |
1852 ms |
192672 KB |
Output is correct |
33 |
Correct |
1564 ms |
174600 KB |
Output is correct |
34 |
Correct |
1586 ms |
175256 KB |
Output is correct |
35 |
Correct |
1561 ms |
175184 KB |
Output is correct |
36 |
Correct |
1349 ms |
147128 KB |
Output is correct |
37 |
Correct |
1286 ms |
146012 KB |
Output is correct |
38 |
Correct |
1344 ms |
144776 KB |
Output is correct |
39 |
Correct |
990 ms |
134648 KB |
Output is correct |
40 |
Correct |
1058 ms |
134084 KB |
Output is correct |
41 |
Correct |
1074 ms |
133748 KB |
Output is correct |
42 |
Correct |
1120 ms |
132500 KB |
Output is correct |
43 |
Correct |
1067 ms |
132252 KB |
Output is correct |
44 |
Correct |
1177 ms |
131872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
49 ms |
7152 KB |
Output is correct |
4 |
Correct |
6 ms |
2892 KB |
Output is correct |
5 |
Correct |
19 ms |
4388 KB |
Output is correct |
6 |
Correct |
17 ms |
4396 KB |
Output is correct |
7 |
Correct |
18 ms |
4432 KB |
Output is correct |
8 |
Correct |
20 ms |
4172 KB |
Output is correct |
9 |
Correct |
22 ms |
5452 KB |
Output is correct |
10 |
Correct |
19 ms |
4340 KB |
Output is correct |
11 |
Correct |
20 ms |
4296 KB |
Output is correct |
12 |
Correct |
25 ms |
4720 KB |
Output is correct |
13 |
Correct |
26 ms |
5012 KB |
Output is correct |
14 |
Correct |
24 ms |
4684 KB |
Output is correct |
15 |
Correct |
24 ms |
4472 KB |
Output is correct |
16 |
Correct |
20 ms |
4812 KB |
Output is correct |
17 |
Correct |
20 ms |
4784 KB |
Output is correct |
18 |
Correct |
1606 ms |
176656 KB |
Output is correct |
19 |
Correct |
1598 ms |
176328 KB |
Output is correct |
20 |
Correct |
1567 ms |
176576 KB |
Output is correct |
21 |
Correct |
1725 ms |
176372 KB |
Output is correct |
22 |
Correct |
1714 ms |
176680 KB |
Output is correct |
23 |
Correct |
2133 ms |
225964 KB |
Output is correct |
24 |
Correct |
2151 ms |
226324 KB |
Output is correct |
25 |
Correct |
2245 ms |
226084 KB |
Output is correct |
26 |
Correct |
44 ms |
4804 KB |
Output is correct |
27 |
Correct |
1377 ms |
200892 KB |
Output is correct |
28 |
Correct |
1297 ms |
185364 KB |
Output is correct |
29 |
Correct |
1301 ms |
167508 KB |
Output is correct |
30 |
Correct |
1284 ms |
164508 KB |
Output is correct |
31 |
Correct |
1082 ms |
134976 KB |
Output is correct |
32 |
Correct |
829 ms |
99584 KB |
Output is correct |
33 |
Correct |
1282 ms |
159716 KB |
Output is correct |
34 |
Correct |
1098 ms |
134504 KB |
Output is correct |
35 |
Correct |
44 ms |
4772 KB |
Output is correct |
36 |
Correct |
1271 ms |
150772 KB |
Output is correct |
37 |
Correct |
1018 ms |
127764 KB |
Output is correct |
38 |
Correct |
873 ms |
115548 KB |
Output is correct |
39 |
Correct |
715 ms |
108140 KB |
Output is correct |
40 |
Correct |
654 ms |
100572 KB |
Output is correct |
41 |
Correct |
778 ms |
106196 KB |
Output is correct |
42 |
Correct |
756 ms |
98696 KB |
Output is correct |
43 |
Correct |
1992 ms |
247004 KB |
Output is correct |
44 |
Correct |
45 ms |
4776 KB |
Output is correct |
45 |
Correct |
279 ms |
34692 KB |
Output is correct |
46 |
Correct |
154 ms |
34676 KB |
Output is correct |
47 |
Correct |
1433 ms |
246900 KB |
Output is correct |
48 |
Correct |
2020 ms |
246908 KB |
Output is correct |
49 |
Correct |
1554 ms |
247004 KB |
Output is correct |
50 |
Correct |
790 ms |
126008 KB |
Output is correct |
51 |
Correct |
765 ms |
125996 KB |
Output is correct |
52 |
Correct |
792 ms |
126180 KB |
Output is correct |
53 |
Correct |
1447 ms |
186720 KB |
Output is correct |
54 |
Correct |
1444 ms |
186936 KB |
Output is correct |
55 |
Correct |
1457 ms |
186872 KB |
Output is correct |
56 |
Correct |
1373 ms |
247052 KB |
Output is correct |
57 |
Correct |
1498 ms |
246900 KB |
Output is correct |
58 |
Correct |
2085 ms |
245776 KB |
Output is correct |
59 |
Correct |
2161 ms |
245672 KB |
Output is correct |
60 |
Correct |
2075 ms |
245496 KB |
Output is correct |
61 |
Correct |
2053 ms |
244960 KB |
Output is correct |
62 |
Correct |
1711 ms |
206912 KB |
Output is correct |
63 |
Correct |
1750 ms |
206916 KB |
Output is correct |
64 |
Correct |
1873 ms |
235160 KB |
Output is correct |
65 |
Correct |
1389 ms |
199276 KB |
Output is correct |
66 |
Correct |
1596 ms |
176260 KB |
Output is correct |
67 |
Correct |
1782 ms |
201840 KB |
Output is correct |
68 |
Correct |
1661 ms |
175204 KB |
Output is correct |
69 |
Correct |
1157 ms |
142116 KB |
Output is correct |
70 |
Correct |
1777 ms |
189880 KB |
Output is correct |
71 |
Correct |
1874 ms |
192156 KB |
Output is correct |
72 |
Correct |
1852 ms |
192672 KB |
Output is correct |
73 |
Correct |
1564 ms |
174600 KB |
Output is correct |
74 |
Correct |
1586 ms |
175256 KB |
Output is correct |
75 |
Correct |
1561 ms |
175184 KB |
Output is correct |
76 |
Correct |
1349 ms |
147128 KB |
Output is correct |
77 |
Correct |
1286 ms |
146012 KB |
Output is correct |
78 |
Correct |
1344 ms |
144776 KB |
Output is correct |
79 |
Correct |
990 ms |
134648 KB |
Output is correct |
80 |
Correct |
1058 ms |
134084 KB |
Output is correct |
81 |
Correct |
1074 ms |
133748 KB |
Output is correct |
82 |
Correct |
1120 ms |
132500 KB |
Output is correct |
83 |
Correct |
1067 ms |
132252 KB |
Output is correct |
84 |
Correct |
1177 ms |
131872 KB |
Output is correct |
85 |
Correct |
2863 ms |
297588 KB |
Output is correct |
86 |
Correct |
309 ms |
41708 KB |
Output is correct |
87 |
Correct |
228 ms |
46232 KB |
Output is correct |
88 |
Correct |
2209 ms |
311792 KB |
Output is correct |
89 |
Correct |
2781 ms |
300288 KB |
Output is correct |
90 |
Correct |
2187 ms |
313308 KB |
Output is correct |
91 |
Correct |
1589 ms |
179088 KB |
Output is correct |
92 |
Correct |
1595 ms |
179128 KB |
Output is correct |
93 |
Correct |
2181 ms |
228928 KB |
Output is correct |
94 |
Correct |
2197 ms |
240264 KB |
Output is correct |
95 |
Correct |
2283 ms |
240436 KB |
Output is correct |
96 |
Correct |
2496 ms |
289308 KB |
Output is correct |
97 |
Correct |
1719 ms |
273580 KB |
Output is correct |
98 |
Correct |
1868 ms |
270036 KB |
Output is correct |
99 |
Correct |
2657 ms |
300724 KB |
Output is correct |
100 |
Correct |
2707 ms |
300056 KB |
Output is correct |
101 |
Correct |
2696 ms |
300564 KB |
Output is correct |
102 |
Correct |
2786 ms |
300060 KB |
Output is correct |
103 |
Correct |
2791 ms |
309688 KB |
Output is correct |
104 |
Correct |
2852 ms |
309632 KB |
Output is correct |
105 |
Correct |
2103 ms |
248256 KB |
Output is correct |
106 |
Correct |
1788 ms |
208068 KB |
Output is correct |
107 |
Correct |
2080 ms |
249520 KB |
Output is correct |
108 |
Correct |
2773 ms |
328556 KB |
Output is correct |
109 |
Correct |
2391 ms |
300604 KB |
Output is correct |