# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
784251 |
2023-07-15T22:21:51 Z |
Seb |
Bridges (APIO19_bridges) |
C++17 |
|
2574 ms |
14036 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
const ll MAXN = 1e5 + 5;
const ll sq = 1000;
ll u[MAXN],v[MAXN],d[MAXN],t[MAXN],s[MAXN],w[MAXN],pa[MAXN],ans[MAXN],sz[MAXN],sus[MAXN];
priority_queue <pair<ll,ll>> pq,pq2;
vector <ll> roll,vec;
bool vis[MAXN];
ll padre(ll a) {
if (sz[a] == 0) {
sz[a] = 1;
pa[a] = a;
}
if (pa[a] == a) return a;
return padre(pa[a]);
}
void unir(ll a, ll b) {
a = padre(a);
b = padre(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a,b);
sz[a] += sz[b];
pa[b] = a;
roll.push_back(b);
return;
}
void rollback(ll pausa) {
while (roll.size() != pausa) {
ll aux = roll.back();
roll.pop_back();
sz[pa[aux]] -= sz[aux];
pa[aux] = aux;
}
return;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
roll.push_back(0);
ll n,m,q;
cin>>n>>m;
for (int i=0;i<m;i++) cin>>u[i]>>v[i]>>d[i];
cin>>q;
for (int i=0;i<q;i++) cin>>t[i]>>s[i]>>w[i];
for (int l=0;l<q;l+=sq) {
int r = min(l+sq-1,q-1);
for (int i=l;i<=r;i++) {
if (t[i]==2) pq2.push({w[i],i});
else {
vis[s[i]-1] = true;
vec.push_back(s[i]-1);
}
}
for (int i=0;i<m;i++) if (vis[i] == false) pq.push({d[i],i});
while (!pq2.empty()) {
pair<ll,ll> p = pq2.top();
pq2.pop();
while (!pq.empty() && pq.top().f >= p.f) {
unir(u[pq.top().s],v[pq.top().s]);
pq.pop();
}
int pau = roll.size();
for (int i=l;i<=p.s;i++) if (t[i]==1) {
sus[s[i]-1] = w[i];
}
for (int i=0;i<vec.size();i++) {
if (sus[vec[i]]==0) {
if (d[vec[i]] >= p.f) unir(u[vec[i]],v[vec[i]]);
}
else {
if (sus[vec[i]] >= p.f) unir(u[vec[i]],v[vec[i]]);
}
}
for (int i=l;i<=p.s;i++) if (t[i]==1) sus[s[i]-1] = 0;
ans[p.s] = sz[padre(s[p.s])];
rollback(pau);
}
for (int i=l;i<=r;i++) if (t[i]==1) d[s[i]-1] = w[i];
while (!pq.empty()) pq.pop();
while (!pq2.empty()) pq2.pop();
rollback(1);
for (int i=0;i<m;i++) {
vis[i] = false;
sus[i] = 0;
}
vec.clear();
}
for (int i=0;i<q;i++) if (ans[i]!=0) cout<<ans[i]<<"\n";
return 0;
}
Compilation message
bridges.cpp: In function 'void rollback(ll)':
bridges.cpp:42:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
42 | while (roll.size() != pausa) {
| ~~~~~~~~~~~~^~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i=0;i<vec.size();i++) {
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
376 KB |
Output is correct |
3 |
Correct |
33 ms |
748 KB |
Output is correct |
4 |
Correct |
11 ms |
696 KB |
Output is correct |
5 |
Correct |
37 ms |
696 KB |
Output is correct |
6 |
Correct |
30 ms |
688 KB |
Output is correct |
7 |
Correct |
34 ms |
924 KB |
Output is correct |
8 |
Correct |
37 ms |
676 KB |
Output is correct |
9 |
Correct |
43 ms |
696 KB |
Output is correct |
10 |
Correct |
37 ms |
664 KB |
Output is correct |
11 |
Correct |
37 ms |
712 KB |
Output is correct |
12 |
Correct |
52 ms |
668 KB |
Output is correct |
13 |
Correct |
42 ms |
700 KB |
Output is correct |
14 |
Correct |
40 ms |
680 KB |
Output is correct |
15 |
Correct |
46 ms |
692 KB |
Output is correct |
16 |
Correct |
34 ms |
716 KB |
Output is correct |
17 |
Correct |
34 ms |
700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1182 ms |
7740 KB |
Output is correct |
2 |
Correct |
1242 ms |
7620 KB |
Output is correct |
3 |
Correct |
1234 ms |
7640 KB |
Output is correct |
4 |
Correct |
1279 ms |
7624 KB |
Output is correct |
5 |
Correct |
1305 ms |
7684 KB |
Output is correct |
6 |
Correct |
1536 ms |
7764 KB |
Output is correct |
7 |
Correct |
1505 ms |
7832 KB |
Output is correct |
8 |
Correct |
1541 ms |
7812 KB |
Output is correct |
9 |
Correct |
113 ms |
3608 KB |
Output is correct |
10 |
Correct |
986 ms |
7724 KB |
Output is correct |
11 |
Correct |
981 ms |
7636 KB |
Output is correct |
12 |
Correct |
1116 ms |
8084 KB |
Output is correct |
13 |
Correct |
1060 ms |
7532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
864 ms |
6152 KB |
Output is correct |
2 |
Correct |
482 ms |
4296 KB |
Output is correct |
3 |
Correct |
975 ms |
6420 KB |
Output is correct |
4 |
Correct |
848 ms |
6164 KB |
Output is correct |
5 |
Correct |
107 ms |
3632 KB |
Output is correct |
6 |
Correct |
956 ms |
6244 KB |
Output is correct |
7 |
Correct |
820 ms |
6168 KB |
Output is correct |
8 |
Correct |
795 ms |
6172 KB |
Output is correct |
9 |
Correct |
729 ms |
6424 KB |
Output is correct |
10 |
Correct |
666 ms |
6324 KB |
Output is correct |
11 |
Correct |
652 ms |
6136 KB |
Output is correct |
12 |
Correct |
629 ms |
6084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1944 ms |
10368 KB |
Output is correct |
2 |
Correct |
109 ms |
4788 KB |
Output is correct |
3 |
Correct |
189 ms |
6768 KB |
Output is correct |
4 |
Correct |
140 ms |
6732 KB |
Output is correct |
5 |
Correct |
1654 ms |
11540 KB |
Output is correct |
6 |
Correct |
1971 ms |
11480 KB |
Output is correct |
7 |
Correct |
1682 ms |
11608 KB |
Output is correct |
8 |
Correct |
910 ms |
8976 KB |
Output is correct |
9 |
Correct |
922 ms |
8960 KB |
Output is correct |
10 |
Correct |
930 ms |
9072 KB |
Output is correct |
11 |
Correct |
1465 ms |
10172 KB |
Output is correct |
12 |
Correct |
1409 ms |
10172 KB |
Output is correct |
13 |
Correct |
1418 ms |
10324 KB |
Output is correct |
14 |
Correct |
1624 ms |
11724 KB |
Output is correct |
15 |
Correct |
1629 ms |
11508 KB |
Output is correct |
16 |
Correct |
1970 ms |
11484 KB |
Output is correct |
17 |
Correct |
1986 ms |
11468 KB |
Output is correct |
18 |
Correct |
1927 ms |
11404 KB |
Output is correct |
19 |
Correct |
1942 ms |
11484 KB |
Output is correct |
20 |
Correct |
1634 ms |
10824 KB |
Output is correct |
21 |
Correct |
1617 ms |
10860 KB |
Output is correct |
22 |
Correct |
1893 ms |
11356 KB |
Output is correct |
23 |
Correct |
1625 ms |
10540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1182 ms |
7740 KB |
Output is correct |
2 |
Correct |
1242 ms |
7620 KB |
Output is correct |
3 |
Correct |
1234 ms |
7640 KB |
Output is correct |
4 |
Correct |
1279 ms |
7624 KB |
Output is correct |
5 |
Correct |
1305 ms |
7684 KB |
Output is correct |
6 |
Correct |
1536 ms |
7764 KB |
Output is correct |
7 |
Correct |
1505 ms |
7832 KB |
Output is correct |
8 |
Correct |
1541 ms |
7812 KB |
Output is correct |
9 |
Correct |
113 ms |
3608 KB |
Output is correct |
10 |
Correct |
986 ms |
7724 KB |
Output is correct |
11 |
Correct |
981 ms |
7636 KB |
Output is correct |
12 |
Correct |
1116 ms |
8084 KB |
Output is correct |
13 |
Correct |
1060 ms |
7532 KB |
Output is correct |
14 |
Correct |
864 ms |
6152 KB |
Output is correct |
15 |
Correct |
482 ms |
4296 KB |
Output is correct |
16 |
Correct |
975 ms |
6420 KB |
Output is correct |
17 |
Correct |
848 ms |
6164 KB |
Output is correct |
18 |
Correct |
107 ms |
3632 KB |
Output is correct |
19 |
Correct |
956 ms |
6244 KB |
Output is correct |
20 |
Correct |
820 ms |
6168 KB |
Output is correct |
21 |
Correct |
795 ms |
6172 KB |
Output is correct |
22 |
Correct |
729 ms |
6424 KB |
Output is correct |
23 |
Correct |
666 ms |
6324 KB |
Output is correct |
24 |
Correct |
652 ms |
6136 KB |
Output is correct |
25 |
Correct |
629 ms |
6084 KB |
Output is correct |
26 |
Correct |
1206 ms |
7772 KB |
Output is correct |
27 |
Correct |
1410 ms |
7748 KB |
Output is correct |
28 |
Correct |
1320 ms |
7700 KB |
Output is correct |
29 |
Correct |
1101 ms |
7616 KB |
Output is correct |
30 |
Correct |
1460 ms |
7920 KB |
Output is correct |
31 |
Correct |
1440 ms |
7720 KB |
Output is correct |
32 |
Correct |
1538 ms |
7856 KB |
Output is correct |
33 |
Correct |
1277 ms |
7632 KB |
Output is correct |
34 |
Correct |
1321 ms |
7688 KB |
Output is correct |
35 |
Correct |
1289 ms |
7628 KB |
Output is correct |
36 |
Correct |
1150 ms |
7604 KB |
Output is correct |
37 |
Correct |
1147 ms |
7592 KB |
Output is correct |
38 |
Correct |
1116 ms |
7636 KB |
Output is correct |
39 |
Correct |
985 ms |
7728 KB |
Output is correct |
40 |
Correct |
980 ms |
7728 KB |
Output is correct |
41 |
Correct |
997 ms |
7760 KB |
Output is correct |
42 |
Correct |
920 ms |
7612 KB |
Output is correct |
43 |
Correct |
902 ms |
7552 KB |
Output is correct |
44 |
Correct |
887 ms |
7504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
376 KB |
Output is correct |
3 |
Correct |
33 ms |
748 KB |
Output is correct |
4 |
Correct |
11 ms |
696 KB |
Output is correct |
5 |
Correct |
37 ms |
696 KB |
Output is correct |
6 |
Correct |
30 ms |
688 KB |
Output is correct |
7 |
Correct |
34 ms |
924 KB |
Output is correct |
8 |
Correct |
37 ms |
676 KB |
Output is correct |
9 |
Correct |
43 ms |
696 KB |
Output is correct |
10 |
Correct |
37 ms |
664 KB |
Output is correct |
11 |
Correct |
37 ms |
712 KB |
Output is correct |
12 |
Correct |
52 ms |
668 KB |
Output is correct |
13 |
Correct |
42 ms |
700 KB |
Output is correct |
14 |
Correct |
40 ms |
680 KB |
Output is correct |
15 |
Correct |
46 ms |
692 KB |
Output is correct |
16 |
Correct |
34 ms |
716 KB |
Output is correct |
17 |
Correct |
34 ms |
700 KB |
Output is correct |
18 |
Correct |
1182 ms |
7740 KB |
Output is correct |
19 |
Correct |
1242 ms |
7620 KB |
Output is correct |
20 |
Correct |
1234 ms |
7640 KB |
Output is correct |
21 |
Correct |
1279 ms |
7624 KB |
Output is correct |
22 |
Correct |
1305 ms |
7684 KB |
Output is correct |
23 |
Correct |
1536 ms |
7764 KB |
Output is correct |
24 |
Correct |
1505 ms |
7832 KB |
Output is correct |
25 |
Correct |
1541 ms |
7812 KB |
Output is correct |
26 |
Correct |
113 ms |
3608 KB |
Output is correct |
27 |
Correct |
986 ms |
7724 KB |
Output is correct |
28 |
Correct |
981 ms |
7636 KB |
Output is correct |
29 |
Correct |
1116 ms |
8084 KB |
Output is correct |
30 |
Correct |
1060 ms |
7532 KB |
Output is correct |
31 |
Correct |
864 ms |
6152 KB |
Output is correct |
32 |
Correct |
482 ms |
4296 KB |
Output is correct |
33 |
Correct |
975 ms |
6420 KB |
Output is correct |
34 |
Correct |
848 ms |
6164 KB |
Output is correct |
35 |
Correct |
107 ms |
3632 KB |
Output is correct |
36 |
Correct |
956 ms |
6244 KB |
Output is correct |
37 |
Correct |
820 ms |
6168 KB |
Output is correct |
38 |
Correct |
795 ms |
6172 KB |
Output is correct |
39 |
Correct |
729 ms |
6424 KB |
Output is correct |
40 |
Correct |
666 ms |
6324 KB |
Output is correct |
41 |
Correct |
652 ms |
6136 KB |
Output is correct |
42 |
Correct |
629 ms |
6084 KB |
Output is correct |
43 |
Correct |
1944 ms |
10368 KB |
Output is correct |
44 |
Correct |
109 ms |
4788 KB |
Output is correct |
45 |
Correct |
189 ms |
6768 KB |
Output is correct |
46 |
Correct |
140 ms |
6732 KB |
Output is correct |
47 |
Correct |
1654 ms |
11540 KB |
Output is correct |
48 |
Correct |
1971 ms |
11480 KB |
Output is correct |
49 |
Correct |
1682 ms |
11608 KB |
Output is correct |
50 |
Correct |
910 ms |
8976 KB |
Output is correct |
51 |
Correct |
922 ms |
8960 KB |
Output is correct |
52 |
Correct |
930 ms |
9072 KB |
Output is correct |
53 |
Correct |
1465 ms |
10172 KB |
Output is correct |
54 |
Correct |
1409 ms |
10172 KB |
Output is correct |
55 |
Correct |
1418 ms |
10324 KB |
Output is correct |
56 |
Correct |
1624 ms |
11724 KB |
Output is correct |
57 |
Correct |
1629 ms |
11508 KB |
Output is correct |
58 |
Correct |
1970 ms |
11484 KB |
Output is correct |
59 |
Correct |
1986 ms |
11468 KB |
Output is correct |
60 |
Correct |
1927 ms |
11404 KB |
Output is correct |
61 |
Correct |
1942 ms |
11484 KB |
Output is correct |
62 |
Correct |
1634 ms |
10824 KB |
Output is correct |
63 |
Correct |
1617 ms |
10860 KB |
Output is correct |
64 |
Correct |
1893 ms |
11356 KB |
Output is correct |
65 |
Correct |
1625 ms |
10540 KB |
Output is correct |
66 |
Correct |
1206 ms |
7772 KB |
Output is correct |
67 |
Correct |
1410 ms |
7748 KB |
Output is correct |
68 |
Correct |
1320 ms |
7700 KB |
Output is correct |
69 |
Correct |
1101 ms |
7616 KB |
Output is correct |
70 |
Correct |
1460 ms |
7920 KB |
Output is correct |
71 |
Correct |
1440 ms |
7720 KB |
Output is correct |
72 |
Correct |
1538 ms |
7856 KB |
Output is correct |
73 |
Correct |
1277 ms |
7632 KB |
Output is correct |
74 |
Correct |
1321 ms |
7688 KB |
Output is correct |
75 |
Correct |
1289 ms |
7628 KB |
Output is correct |
76 |
Correct |
1150 ms |
7604 KB |
Output is correct |
77 |
Correct |
1147 ms |
7592 KB |
Output is correct |
78 |
Correct |
1116 ms |
7636 KB |
Output is correct |
79 |
Correct |
985 ms |
7728 KB |
Output is correct |
80 |
Correct |
980 ms |
7728 KB |
Output is correct |
81 |
Correct |
997 ms |
7760 KB |
Output is correct |
82 |
Correct |
920 ms |
7612 KB |
Output is correct |
83 |
Correct |
902 ms |
7552 KB |
Output is correct |
84 |
Correct |
887 ms |
7504 KB |
Output is correct |
85 |
Correct |
2504 ms |
14036 KB |
Output is correct |
86 |
Correct |
227 ms |
7464 KB |
Output is correct |
87 |
Correct |
170 ms |
7564 KB |
Output is correct |
88 |
Correct |
1939 ms |
12356 KB |
Output is correct |
89 |
Correct |
2502 ms |
14020 KB |
Output is correct |
90 |
Correct |
1921 ms |
12552 KB |
Output is correct |
91 |
Correct |
1365 ms |
10356 KB |
Output is correct |
92 |
Correct |
1304 ms |
10568 KB |
Output is correct |
93 |
Correct |
1664 ms |
10540 KB |
Output is correct |
94 |
Correct |
1992 ms |
11956 KB |
Output is correct |
95 |
Correct |
1926 ms |
12228 KB |
Output is correct |
96 |
Correct |
2195 ms |
12128 KB |
Output is correct |
97 |
Correct |
1750 ms |
12708 KB |
Output is correct |
98 |
Correct |
1730 ms |
12244 KB |
Output is correct |
99 |
Correct |
2513 ms |
13968 KB |
Output is correct |
100 |
Correct |
2479 ms |
13816 KB |
Output is correct |
101 |
Correct |
2496 ms |
13892 KB |
Output is correct |
102 |
Correct |
2574 ms |
13952 KB |
Output is correct |
103 |
Correct |
2408 ms |
12696 KB |
Output is correct |
104 |
Correct |
2417 ms |
12804 KB |
Output is correct |
105 |
Correct |
1908 ms |
12492 KB |
Output is correct |
106 |
Correct |
1572 ms |
11972 KB |
Output is correct |
107 |
Correct |
1849 ms |
12784 KB |
Output is correct |
108 |
Correct |
2525 ms |
13540 KB |
Output is correct |
109 |
Correct |
2126 ms |
11356 KB |
Output is correct |