# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
862582 |
2023-10-18T14:02:09 Z |
mraron |
Bridges (APIO19_bridges) |
C++14 |
|
2019 ms |
19668 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=700;
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 |
16 ms |
4652 KB |
Output is correct |
4 |
Correct |
7 ms |
4444 KB |
Output is correct |
5 |
Correct |
18 ms |
4444 KB |
Output is correct |
6 |
Correct |
15 ms |
4616 KB |
Output is correct |
7 |
Correct |
18 ms |
4444 KB |
Output is correct |
8 |
Correct |
23 ms |
4444 KB |
Output is correct |
9 |
Correct |
19 ms |
4444 KB |
Output is correct |
10 |
Correct |
17 ms |
4444 KB |
Output is correct |
11 |
Correct |
17 ms |
4444 KB |
Output is correct |
12 |
Correct |
18 ms |
4440 KB |
Output is correct |
13 |
Correct |
23 ms |
4624 KB |
Output is correct |
14 |
Correct |
23 ms |
4624 KB |
Output is correct |
15 |
Correct |
24 ms |
4444 KB |
Output is correct |
16 |
Correct |
24 ms |
4612 KB |
Output is correct |
17 |
Correct |
23 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
977 ms |
8324 KB |
Output is correct |
2 |
Correct |
1012 ms |
8336 KB |
Output is correct |
3 |
Correct |
974 ms |
8204 KB |
Output is correct |
4 |
Correct |
1000 ms |
8364 KB |
Output is correct |
5 |
Correct |
967 ms |
8160 KB |
Output is correct |
6 |
Correct |
1306 ms |
8500 KB |
Output is correct |
7 |
Correct |
1207 ms |
8064 KB |
Output is correct |
8 |
Correct |
1188 ms |
8180 KB |
Output is correct |
9 |
Correct |
62 ms |
5460 KB |
Output is correct |
10 |
Correct |
695 ms |
8332 KB |
Output is correct |
11 |
Correct |
659 ms |
8120 KB |
Output is correct |
12 |
Correct |
898 ms |
7320 KB |
Output is correct |
13 |
Correct |
869 ms |
8532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
828 ms |
11108 KB |
Output is correct |
2 |
Correct |
560 ms |
9296 KB |
Output is correct |
3 |
Correct |
998 ms |
14740 KB |
Output is correct |
4 |
Correct |
859 ms |
19668 KB |
Output is correct |
5 |
Correct |
75 ms |
5376 KB |
Output is correct |
6 |
Correct |
1022 ms |
17196 KB |
Output is correct |
7 |
Correct |
893 ms |
16480 KB |
Output is correct |
8 |
Correct |
812 ms |
13188 KB |
Output is correct |
9 |
Correct |
749 ms |
9392 KB |
Output is correct |
10 |
Correct |
720 ms |
8592 KB |
Output is correct |
11 |
Correct |
718 ms |
15452 KB |
Output is correct |
12 |
Correct |
663 ms |
12368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1825 ms |
8436 KB |
Output is correct |
2 |
Correct |
63 ms |
5380 KB |
Output is correct |
3 |
Correct |
174 ms |
7064 KB |
Output is correct |
4 |
Correct |
61 ms |
7096 KB |
Output is correct |
5 |
Correct |
935 ms |
8212 KB |
Output is correct |
6 |
Correct |
1810 ms |
8264 KB |
Output is correct |
7 |
Correct |
928 ms |
8032 KB |
Output is correct |
8 |
Correct |
796 ms |
7012 KB |
Output is correct |
9 |
Correct |
836 ms |
6908 KB |
Output is correct |
10 |
Correct |
780 ms |
7000 KB |
Output is correct |
11 |
Correct |
1296 ms |
7640 KB |
Output is correct |
12 |
Correct |
1277 ms |
7876 KB |
Output is correct |
13 |
Correct |
1295 ms |
7696 KB |
Output is correct |
14 |
Correct |
833 ms |
8288 KB |
Output is correct |
15 |
Correct |
853 ms |
8176 KB |
Output is correct |
16 |
Correct |
1812 ms |
8308 KB |
Output is correct |
17 |
Correct |
1822 ms |
8276 KB |
Output is correct |
18 |
Correct |
1764 ms |
8292 KB |
Output is correct |
19 |
Correct |
1766 ms |
8536 KB |
Output is correct |
20 |
Correct |
1438 ms |
7856 KB |
Output is correct |
21 |
Correct |
1427 ms |
7916 KB |
Output is correct |
22 |
Correct |
1733 ms |
8148 KB |
Output is correct |
23 |
Correct |
971 ms |
7852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
977 ms |
8324 KB |
Output is correct |
2 |
Correct |
1012 ms |
8336 KB |
Output is correct |
3 |
Correct |
974 ms |
8204 KB |
Output is correct |
4 |
Correct |
1000 ms |
8364 KB |
Output is correct |
5 |
Correct |
967 ms |
8160 KB |
Output is correct |
6 |
Correct |
1306 ms |
8500 KB |
Output is correct |
7 |
Correct |
1207 ms |
8064 KB |
Output is correct |
8 |
Correct |
1188 ms |
8180 KB |
Output is correct |
9 |
Correct |
62 ms |
5460 KB |
Output is correct |
10 |
Correct |
695 ms |
8332 KB |
Output is correct |
11 |
Correct |
659 ms |
8120 KB |
Output is correct |
12 |
Correct |
898 ms |
7320 KB |
Output is correct |
13 |
Correct |
869 ms |
8532 KB |
Output is correct |
14 |
Correct |
828 ms |
11108 KB |
Output is correct |
15 |
Correct |
560 ms |
9296 KB |
Output is correct |
16 |
Correct |
998 ms |
14740 KB |
Output is correct |
17 |
Correct |
859 ms |
19668 KB |
Output is correct |
18 |
Correct |
75 ms |
5376 KB |
Output is correct |
19 |
Correct |
1022 ms |
17196 KB |
Output is correct |
20 |
Correct |
893 ms |
16480 KB |
Output is correct |
21 |
Correct |
812 ms |
13188 KB |
Output is correct |
22 |
Correct |
749 ms |
9392 KB |
Output is correct |
23 |
Correct |
720 ms |
8592 KB |
Output is correct |
24 |
Correct |
718 ms |
15452 KB |
Output is correct |
25 |
Correct |
663 ms |
12368 KB |
Output is correct |
26 |
Correct |
1196 ms |
13948 KB |
Output is correct |
27 |
Correct |
1248 ms |
11176 KB |
Output is correct |
28 |
Correct |
1203 ms |
16792 KB |
Output is correct |
29 |
Correct |
1018 ms |
11176 KB |
Output is correct |
30 |
Correct |
1180 ms |
8372 KB |
Output is correct |
31 |
Correct |
1178 ms |
8256 KB |
Output is correct |
32 |
Correct |
1204 ms |
8624 KB |
Output is correct |
33 |
Correct |
1057 ms |
8460 KB |
Output is correct |
34 |
Correct |
1062 ms |
8656 KB |
Output is correct |
35 |
Correct |
1094 ms |
8424 KB |
Output is correct |
36 |
Correct |
948 ms |
8528 KB |
Output is correct |
37 |
Correct |
958 ms |
8420 KB |
Output is correct |
38 |
Correct |
950 ms |
8328 KB |
Output is correct |
39 |
Correct |
872 ms |
7744 KB |
Output is correct |
40 |
Correct |
855 ms |
7708 KB |
Output is correct |
41 |
Correct |
853 ms |
7644 KB |
Output is correct |
42 |
Correct |
817 ms |
8520 KB |
Output is correct |
43 |
Correct |
839 ms |
8488 KB |
Output is correct |
44 |
Correct |
832 ms |
8496 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 |
16 ms |
4652 KB |
Output is correct |
4 |
Correct |
7 ms |
4444 KB |
Output is correct |
5 |
Correct |
18 ms |
4444 KB |
Output is correct |
6 |
Correct |
15 ms |
4616 KB |
Output is correct |
7 |
Correct |
18 ms |
4444 KB |
Output is correct |
8 |
Correct |
23 ms |
4444 KB |
Output is correct |
9 |
Correct |
19 ms |
4444 KB |
Output is correct |
10 |
Correct |
17 ms |
4444 KB |
Output is correct |
11 |
Correct |
17 ms |
4444 KB |
Output is correct |
12 |
Correct |
18 ms |
4440 KB |
Output is correct |
13 |
Correct |
23 ms |
4624 KB |
Output is correct |
14 |
Correct |
23 ms |
4624 KB |
Output is correct |
15 |
Correct |
24 ms |
4444 KB |
Output is correct |
16 |
Correct |
24 ms |
4612 KB |
Output is correct |
17 |
Correct |
23 ms |
4444 KB |
Output is correct |
18 |
Correct |
977 ms |
8324 KB |
Output is correct |
19 |
Correct |
1012 ms |
8336 KB |
Output is correct |
20 |
Correct |
974 ms |
8204 KB |
Output is correct |
21 |
Correct |
1000 ms |
8364 KB |
Output is correct |
22 |
Correct |
967 ms |
8160 KB |
Output is correct |
23 |
Correct |
1306 ms |
8500 KB |
Output is correct |
24 |
Correct |
1207 ms |
8064 KB |
Output is correct |
25 |
Correct |
1188 ms |
8180 KB |
Output is correct |
26 |
Correct |
62 ms |
5460 KB |
Output is correct |
27 |
Correct |
695 ms |
8332 KB |
Output is correct |
28 |
Correct |
659 ms |
8120 KB |
Output is correct |
29 |
Correct |
898 ms |
7320 KB |
Output is correct |
30 |
Correct |
869 ms |
8532 KB |
Output is correct |
31 |
Correct |
828 ms |
11108 KB |
Output is correct |
32 |
Correct |
560 ms |
9296 KB |
Output is correct |
33 |
Correct |
998 ms |
14740 KB |
Output is correct |
34 |
Correct |
859 ms |
19668 KB |
Output is correct |
35 |
Correct |
75 ms |
5376 KB |
Output is correct |
36 |
Correct |
1022 ms |
17196 KB |
Output is correct |
37 |
Correct |
893 ms |
16480 KB |
Output is correct |
38 |
Correct |
812 ms |
13188 KB |
Output is correct |
39 |
Correct |
749 ms |
9392 KB |
Output is correct |
40 |
Correct |
720 ms |
8592 KB |
Output is correct |
41 |
Correct |
718 ms |
15452 KB |
Output is correct |
42 |
Correct |
663 ms |
12368 KB |
Output is correct |
43 |
Correct |
1825 ms |
8436 KB |
Output is correct |
44 |
Correct |
63 ms |
5380 KB |
Output is correct |
45 |
Correct |
174 ms |
7064 KB |
Output is correct |
46 |
Correct |
61 ms |
7096 KB |
Output is correct |
47 |
Correct |
935 ms |
8212 KB |
Output is correct |
48 |
Correct |
1810 ms |
8264 KB |
Output is correct |
49 |
Correct |
928 ms |
8032 KB |
Output is correct |
50 |
Correct |
796 ms |
7012 KB |
Output is correct |
51 |
Correct |
836 ms |
6908 KB |
Output is correct |
52 |
Correct |
780 ms |
7000 KB |
Output is correct |
53 |
Correct |
1296 ms |
7640 KB |
Output is correct |
54 |
Correct |
1277 ms |
7876 KB |
Output is correct |
55 |
Correct |
1295 ms |
7696 KB |
Output is correct |
56 |
Correct |
833 ms |
8288 KB |
Output is correct |
57 |
Correct |
853 ms |
8176 KB |
Output is correct |
58 |
Correct |
1812 ms |
8308 KB |
Output is correct |
59 |
Correct |
1822 ms |
8276 KB |
Output is correct |
60 |
Correct |
1764 ms |
8292 KB |
Output is correct |
61 |
Correct |
1766 ms |
8536 KB |
Output is correct |
62 |
Correct |
1438 ms |
7856 KB |
Output is correct |
63 |
Correct |
1427 ms |
7916 KB |
Output is correct |
64 |
Correct |
1733 ms |
8148 KB |
Output is correct |
65 |
Correct |
971 ms |
7852 KB |
Output is correct |
66 |
Correct |
1196 ms |
13948 KB |
Output is correct |
67 |
Correct |
1248 ms |
11176 KB |
Output is correct |
68 |
Correct |
1203 ms |
16792 KB |
Output is correct |
69 |
Correct |
1018 ms |
11176 KB |
Output is correct |
70 |
Correct |
1180 ms |
8372 KB |
Output is correct |
71 |
Correct |
1178 ms |
8256 KB |
Output is correct |
72 |
Correct |
1204 ms |
8624 KB |
Output is correct |
73 |
Correct |
1057 ms |
8460 KB |
Output is correct |
74 |
Correct |
1062 ms |
8656 KB |
Output is correct |
75 |
Correct |
1094 ms |
8424 KB |
Output is correct |
76 |
Correct |
948 ms |
8528 KB |
Output is correct |
77 |
Correct |
958 ms |
8420 KB |
Output is correct |
78 |
Correct |
950 ms |
8328 KB |
Output is correct |
79 |
Correct |
872 ms |
7744 KB |
Output is correct |
80 |
Correct |
855 ms |
7708 KB |
Output is correct |
81 |
Correct |
853 ms |
7644 KB |
Output is correct |
82 |
Correct |
817 ms |
8520 KB |
Output is correct |
83 |
Correct |
839 ms |
8488 KB |
Output is correct |
84 |
Correct |
832 ms |
8496 KB |
Output is correct |
85 |
Correct |
2019 ms |
12292 KB |
Output is correct |
86 |
Correct |
167 ms |
7092 KB |
Output is correct |
87 |
Correct |
64 ms |
7068 KB |
Output is correct |
88 |
Correct |
1038 ms |
9616 KB |
Output is correct |
89 |
Correct |
2009 ms |
12220 KB |
Output is correct |
90 |
Correct |
1027 ms |
9288 KB |
Output is correct |
91 |
Correct |
1018 ms |
8620 KB |
Output is correct |
92 |
Correct |
1024 ms |
8268 KB |
Output is correct |
93 |
Correct |
1113 ms |
7760 KB |
Output is correct |
94 |
Correct |
1471 ms |
9036 KB |
Output is correct |
95 |
Correct |
1444 ms |
9092 KB |
Output is correct |
96 |
Correct |
1366 ms |
8188 KB |
Output is correct |
97 |
Correct |
994 ms |
8764 KB |
Output is correct |
98 |
Correct |
976 ms |
9412 KB |
Output is correct |
99 |
Correct |
1949 ms |
9924 KB |
Output is correct |
100 |
Correct |
1990 ms |
10148 KB |
Output is correct |
101 |
Correct |
1911 ms |
9916 KB |
Output is correct |
102 |
Correct |
1930 ms |
10104 KB |
Output is correct |
103 |
Correct |
1506 ms |
8048 KB |
Output is correct |
104 |
Correct |
1523 ms |
8052 KB |
Output is correct |
105 |
Correct |
1425 ms |
8332 KB |
Output is correct |
106 |
Correct |
1273 ms |
8204 KB |
Output is correct |
107 |
Correct |
1448 ms |
8016 KB |
Output is correct |
108 |
Correct |
1849 ms |
8864 KB |
Output is correct |
109 |
Correct |
1020 ms |
8020 KB |
Output is correct |