# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
558158 |
2022-05-07T01:22:27 Z |
hibiki |
Bridges (APIO19_bridges) |
C++11 |
|
2265 ms |
32168 KB |
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
const int sq = 1000;
int n,m,q;
// dsu
int l[50005],sz[50005];
stack<int> stk;
void reset()
{
iota(l + 1, l + 1 + n, 1);
fill(sz + 1, sz + 1 + n, 1);
}
int fi(int idx)
{
while(l[idx] != idx) idx = l[idx];
return idx;
}
void uni(int a,int b)
{
a = fi(a), b = fi(b);
if(a == b) return ;
if(sz[a] > sz[b]) swap(a,b);
stk.push(a);
sz[b] += sz[a];
l[a] = l[b];
}
void rollback(int x)
{
while(stk.size() > x)
{
int a = stk.top();
stk.pop();
sz[l[a]] -= sz[a];
l[a] = a;
}
}
int u[100005],v[100005],w[100005];
int ty[100005],x[100005],y[100005],ans[100005];
bool chg[100005];
vector<int> to_join[sq];
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d %d %d",&u[i],&v[i],&w[i]);
scanf("%d",&q);
for(int i=1;i<=q;i++)
scanf("%d %d %d",&ty[i],&x[i],&y[i]);
for(int l = 1; l <= q; l += sq)
{
int r = min(q + 1, l + sq);
reset();
fill(chg + 1, chg + 1 + m, false);
vector<int> ask, upd, unchg;
for(int i = l; i < r; i++)
{
if(ty[i] == 1)
{
chg[x[i]] = true;
upd.PB(i);
}
else
ask.PB(i);
}
for(int i = 1; i <= m;i++)
if(!chg[i])
unchg.PB(i);
for(int i = l; i < r; i++)
{
if(ty[i] == 1)
w[x[i]] = y[i];
else
{
to_join[i - l].clear();
for(int j: upd)
if(w[x[j]] >= y[i])
to_join[i - l].PB(x[j]);
}
}
sort(ask.begin(), ask.end(), [&](int a,int b) { return y[a] > y[b]; } );
sort(unchg.begin(), unchg.end(), [&](int a,int b) { return w[a] > w[b]; });
int ptr = 0;
for(int i: ask)
{
while(ptr < unchg.size() && w[unchg[ptr]] >= y[i])
{
uni(u[unchg[ptr]], v[unchg[ptr]]);
ptr++;
}
int prev_sz = stk.size();
for(int j: to_join[i - l])
uni(u[j], v[j]);
ans[i] = sz[fi(x[i])];
rollback(prev_sz);
}
}
for(int i = 1; i <= q; i++)
if(ty[i] == 2)
printf("%d\n",ans[i]);
}
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:38:22: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
38 | while(stk.size() > x)
| ~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | while(ptr < unchg.size() && w[unchg[ptr]] >= y[i])
| ~~~~^~~~~~~~~~~~~~
bridges.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d %d",&u[i],&v[i],&w[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
bridges.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d %d",&ty[i],&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
34 ms |
2764 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
37 ms |
2928 KB |
Output is correct |
6 |
Correct |
27 ms |
2636 KB |
Output is correct |
7 |
Correct |
35 ms |
3668 KB |
Output is correct |
8 |
Correct |
37 ms |
2672 KB |
Output is correct |
9 |
Correct |
45 ms |
4300 KB |
Output is correct |
10 |
Correct |
38 ms |
2800 KB |
Output is correct |
11 |
Correct |
37 ms |
2760 KB |
Output is correct |
12 |
Correct |
44 ms |
2892 KB |
Output is correct |
13 |
Correct |
44 ms |
2856 KB |
Output is correct |
14 |
Correct |
39 ms |
2780 KB |
Output is correct |
15 |
Correct |
44 ms |
2720 KB |
Output is correct |
16 |
Correct |
42 ms |
3920 KB |
Output is correct |
17 |
Correct |
43 ms |
3428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1272 ms |
26612 KB |
Output is correct |
2 |
Correct |
1317 ms |
26660 KB |
Output is correct |
3 |
Correct |
1289 ms |
26768 KB |
Output is correct |
4 |
Correct |
1312 ms |
26552 KB |
Output is correct |
5 |
Correct |
1309 ms |
26992 KB |
Output is correct |
6 |
Correct |
1942 ms |
28416 KB |
Output is correct |
7 |
Correct |
1908 ms |
28388 KB |
Output is correct |
8 |
Correct |
1909 ms |
28392 KB |
Output is correct |
9 |
Correct |
42 ms |
2572 KB |
Output is correct |
10 |
Correct |
1092 ms |
28456 KB |
Output is correct |
11 |
Correct |
1029 ms |
28384 KB |
Output is correct |
12 |
Correct |
1106 ms |
25280 KB |
Output is correct |
13 |
Correct |
1150 ms |
27792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1063 ms |
19048 KB |
Output is correct |
2 |
Correct |
822 ms |
10004 KB |
Output is correct |
3 |
Correct |
1283 ms |
20848 KB |
Output is correct |
4 |
Correct |
1024 ms |
19144 KB |
Output is correct |
5 |
Correct |
50 ms |
2360 KB |
Output is correct |
6 |
Correct |
1198 ms |
19076 KB |
Output is correct |
7 |
Correct |
968 ms |
18796 KB |
Output is correct |
8 |
Correct |
848 ms |
18696 KB |
Output is correct |
9 |
Correct |
681 ms |
17488 KB |
Output is correct |
10 |
Correct |
606 ms |
17332 KB |
Output is correct |
11 |
Correct |
753 ms |
20208 KB |
Output is correct |
12 |
Correct |
640 ms |
20156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1529 ms |
25140 KB |
Output is correct |
2 |
Correct |
40 ms |
3404 KB |
Output is correct |
3 |
Correct |
160 ms |
4552 KB |
Output is correct |
4 |
Correct |
80 ms |
4716 KB |
Output is correct |
5 |
Correct |
765 ms |
27244 KB |
Output is correct |
6 |
Correct |
1467 ms |
28668 KB |
Output is correct |
7 |
Correct |
784 ms |
27140 KB |
Output is correct |
8 |
Correct |
724 ms |
26584 KB |
Output is correct |
9 |
Correct |
720 ms |
26672 KB |
Output is correct |
10 |
Correct |
741 ms |
26492 KB |
Output is correct |
11 |
Correct |
1104 ms |
28008 KB |
Output is correct |
12 |
Correct |
1071 ms |
28088 KB |
Output is correct |
13 |
Correct |
1107 ms |
28012 KB |
Output is correct |
14 |
Correct |
648 ms |
27220 KB |
Output is correct |
15 |
Correct |
720 ms |
27204 KB |
Output is correct |
16 |
Correct |
1466 ms |
28880 KB |
Output is correct |
17 |
Correct |
1459 ms |
28800 KB |
Output is correct |
18 |
Correct |
1448 ms |
29016 KB |
Output is correct |
19 |
Correct |
1416 ms |
28980 KB |
Output is correct |
20 |
Correct |
1232 ms |
28308 KB |
Output is correct |
21 |
Correct |
1205 ms |
28240 KB |
Output is correct |
22 |
Correct |
1369 ms |
28348 KB |
Output is correct |
23 |
Correct |
794 ms |
24888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1272 ms |
26612 KB |
Output is correct |
2 |
Correct |
1317 ms |
26660 KB |
Output is correct |
3 |
Correct |
1289 ms |
26768 KB |
Output is correct |
4 |
Correct |
1312 ms |
26552 KB |
Output is correct |
5 |
Correct |
1309 ms |
26992 KB |
Output is correct |
6 |
Correct |
1942 ms |
28416 KB |
Output is correct |
7 |
Correct |
1908 ms |
28388 KB |
Output is correct |
8 |
Correct |
1909 ms |
28392 KB |
Output is correct |
9 |
Correct |
42 ms |
2572 KB |
Output is correct |
10 |
Correct |
1092 ms |
28456 KB |
Output is correct |
11 |
Correct |
1029 ms |
28384 KB |
Output is correct |
12 |
Correct |
1106 ms |
25280 KB |
Output is correct |
13 |
Correct |
1150 ms |
27792 KB |
Output is correct |
14 |
Correct |
1063 ms |
19048 KB |
Output is correct |
15 |
Correct |
822 ms |
10004 KB |
Output is correct |
16 |
Correct |
1283 ms |
20848 KB |
Output is correct |
17 |
Correct |
1024 ms |
19144 KB |
Output is correct |
18 |
Correct |
50 ms |
2360 KB |
Output is correct |
19 |
Correct |
1198 ms |
19076 KB |
Output is correct |
20 |
Correct |
968 ms |
18796 KB |
Output is correct |
21 |
Correct |
848 ms |
18696 KB |
Output is correct |
22 |
Correct |
681 ms |
17488 KB |
Output is correct |
23 |
Correct |
606 ms |
17332 KB |
Output is correct |
24 |
Correct |
753 ms |
20208 KB |
Output is correct |
25 |
Correct |
640 ms |
20156 KB |
Output is correct |
26 |
Correct |
1285 ms |
26684 KB |
Output is correct |
27 |
Correct |
1591 ms |
28324 KB |
Output is correct |
28 |
Correct |
1310 ms |
26488 KB |
Output is correct |
29 |
Correct |
931 ms |
26052 KB |
Output is correct |
30 |
Correct |
1504 ms |
28116 KB |
Output is correct |
31 |
Correct |
1541 ms |
28328 KB |
Output is correct |
32 |
Correct |
1553 ms |
28240 KB |
Output is correct |
33 |
Correct |
1277 ms |
26532 KB |
Output is correct |
34 |
Correct |
1299 ms |
26276 KB |
Output is correct |
35 |
Correct |
1289 ms |
26404 KB |
Output is correct |
36 |
Correct |
990 ms |
26220 KB |
Output is correct |
37 |
Correct |
959 ms |
26032 KB |
Output is correct |
38 |
Correct |
937 ms |
26044 KB |
Output is correct |
39 |
Correct |
780 ms |
24824 KB |
Output is correct |
40 |
Correct |
774 ms |
24760 KB |
Output is correct |
41 |
Correct |
781 ms |
24656 KB |
Output is correct |
42 |
Correct |
780 ms |
26892 KB |
Output is correct |
43 |
Correct |
796 ms |
26612 KB |
Output is correct |
44 |
Correct |
767 ms |
26528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
34 ms |
2764 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
37 ms |
2928 KB |
Output is correct |
6 |
Correct |
27 ms |
2636 KB |
Output is correct |
7 |
Correct |
35 ms |
3668 KB |
Output is correct |
8 |
Correct |
37 ms |
2672 KB |
Output is correct |
9 |
Correct |
45 ms |
4300 KB |
Output is correct |
10 |
Correct |
38 ms |
2800 KB |
Output is correct |
11 |
Correct |
37 ms |
2760 KB |
Output is correct |
12 |
Correct |
44 ms |
2892 KB |
Output is correct |
13 |
Correct |
44 ms |
2856 KB |
Output is correct |
14 |
Correct |
39 ms |
2780 KB |
Output is correct |
15 |
Correct |
44 ms |
2720 KB |
Output is correct |
16 |
Correct |
42 ms |
3920 KB |
Output is correct |
17 |
Correct |
43 ms |
3428 KB |
Output is correct |
18 |
Correct |
1272 ms |
26612 KB |
Output is correct |
19 |
Correct |
1317 ms |
26660 KB |
Output is correct |
20 |
Correct |
1289 ms |
26768 KB |
Output is correct |
21 |
Correct |
1312 ms |
26552 KB |
Output is correct |
22 |
Correct |
1309 ms |
26992 KB |
Output is correct |
23 |
Correct |
1942 ms |
28416 KB |
Output is correct |
24 |
Correct |
1908 ms |
28388 KB |
Output is correct |
25 |
Correct |
1909 ms |
28392 KB |
Output is correct |
26 |
Correct |
42 ms |
2572 KB |
Output is correct |
27 |
Correct |
1092 ms |
28456 KB |
Output is correct |
28 |
Correct |
1029 ms |
28384 KB |
Output is correct |
29 |
Correct |
1106 ms |
25280 KB |
Output is correct |
30 |
Correct |
1150 ms |
27792 KB |
Output is correct |
31 |
Correct |
1063 ms |
19048 KB |
Output is correct |
32 |
Correct |
822 ms |
10004 KB |
Output is correct |
33 |
Correct |
1283 ms |
20848 KB |
Output is correct |
34 |
Correct |
1024 ms |
19144 KB |
Output is correct |
35 |
Correct |
50 ms |
2360 KB |
Output is correct |
36 |
Correct |
1198 ms |
19076 KB |
Output is correct |
37 |
Correct |
968 ms |
18796 KB |
Output is correct |
38 |
Correct |
848 ms |
18696 KB |
Output is correct |
39 |
Correct |
681 ms |
17488 KB |
Output is correct |
40 |
Correct |
606 ms |
17332 KB |
Output is correct |
41 |
Correct |
753 ms |
20208 KB |
Output is correct |
42 |
Correct |
640 ms |
20156 KB |
Output is correct |
43 |
Correct |
1529 ms |
25140 KB |
Output is correct |
44 |
Correct |
40 ms |
3404 KB |
Output is correct |
45 |
Correct |
160 ms |
4552 KB |
Output is correct |
46 |
Correct |
80 ms |
4716 KB |
Output is correct |
47 |
Correct |
765 ms |
27244 KB |
Output is correct |
48 |
Correct |
1467 ms |
28668 KB |
Output is correct |
49 |
Correct |
784 ms |
27140 KB |
Output is correct |
50 |
Correct |
724 ms |
26584 KB |
Output is correct |
51 |
Correct |
720 ms |
26672 KB |
Output is correct |
52 |
Correct |
741 ms |
26492 KB |
Output is correct |
53 |
Correct |
1104 ms |
28008 KB |
Output is correct |
54 |
Correct |
1071 ms |
28088 KB |
Output is correct |
55 |
Correct |
1107 ms |
28012 KB |
Output is correct |
56 |
Correct |
648 ms |
27220 KB |
Output is correct |
57 |
Correct |
720 ms |
27204 KB |
Output is correct |
58 |
Correct |
1466 ms |
28880 KB |
Output is correct |
59 |
Correct |
1459 ms |
28800 KB |
Output is correct |
60 |
Correct |
1448 ms |
29016 KB |
Output is correct |
61 |
Correct |
1416 ms |
28980 KB |
Output is correct |
62 |
Correct |
1232 ms |
28308 KB |
Output is correct |
63 |
Correct |
1205 ms |
28240 KB |
Output is correct |
64 |
Correct |
1369 ms |
28348 KB |
Output is correct |
65 |
Correct |
794 ms |
24888 KB |
Output is correct |
66 |
Correct |
1285 ms |
26684 KB |
Output is correct |
67 |
Correct |
1591 ms |
28324 KB |
Output is correct |
68 |
Correct |
1310 ms |
26488 KB |
Output is correct |
69 |
Correct |
931 ms |
26052 KB |
Output is correct |
70 |
Correct |
1504 ms |
28116 KB |
Output is correct |
71 |
Correct |
1541 ms |
28328 KB |
Output is correct |
72 |
Correct |
1553 ms |
28240 KB |
Output is correct |
73 |
Correct |
1277 ms |
26532 KB |
Output is correct |
74 |
Correct |
1299 ms |
26276 KB |
Output is correct |
75 |
Correct |
1289 ms |
26404 KB |
Output is correct |
76 |
Correct |
990 ms |
26220 KB |
Output is correct |
77 |
Correct |
959 ms |
26032 KB |
Output is correct |
78 |
Correct |
937 ms |
26044 KB |
Output is correct |
79 |
Correct |
780 ms |
24824 KB |
Output is correct |
80 |
Correct |
774 ms |
24760 KB |
Output is correct |
81 |
Correct |
781 ms |
24656 KB |
Output is correct |
82 |
Correct |
780 ms |
26892 KB |
Output is correct |
83 |
Correct |
796 ms |
26612 KB |
Output is correct |
84 |
Correct |
767 ms |
26528 KB |
Output is correct |
85 |
Correct |
1858 ms |
30860 KB |
Output is correct |
86 |
Correct |
200 ms |
6528 KB |
Output is correct |
87 |
Correct |
117 ms |
8000 KB |
Output is correct |
88 |
Correct |
1119 ms |
31228 KB |
Output is correct |
89 |
Correct |
1941 ms |
30936 KB |
Output is correct |
90 |
Correct |
1220 ms |
31228 KB |
Output is correct |
91 |
Correct |
1442 ms |
28756 KB |
Output is correct |
92 |
Correct |
1536 ms |
28668 KB |
Output is correct |
93 |
Correct |
2066 ms |
30116 KB |
Output is correct |
94 |
Correct |
1574 ms |
30488 KB |
Output is correct |
95 |
Correct |
1573 ms |
30520 KB |
Output is correct |
96 |
Correct |
1965 ms |
31964 KB |
Output is correct |
97 |
Correct |
945 ms |
27636 KB |
Output is correct |
98 |
Correct |
988 ms |
30728 KB |
Output is correct |
99 |
Correct |
2066 ms |
31336 KB |
Output is correct |
100 |
Correct |
2031 ms |
30996 KB |
Output is correct |
101 |
Correct |
2112 ms |
31252 KB |
Output is correct |
102 |
Correct |
2052 ms |
31252 KB |
Output is correct |
103 |
Correct |
2198 ms |
32168 KB |
Output is correct |
104 |
Correct |
2265 ms |
32156 KB |
Output is correct |
105 |
Correct |
1674 ms |
31956 KB |
Output is correct |
106 |
Correct |
1360 ms |
31620 KB |
Output is correct |
107 |
Correct |
1571 ms |
28824 KB |
Output is correct |
108 |
Correct |
2158 ms |
31072 KB |
Output is correct |
109 |
Correct |
1485 ms |
28876 KB |
Output is correct |