# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
713919 |
2023-03-23T08:40:57 Z |
ooo |
Bridges (APIO19_bridges) |
C++14 |
|
2379 ms |
10828 KB |
#include <bits/stdc++.h>
using namespace std;
const int nu = 1e5+5;
typedef pair<int, int> cap1;
typedef pair< pair<int, int>, pair<int, int> > cap2;
#define fi first
#define se second
int n, m, query, hang[nu], root[nu];
int type[nu], u[nu], v[nu], a[nu], b[nu];
int w[nu], ans[nu];
int c[nu*2], d[nu*2], e[nu*2], pos[nu*2], trc[nu*2], pp[nu*2];
bool dd[nu], kt[nu], check[nu*2];
stack<cap2> st;
vector<int> q;
vector<cap1> temp;
int findroot(int x)
{
if(x == root[x]) return x;
else return findroot(root[x]);
}
void dsu(int x, int y)
{
hang[y] += hang[x];
root[x] = y;
}
void rollback(int x, int y)
{
root[x] = st.top().fi.fi; root[y] = st.top().fi.se;
hang[x] = st.top().se.fi; hang[y] = st.top().se.se;
st.pop();
}
bool ss(int x, int y)
{
return (e[x] > e[y]);
}
bool ss2(int x, int y)
{
return (b[x] > b[y]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
int len = 0;
for(int i = 1; i <= m; ++i) cin >> u[i] >> v[i] >> w[i], c[++len] = i, d[len] = i, e[len] = w[i], pos[i] = i, check[i] = true;
cin >> query;
for(int i = 1; i <= query; ++i) cin >> type[i] >> a[i] >> b[i];
int p = m;
for(int i = 1; i <= query; ++i)
if(type[i] == 1)
{
c[++len] = ++m, d[m] = a[i], e[m] = b[i];
trc[m] = pos[a[i]];
pos[a[i]] = m;
pp[i] = m;
}
sort(c+1, c+1+len, ss);
int can = sqrt(query);
int x = query/can;
if(query%can > 0) x++;
for(int i = 1; i <= can; ++i)
{
int l = (i-1)*x+1;
int r = min(i*x, query);
for(int j = l; j <= r; ++j)
if(type[j] == 2) q.push_back(j);
else kt[a[j]] = true;
sort(q.begin(), q.end(), ss2);
for(int j = 1; j <= n; ++j) root[j] = j, hang[j] = 1;
int j = 0; int k = 1;
while(j < int(q.size()))
{
while(k <= len && e[c[k]] >= b[q[j]])
{
if(check[c[k]] && !kt[d[c[k]]])
{
int x = findroot(u[d[c[k]]]);
int y = findroot(v[d[c[k]]]);
if(hang[x] > hang[y]) swap(x, y);
if(x != y) dsu(x, y);
}
k++;
}
for(int h = q[j]; h >= l; --h)
if(!dd[a[h]] && type[h] == 1)
{
if(b[h] >= b[q[j]])
{
int x = findroot(u[a[h]]);
int y = findroot(v[a[h]]);
if(x != y)
{
if(hang[x] > hang[y]) swap(x, y);
st.push({{root[x], root[y]}, {hang[x], hang[y]}});
temp.push_back({x, y});
dsu(x, y);
}
}
dd[a[h]] = true;
}
for(int h = q[j]+1; h <= r; ++h)
if(type[h] == 1 && w[a[h]] >= b[q[j]] && !dd[a[h]])
{
int x = findroot(u[a[h]]);
int y = findroot(v[a[h]]);
if(x != y)
{
if(hang[x] > hang[y]) swap(x, y);
st.push({{root[x], root[y]}, {hang[x], hang[y]}});
temp.push_back({x, y});
dsu(x, y);
}
}
for(int h = l; h <= q[j]; ++h) if(type[h] == 1) dd[a[h]] = false;
ans[q[j]] = hang[findroot(a[q[j]])];
while(!temp.empty()) rollback(temp.back().fi, temp.back().se), temp.pop_back();
j++;
}
for(int j = l; j <= r; ++j) if(type[j] == 1)
{
check[trc[pp[j]]] = false;
check[pp[j]] = true;
kt[a[j]] = false;
w[a[j]] = b[j];
}
q.clear();
}
for(int i = 1; i <= query; ++i)
if(ans[i] > 0) cout << ans[i] << '\n';
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:51:9: warning: unused variable 'p' [-Wunused-variable]
51 | int p = m;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
13 ms |
680 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
12 ms |
596 KB |
Output is correct |
6 |
Correct |
9 ms |
596 KB |
Output is correct |
7 |
Correct |
10 ms |
596 KB |
Output is correct |
8 |
Correct |
11 ms |
668 KB |
Output is correct |
9 |
Correct |
12 ms |
596 KB |
Output is correct |
10 |
Correct |
12 ms |
684 KB |
Output is correct |
11 |
Correct |
11 ms |
620 KB |
Output is correct |
12 |
Correct |
12 ms |
668 KB |
Output is correct |
13 |
Correct |
12 ms |
608 KB |
Output is correct |
14 |
Correct |
11 ms |
676 KB |
Output is correct |
15 |
Correct |
11 ms |
640 KB |
Output is correct |
16 |
Correct |
11 ms |
648 KB |
Output is correct |
17 |
Correct |
11 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1349 ms |
5236 KB |
Output is correct |
2 |
Correct |
1289 ms |
5220 KB |
Output is correct |
3 |
Correct |
1296 ms |
5300 KB |
Output is correct |
4 |
Correct |
1295 ms |
5156 KB |
Output is correct |
5 |
Correct |
1295 ms |
5068 KB |
Output is correct |
6 |
Correct |
1447 ms |
5248 KB |
Output is correct |
7 |
Correct |
1475 ms |
5380 KB |
Output is correct |
8 |
Correct |
1486 ms |
5308 KB |
Output is correct |
9 |
Correct |
67 ms |
1996 KB |
Output is correct |
10 |
Correct |
881 ms |
5176 KB |
Output is correct |
11 |
Correct |
877 ms |
5324 KB |
Output is correct |
12 |
Correct |
970 ms |
4820 KB |
Output is correct |
13 |
Correct |
1227 ms |
5888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1002 ms |
4636 KB |
Output is correct |
2 |
Correct |
446 ms |
3668 KB |
Output is correct |
3 |
Correct |
995 ms |
4592 KB |
Output is correct |
4 |
Correct |
951 ms |
4520 KB |
Output is correct |
5 |
Correct |
64 ms |
2072 KB |
Output is correct |
6 |
Correct |
1022 ms |
4616 KB |
Output is correct |
7 |
Correct |
897 ms |
4596 KB |
Output is correct |
8 |
Correct |
865 ms |
4596 KB |
Output is correct |
9 |
Correct |
677 ms |
3988 KB |
Output is correct |
10 |
Correct |
665 ms |
3940 KB |
Output is correct |
11 |
Correct |
846 ms |
5116 KB |
Output is correct |
12 |
Correct |
789 ms |
5208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1698 ms |
5652 KB |
Output is correct |
2 |
Correct |
64 ms |
2032 KB |
Output is correct |
3 |
Correct |
335 ms |
3332 KB |
Output is correct |
4 |
Correct |
251 ms |
3404 KB |
Output is correct |
5 |
Correct |
1233 ms |
5920 KB |
Output is correct |
6 |
Correct |
1587 ms |
5752 KB |
Output is correct |
7 |
Correct |
1252 ms |
5624 KB |
Output is correct |
8 |
Correct |
905 ms |
3912 KB |
Output is correct |
9 |
Correct |
883 ms |
3876 KB |
Output is correct |
10 |
Correct |
903 ms |
4044 KB |
Output is correct |
11 |
Correct |
1303 ms |
4864 KB |
Output is correct |
12 |
Correct |
1292 ms |
4684 KB |
Output is correct |
13 |
Correct |
1291 ms |
4836 KB |
Output is correct |
14 |
Correct |
1182 ms |
5704 KB |
Output is correct |
15 |
Correct |
1184 ms |
5712 KB |
Output is correct |
16 |
Correct |
1718 ms |
5588 KB |
Output is correct |
17 |
Correct |
2024 ms |
5544 KB |
Output is correct |
18 |
Correct |
1730 ms |
5684 KB |
Output is correct |
19 |
Correct |
1699 ms |
5572 KB |
Output is correct |
20 |
Correct |
1488 ms |
5468 KB |
Output is correct |
21 |
Correct |
1468 ms |
5328 KB |
Output is correct |
22 |
Correct |
1652 ms |
5608 KB |
Output is correct |
23 |
Correct |
1341 ms |
5160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1349 ms |
5236 KB |
Output is correct |
2 |
Correct |
1289 ms |
5220 KB |
Output is correct |
3 |
Correct |
1296 ms |
5300 KB |
Output is correct |
4 |
Correct |
1295 ms |
5156 KB |
Output is correct |
5 |
Correct |
1295 ms |
5068 KB |
Output is correct |
6 |
Correct |
1447 ms |
5248 KB |
Output is correct |
7 |
Correct |
1475 ms |
5380 KB |
Output is correct |
8 |
Correct |
1486 ms |
5308 KB |
Output is correct |
9 |
Correct |
67 ms |
1996 KB |
Output is correct |
10 |
Correct |
881 ms |
5176 KB |
Output is correct |
11 |
Correct |
877 ms |
5324 KB |
Output is correct |
12 |
Correct |
970 ms |
4820 KB |
Output is correct |
13 |
Correct |
1227 ms |
5888 KB |
Output is correct |
14 |
Correct |
1002 ms |
4636 KB |
Output is correct |
15 |
Correct |
446 ms |
3668 KB |
Output is correct |
16 |
Correct |
995 ms |
4592 KB |
Output is correct |
17 |
Correct |
951 ms |
4520 KB |
Output is correct |
18 |
Correct |
64 ms |
2072 KB |
Output is correct |
19 |
Correct |
1022 ms |
4616 KB |
Output is correct |
20 |
Correct |
897 ms |
4596 KB |
Output is correct |
21 |
Correct |
865 ms |
4596 KB |
Output is correct |
22 |
Correct |
677 ms |
3988 KB |
Output is correct |
23 |
Correct |
665 ms |
3940 KB |
Output is correct |
24 |
Correct |
846 ms |
5116 KB |
Output is correct |
25 |
Correct |
789 ms |
5208 KB |
Output is correct |
26 |
Correct |
1478 ms |
5156 KB |
Output is correct |
27 |
Correct |
1525 ms |
5412 KB |
Output is correct |
28 |
Correct |
1463 ms |
5488 KB |
Output is correct |
29 |
Correct |
1303 ms |
5244 KB |
Output is correct |
30 |
Correct |
1509 ms |
5360 KB |
Output is correct |
31 |
Correct |
1545 ms |
5284 KB |
Output is correct |
32 |
Correct |
1550 ms |
5228 KB |
Output is correct |
33 |
Correct |
1428 ms |
5440 KB |
Output is correct |
34 |
Correct |
1428 ms |
5264 KB |
Output is correct |
35 |
Correct |
1443 ms |
5416 KB |
Output is correct |
36 |
Correct |
1297 ms |
5132 KB |
Output is correct |
37 |
Correct |
1282 ms |
5108 KB |
Output is correct |
38 |
Correct |
1277 ms |
5156 KB |
Output is correct |
39 |
Correct |
1046 ms |
4516 KB |
Output is correct |
40 |
Correct |
1055 ms |
4652 KB |
Output is correct |
41 |
Correct |
1056 ms |
4508 KB |
Output is correct |
42 |
Correct |
1104 ms |
5980 KB |
Output is correct |
43 |
Correct |
1119 ms |
5816 KB |
Output is correct |
44 |
Correct |
1085 ms |
5744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
13 ms |
680 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
12 ms |
596 KB |
Output is correct |
6 |
Correct |
9 ms |
596 KB |
Output is correct |
7 |
Correct |
10 ms |
596 KB |
Output is correct |
8 |
Correct |
11 ms |
668 KB |
Output is correct |
9 |
Correct |
12 ms |
596 KB |
Output is correct |
10 |
Correct |
12 ms |
684 KB |
Output is correct |
11 |
Correct |
11 ms |
620 KB |
Output is correct |
12 |
Correct |
12 ms |
668 KB |
Output is correct |
13 |
Correct |
12 ms |
608 KB |
Output is correct |
14 |
Correct |
11 ms |
676 KB |
Output is correct |
15 |
Correct |
11 ms |
640 KB |
Output is correct |
16 |
Correct |
11 ms |
648 KB |
Output is correct |
17 |
Correct |
11 ms |
596 KB |
Output is correct |
18 |
Correct |
1349 ms |
5236 KB |
Output is correct |
19 |
Correct |
1289 ms |
5220 KB |
Output is correct |
20 |
Correct |
1296 ms |
5300 KB |
Output is correct |
21 |
Correct |
1295 ms |
5156 KB |
Output is correct |
22 |
Correct |
1295 ms |
5068 KB |
Output is correct |
23 |
Correct |
1447 ms |
5248 KB |
Output is correct |
24 |
Correct |
1475 ms |
5380 KB |
Output is correct |
25 |
Correct |
1486 ms |
5308 KB |
Output is correct |
26 |
Correct |
67 ms |
1996 KB |
Output is correct |
27 |
Correct |
881 ms |
5176 KB |
Output is correct |
28 |
Correct |
877 ms |
5324 KB |
Output is correct |
29 |
Correct |
970 ms |
4820 KB |
Output is correct |
30 |
Correct |
1227 ms |
5888 KB |
Output is correct |
31 |
Correct |
1002 ms |
4636 KB |
Output is correct |
32 |
Correct |
446 ms |
3668 KB |
Output is correct |
33 |
Correct |
995 ms |
4592 KB |
Output is correct |
34 |
Correct |
951 ms |
4520 KB |
Output is correct |
35 |
Correct |
64 ms |
2072 KB |
Output is correct |
36 |
Correct |
1022 ms |
4616 KB |
Output is correct |
37 |
Correct |
897 ms |
4596 KB |
Output is correct |
38 |
Correct |
865 ms |
4596 KB |
Output is correct |
39 |
Correct |
677 ms |
3988 KB |
Output is correct |
40 |
Correct |
665 ms |
3940 KB |
Output is correct |
41 |
Correct |
846 ms |
5116 KB |
Output is correct |
42 |
Correct |
789 ms |
5208 KB |
Output is correct |
43 |
Correct |
1698 ms |
5652 KB |
Output is correct |
44 |
Correct |
64 ms |
2032 KB |
Output is correct |
45 |
Correct |
335 ms |
3332 KB |
Output is correct |
46 |
Correct |
251 ms |
3404 KB |
Output is correct |
47 |
Correct |
1233 ms |
5920 KB |
Output is correct |
48 |
Correct |
1587 ms |
5752 KB |
Output is correct |
49 |
Correct |
1252 ms |
5624 KB |
Output is correct |
50 |
Correct |
905 ms |
3912 KB |
Output is correct |
51 |
Correct |
883 ms |
3876 KB |
Output is correct |
52 |
Correct |
903 ms |
4044 KB |
Output is correct |
53 |
Correct |
1303 ms |
4864 KB |
Output is correct |
54 |
Correct |
1292 ms |
4684 KB |
Output is correct |
55 |
Correct |
1291 ms |
4836 KB |
Output is correct |
56 |
Correct |
1182 ms |
5704 KB |
Output is correct |
57 |
Correct |
1184 ms |
5712 KB |
Output is correct |
58 |
Correct |
1718 ms |
5588 KB |
Output is correct |
59 |
Correct |
2024 ms |
5544 KB |
Output is correct |
60 |
Correct |
1730 ms |
5684 KB |
Output is correct |
61 |
Correct |
1699 ms |
5572 KB |
Output is correct |
62 |
Correct |
1488 ms |
5468 KB |
Output is correct |
63 |
Correct |
1468 ms |
5328 KB |
Output is correct |
64 |
Correct |
1652 ms |
5608 KB |
Output is correct |
65 |
Correct |
1341 ms |
5160 KB |
Output is correct |
66 |
Correct |
1478 ms |
5156 KB |
Output is correct |
67 |
Correct |
1525 ms |
5412 KB |
Output is correct |
68 |
Correct |
1463 ms |
5488 KB |
Output is correct |
69 |
Correct |
1303 ms |
5244 KB |
Output is correct |
70 |
Correct |
1509 ms |
5360 KB |
Output is correct |
71 |
Correct |
1545 ms |
5284 KB |
Output is correct |
72 |
Correct |
1550 ms |
5228 KB |
Output is correct |
73 |
Correct |
1428 ms |
5440 KB |
Output is correct |
74 |
Correct |
1428 ms |
5264 KB |
Output is correct |
75 |
Correct |
1443 ms |
5416 KB |
Output is correct |
76 |
Correct |
1297 ms |
5132 KB |
Output is correct |
77 |
Correct |
1282 ms |
5108 KB |
Output is correct |
78 |
Correct |
1277 ms |
5156 KB |
Output is correct |
79 |
Correct |
1046 ms |
4516 KB |
Output is correct |
80 |
Correct |
1055 ms |
4652 KB |
Output is correct |
81 |
Correct |
1056 ms |
4508 KB |
Output is correct |
82 |
Correct |
1104 ms |
5980 KB |
Output is correct |
83 |
Correct |
1119 ms |
5816 KB |
Output is correct |
84 |
Correct |
1085 ms |
5744 KB |
Output is correct |
85 |
Correct |
2219 ms |
10828 KB |
Output is correct |
86 |
Correct |
353 ms |
5436 KB |
Output is correct |
87 |
Correct |
290 ms |
5676 KB |
Output is correct |
88 |
Correct |
1714 ms |
9336 KB |
Output is correct |
89 |
Correct |
2306 ms |
10768 KB |
Output is correct |
90 |
Correct |
1730 ms |
8948 KB |
Output is correct |
91 |
Correct |
1459 ms |
7852 KB |
Output is correct |
92 |
Correct |
1447 ms |
8108 KB |
Output is correct |
93 |
Correct |
1644 ms |
8088 KB |
Output is correct |
94 |
Correct |
1914 ms |
9124 KB |
Output is correct |
95 |
Correct |
1905 ms |
9356 KB |
Output is correct |
96 |
Correct |
1889 ms |
9232 KB |
Output is correct |
97 |
Correct |
1452 ms |
8604 KB |
Output is correct |
98 |
Correct |
1698 ms |
9468 KB |
Output is correct |
99 |
Correct |
2296 ms |
10396 KB |
Output is correct |
100 |
Correct |
2278 ms |
10496 KB |
Output is correct |
101 |
Correct |
2363 ms |
10588 KB |
Output is correct |
102 |
Correct |
2379 ms |
10680 KB |
Output is correct |
103 |
Correct |
2041 ms |
9484 KB |
Output is correct |
104 |
Correct |
2031 ms |
9644 KB |
Output is correct |
105 |
Correct |
2139 ms |
10084 KB |
Output is correct |
106 |
Correct |
1878 ms |
9768 KB |
Output is correct |
107 |
Correct |
1667 ms |
9204 KB |
Output is correct |
108 |
Correct |
2253 ms |
10328 KB |
Output is correct |
109 |
Correct |
1880 ms |
8256 KB |
Output is correct |