# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
862580 |
2023-10-18T14:00:41 Z |
mraron |
Bridges (APIO19_bridges) |
C++14 |
|
2699 ms |
17972 KB |
#include<bits/stdc++.h>
using namespace std;
struct edge {
int a,b,c;
int ind;
} edgs[100001];
struct query {
int typ;
int x,y;
} qs[100010];
int sz[100010], par[100010];
vector<int> adj[100010];
int volt[100010], cur=0;
void dfs(int x, int& ans) {
volt[x]=cur;
ans+=sz[x];
for(int i:adj[x]) {
if(volt[i]<cur) {
dfs(i, ans);
}
}
}
int n,m;
void init() {
fill(sz+1, sz+n+1, 1);
fill(par+1, par+n+1, -1);
}
int get(int x) {
if(par[x]==-1) return x;
return par[x]=get(par[x]);
}
void merge(int x, int y) {
int px=get(x), py=get(y);
if(px!=py) {
par[px]=py;
sz[py]+=sz[px];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<m;++i) {
cin>>edgs[i].a>>edgs[i].b>>edgs[i].c;
edgs[i].ind=i;
}
int q;
cin>>q;
for(int i=0;i<q;++i) {
cin>>qs[i].typ>>qs[i].x>>qs[i].y;
if(qs[i].typ==1) qs[i].x--;
}
vector<int> results(q);
const int blksz=500;
for(int L=0;;L+=blksz) {
int R=min(q-1, L+blksz-1);
if(L>=q) break ;
vector<bool> changedHere(m);
vector<int> asked, bridges;
for(int i=L;i<=R;++i) {
if(qs[i].typ==1) changedHere[qs[i].x]=true;
else asked.push_back(i);
}
for(int i=0;i<m;++i) {
if(!changedHere[i]) {
bridges.push_back(i);
}
}
sort(asked.begin(), asked.end(), [&](int x, int y) -> bool {
return qs[x].y>qs[y].y;
});
sort(bridges.begin(), bridges.end(), [&](int x, int y) -> bool {
return edgs[x].c>edgs[y].c;
});
int ind=0;
vector<int> last(m, -1);
init();
for(int i=0;i<(int)asked.size();++i) {
while(ind<(int)bridges.size() && edgs[bridges[ind]].c>=qs[asked[i]].y) {
merge(edgs[bridges[ind]].a, edgs[bridges[ind]].b);
ind++;
}
vector<int> lst;
for(int j=asked[i];j>=L;--j) {
if(qs[j].typ==1) {
if(last[qs[j].x]!=i && qs[j].y>=qs[asked[i]].y) {
//~ cerr<<asked[i]<<" "<<j<<"firstcase\n";
int a=get(edgs[qs[j].x].a), b=get(edgs[qs[j].x].b);
if(a!=b) {
adj[a].push_back(b);
adj[b].push_back(a);
lst.push_back(a);
lst.push_back(b);
}
}
last[qs[j].x]=i;
}
}
for(int j=asked[i]+1;j<=R;++j) {
if(qs[j].typ==1 && last[qs[j].x]!=i) {
if(edgs[qs[j].x].c>=qs[asked[i]].y) {
int a=get(edgs[qs[j].x].a), b=get(edgs[qs[j].x].b);
if(a!=b) {
adj[a].push_back(b);
adj[b].push_back(a);
lst.push_back(a);
lst.push_back(b);
}
}
last[qs[j].x]=i;
}
}
cur++;
//~ cerr<<"NEED: "<<get(qs[asked[i]].x)<<" "<<asked[i]<<"\n";
dfs(get(qs[asked[i]].x), results[asked[i]]);
for(int i:lst) adj[i].clear();
}
for(int i=L;i<=R;++i) {
if(qs[i].typ==1) edgs[qs[i].x].c=qs[i].y;
}
}
for(int i=0;i<q;++i) if(qs[i].typ==2) cout<<results[i]<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
13 ms |
4824 KB |
Output is correct |
4 |
Correct |
6 ms |
4696 KB |
Output is correct |
5 |
Correct |
15 ms |
4952 KB |
Output is correct |
6 |
Correct |
13 ms |
4680 KB |
Output is correct |
7 |
Correct |
16 ms |
4700 KB |
Output is correct |
8 |
Correct |
15 ms |
4700 KB |
Output is correct |
9 |
Correct |
18 ms |
4692 KB |
Output is correct |
10 |
Correct |
15 ms |
4764 KB |
Output is correct |
11 |
Correct |
15 ms |
4716 KB |
Output is correct |
12 |
Correct |
17 ms |
4852 KB |
Output is correct |
13 |
Correct |
19 ms |
4696 KB |
Output is correct |
14 |
Correct |
17 ms |
4700 KB |
Output is correct |
15 |
Correct |
18 ms |
4720 KB |
Output is correct |
16 |
Correct |
16 ms |
4700 KB |
Output is correct |
17 |
Correct |
16 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1179 ms |
8604 KB |
Output is correct |
2 |
Correct |
1159 ms |
11280 KB |
Output is correct |
3 |
Correct |
1173 ms |
11380 KB |
Output is correct |
4 |
Correct |
1173 ms |
11204 KB |
Output is correct |
5 |
Correct |
1168 ms |
11360 KB |
Output is correct |
6 |
Correct |
1378 ms |
10732 KB |
Output is correct |
7 |
Correct |
1309 ms |
10824 KB |
Output is correct |
8 |
Correct |
1274 ms |
10920 KB |
Output is correct |
9 |
Correct |
55 ms |
6804 KB |
Output is correct |
10 |
Correct |
658 ms |
10032 KB |
Output is correct |
11 |
Correct |
651 ms |
9948 KB |
Output is correct |
12 |
Correct |
1081 ms |
10116 KB |
Output is correct |
13 |
Correct |
1082 ms |
11196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
959 ms |
9924 KB |
Output is correct |
2 |
Correct |
471 ms |
10408 KB |
Output is correct |
3 |
Correct |
1081 ms |
14520 KB |
Output is correct |
4 |
Correct |
987 ms |
17972 KB |
Output is correct |
5 |
Correct |
51 ms |
6736 KB |
Output is correct |
6 |
Correct |
1070 ms |
16172 KB |
Output is correct |
7 |
Correct |
988 ms |
15852 KB |
Output is correct |
8 |
Correct |
964 ms |
13688 KB |
Output is correct |
9 |
Correct |
904 ms |
10880 KB |
Output is correct |
10 |
Correct |
856 ms |
10596 KB |
Output is correct |
11 |
Correct |
867 ms |
15632 KB |
Output is correct |
12 |
Correct |
819 ms |
13912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2471 ms |
8476 KB |
Output is correct |
2 |
Correct |
50 ms |
5532 KB |
Output is correct |
3 |
Correct |
210 ms |
7056 KB |
Output is correct |
4 |
Correct |
65 ms |
7084 KB |
Output is correct |
5 |
Correct |
1253 ms |
8584 KB |
Output is correct |
6 |
Correct |
2429 ms |
8288 KB |
Output is correct |
7 |
Correct |
1237 ms |
8144 KB |
Output is correct |
8 |
Correct |
1045 ms |
6976 KB |
Output is correct |
9 |
Correct |
1035 ms |
6784 KB |
Output is correct |
10 |
Correct |
1047 ms |
7120 KB |
Output is correct |
11 |
Correct |
1736 ms |
7932 KB |
Output is correct |
12 |
Correct |
1693 ms |
7700 KB |
Output is correct |
13 |
Correct |
1737 ms |
7664 KB |
Output is correct |
14 |
Correct |
1072 ms |
8032 KB |
Output is correct |
15 |
Correct |
1151 ms |
8244 KB |
Output is correct |
16 |
Correct |
2421 ms |
8788 KB |
Output is correct |
17 |
Correct |
2438 ms |
8136 KB |
Output is correct |
18 |
Correct |
2352 ms |
8004 KB |
Output is correct |
19 |
Correct |
2364 ms |
8272 KB |
Output is correct |
20 |
Correct |
1947 ms |
7920 KB |
Output is correct |
21 |
Correct |
2000 ms |
7808 KB |
Output is correct |
22 |
Correct |
2342 ms |
7960 KB |
Output is correct |
23 |
Correct |
1305 ms |
7832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1179 ms |
8604 KB |
Output is correct |
2 |
Correct |
1159 ms |
11280 KB |
Output is correct |
3 |
Correct |
1173 ms |
11380 KB |
Output is correct |
4 |
Correct |
1173 ms |
11204 KB |
Output is correct |
5 |
Correct |
1168 ms |
11360 KB |
Output is correct |
6 |
Correct |
1378 ms |
10732 KB |
Output is correct |
7 |
Correct |
1309 ms |
10824 KB |
Output is correct |
8 |
Correct |
1274 ms |
10920 KB |
Output is correct |
9 |
Correct |
55 ms |
6804 KB |
Output is correct |
10 |
Correct |
658 ms |
10032 KB |
Output is correct |
11 |
Correct |
651 ms |
9948 KB |
Output is correct |
12 |
Correct |
1081 ms |
10116 KB |
Output is correct |
13 |
Correct |
1082 ms |
11196 KB |
Output is correct |
14 |
Correct |
959 ms |
9924 KB |
Output is correct |
15 |
Correct |
471 ms |
10408 KB |
Output is correct |
16 |
Correct |
1081 ms |
14520 KB |
Output is correct |
17 |
Correct |
987 ms |
17972 KB |
Output is correct |
18 |
Correct |
51 ms |
6736 KB |
Output is correct |
19 |
Correct |
1070 ms |
16172 KB |
Output is correct |
20 |
Correct |
988 ms |
15852 KB |
Output is correct |
21 |
Correct |
964 ms |
13688 KB |
Output is correct |
22 |
Correct |
904 ms |
10880 KB |
Output is correct |
23 |
Correct |
856 ms |
10596 KB |
Output is correct |
24 |
Correct |
867 ms |
15632 KB |
Output is correct |
25 |
Correct |
819 ms |
13912 KB |
Output is correct |
26 |
Correct |
1447 ms |
14588 KB |
Output is correct |
27 |
Correct |
1490 ms |
12540 KB |
Output is correct |
28 |
Correct |
1430 ms |
15880 KB |
Output is correct |
29 |
Correct |
1282 ms |
13000 KB |
Output is correct |
30 |
Correct |
1325 ms |
11056 KB |
Output is correct |
31 |
Correct |
1362 ms |
11096 KB |
Output is correct |
32 |
Correct |
1357 ms |
10932 KB |
Output is correct |
33 |
Correct |
1263 ms |
11256 KB |
Output is correct |
34 |
Correct |
1288 ms |
11460 KB |
Output is correct |
35 |
Correct |
1297 ms |
11332 KB |
Output is correct |
36 |
Correct |
1181 ms |
11096 KB |
Output is correct |
37 |
Correct |
1175 ms |
11128 KB |
Output is correct |
38 |
Correct |
1196 ms |
11444 KB |
Output is correct |
39 |
Correct |
1159 ms |
10720 KB |
Output is correct |
40 |
Correct |
1190 ms |
10476 KB |
Output is correct |
41 |
Correct |
1204 ms |
10688 KB |
Output is correct |
42 |
Correct |
1106 ms |
11184 KB |
Output is correct |
43 |
Correct |
1103 ms |
11236 KB |
Output is correct |
44 |
Correct |
1137 ms |
11196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
13 ms |
4824 KB |
Output is correct |
4 |
Correct |
6 ms |
4696 KB |
Output is correct |
5 |
Correct |
15 ms |
4952 KB |
Output is correct |
6 |
Correct |
13 ms |
4680 KB |
Output is correct |
7 |
Correct |
16 ms |
4700 KB |
Output is correct |
8 |
Correct |
15 ms |
4700 KB |
Output is correct |
9 |
Correct |
18 ms |
4692 KB |
Output is correct |
10 |
Correct |
15 ms |
4764 KB |
Output is correct |
11 |
Correct |
15 ms |
4716 KB |
Output is correct |
12 |
Correct |
17 ms |
4852 KB |
Output is correct |
13 |
Correct |
19 ms |
4696 KB |
Output is correct |
14 |
Correct |
17 ms |
4700 KB |
Output is correct |
15 |
Correct |
18 ms |
4720 KB |
Output is correct |
16 |
Correct |
16 ms |
4700 KB |
Output is correct |
17 |
Correct |
16 ms |
4700 KB |
Output is correct |
18 |
Correct |
1179 ms |
8604 KB |
Output is correct |
19 |
Correct |
1159 ms |
11280 KB |
Output is correct |
20 |
Correct |
1173 ms |
11380 KB |
Output is correct |
21 |
Correct |
1173 ms |
11204 KB |
Output is correct |
22 |
Correct |
1168 ms |
11360 KB |
Output is correct |
23 |
Correct |
1378 ms |
10732 KB |
Output is correct |
24 |
Correct |
1309 ms |
10824 KB |
Output is correct |
25 |
Correct |
1274 ms |
10920 KB |
Output is correct |
26 |
Correct |
55 ms |
6804 KB |
Output is correct |
27 |
Correct |
658 ms |
10032 KB |
Output is correct |
28 |
Correct |
651 ms |
9948 KB |
Output is correct |
29 |
Correct |
1081 ms |
10116 KB |
Output is correct |
30 |
Correct |
1082 ms |
11196 KB |
Output is correct |
31 |
Correct |
959 ms |
9924 KB |
Output is correct |
32 |
Correct |
471 ms |
10408 KB |
Output is correct |
33 |
Correct |
1081 ms |
14520 KB |
Output is correct |
34 |
Correct |
987 ms |
17972 KB |
Output is correct |
35 |
Correct |
51 ms |
6736 KB |
Output is correct |
36 |
Correct |
1070 ms |
16172 KB |
Output is correct |
37 |
Correct |
988 ms |
15852 KB |
Output is correct |
38 |
Correct |
964 ms |
13688 KB |
Output is correct |
39 |
Correct |
904 ms |
10880 KB |
Output is correct |
40 |
Correct |
856 ms |
10596 KB |
Output is correct |
41 |
Correct |
867 ms |
15632 KB |
Output is correct |
42 |
Correct |
819 ms |
13912 KB |
Output is correct |
43 |
Correct |
2471 ms |
8476 KB |
Output is correct |
44 |
Correct |
50 ms |
5532 KB |
Output is correct |
45 |
Correct |
210 ms |
7056 KB |
Output is correct |
46 |
Correct |
65 ms |
7084 KB |
Output is correct |
47 |
Correct |
1253 ms |
8584 KB |
Output is correct |
48 |
Correct |
2429 ms |
8288 KB |
Output is correct |
49 |
Correct |
1237 ms |
8144 KB |
Output is correct |
50 |
Correct |
1045 ms |
6976 KB |
Output is correct |
51 |
Correct |
1035 ms |
6784 KB |
Output is correct |
52 |
Correct |
1047 ms |
7120 KB |
Output is correct |
53 |
Correct |
1736 ms |
7932 KB |
Output is correct |
54 |
Correct |
1693 ms |
7700 KB |
Output is correct |
55 |
Correct |
1737 ms |
7664 KB |
Output is correct |
56 |
Correct |
1072 ms |
8032 KB |
Output is correct |
57 |
Correct |
1151 ms |
8244 KB |
Output is correct |
58 |
Correct |
2421 ms |
8788 KB |
Output is correct |
59 |
Correct |
2438 ms |
8136 KB |
Output is correct |
60 |
Correct |
2352 ms |
8004 KB |
Output is correct |
61 |
Correct |
2364 ms |
8272 KB |
Output is correct |
62 |
Correct |
1947 ms |
7920 KB |
Output is correct |
63 |
Correct |
2000 ms |
7808 KB |
Output is correct |
64 |
Correct |
2342 ms |
7960 KB |
Output is correct |
65 |
Correct |
1305 ms |
7832 KB |
Output is correct |
66 |
Correct |
1447 ms |
14588 KB |
Output is correct |
67 |
Correct |
1490 ms |
12540 KB |
Output is correct |
68 |
Correct |
1430 ms |
15880 KB |
Output is correct |
69 |
Correct |
1282 ms |
13000 KB |
Output is correct |
70 |
Correct |
1325 ms |
11056 KB |
Output is correct |
71 |
Correct |
1362 ms |
11096 KB |
Output is correct |
72 |
Correct |
1357 ms |
10932 KB |
Output is correct |
73 |
Correct |
1263 ms |
11256 KB |
Output is correct |
74 |
Correct |
1288 ms |
11460 KB |
Output is correct |
75 |
Correct |
1297 ms |
11332 KB |
Output is correct |
76 |
Correct |
1181 ms |
11096 KB |
Output is correct |
77 |
Correct |
1175 ms |
11128 KB |
Output is correct |
78 |
Correct |
1196 ms |
11444 KB |
Output is correct |
79 |
Correct |
1159 ms |
10720 KB |
Output is correct |
80 |
Correct |
1190 ms |
10476 KB |
Output is correct |
81 |
Correct |
1204 ms |
10688 KB |
Output is correct |
82 |
Correct |
1106 ms |
11184 KB |
Output is correct |
83 |
Correct |
1103 ms |
11236 KB |
Output is correct |
84 |
Correct |
1137 ms |
11196 KB |
Output is correct |
85 |
Correct |
2690 ms |
15244 KB |
Output is correct |
86 |
Correct |
216 ms |
9432 KB |
Output is correct |
87 |
Correct |
72 ms |
9064 KB |
Output is correct |
88 |
Correct |
1381 ms |
11592 KB |
Output is correct |
89 |
Correct |
2699 ms |
15240 KB |
Output is correct |
90 |
Correct |
1379 ms |
11796 KB |
Output is correct |
91 |
Correct |
1272 ms |
11132 KB |
Output is correct |
92 |
Correct |
1246 ms |
11328 KB |
Output is correct |
93 |
Correct |
1360 ms |
10240 KB |
Output is correct |
94 |
Correct |
1961 ms |
12512 KB |
Output is correct |
95 |
Correct |
1880 ms |
12376 KB |
Output is correct |
96 |
Correct |
1819 ms |
11232 KB |
Output is correct |
97 |
Correct |
1291 ms |
11008 KB |
Output is correct |
98 |
Correct |
1308 ms |
12096 KB |
Output is correct |
99 |
Correct |
2595 ms |
13848 KB |
Output is correct |
100 |
Correct |
2684 ms |
13812 KB |
Output is correct |
101 |
Correct |
2561 ms |
13864 KB |
Output is correct |
102 |
Correct |
2555 ms |
13868 KB |
Output is correct |
103 |
Correct |
2037 ms |
11660 KB |
Output is correct |
104 |
Correct |
2078 ms |
11812 KB |
Output is correct |
105 |
Correct |
1992 ms |
11700 KB |
Output is correct |
106 |
Correct |
1749 ms |
11124 KB |
Output is correct |
107 |
Correct |
1976 ms |
11504 KB |
Output is correct |
108 |
Correct |
2474 ms |
12540 KB |
Output is correct |
109 |
Correct |
1329 ms |
10388 KB |
Output is correct |