#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N = 5e4 + 10;
int n, m, p, s = 1e3;
int vis[N << 1], ans[N << 1], par[N];
struct brg {
int u, v, w;
};
brg e[N << 1];
struct quest {
int t, b, r, w, s, i;
};
quest q[N << 1];
stack<pair<int, int>> rb;
int root(int x) {
if(par[x] < 0) return x;
return root(par[x]);
}
void join(int u, int v, int task) {
u = root(u);
v = root(v);
if(u == v) return;
if(par[u] > par[v]) swap(u, v);
if(task) {
rb.push({u, par[u]});
rb.push({v, par[v]});
}
par[u] += par[v];
par[v] = u;
}
void relife() {
while(!rb.empty()) {
int u, p; tie(u, p) = rb.top(); rb.pop();
par[u] = p;
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("Task.inp","r")) {
freopen("Task.inp","r",stdin);
freopen("WA.out","w",stdout);
}
cin>>n>>m;
forin(i,1,m) {
int u, v, w; cin>>u>>v>>w;
e[i] = {u, v, w};
}
cin>>p;
forin(i,1,p) {
cin>>q[i].t;
if(q[i].t == 1) cin>>q[i].b>>q[i].r;
else cin>>q[i].s>>q[i].w;
}
forin(blk,0,s) {
int f = blk * s + 1;
int l = min(p, (blk + 1) * s);
if(f > l) break;
fill(par + 1, par + n + 1, -1);
fill(vis + 1, vis + m + 1, 0);
vector<brg> rem;
vector<quest> emilia;
forin(i,f,l) {
if(q[i].t == 1) vis[q[i].b] = 1;
else {
quest aa = q[i]; aa.i = i;
emilia.push_back(aa);
}
}
forin(i,1,m) if(!vis[i]) rem.push_back(e[i]);
sort(rem.begin(), rem.end(), [] (brg x, brg y) {
return x.w < y.w;
});
sort(emilia.begin(), emilia.end(), [] (quest x, quest y) {
return x.w > y.w;
});
int j = 0;
forin(i,f,l) if(q[i].t == 1) vis[q[i].b] = e[q[i].b].w;
for(auto Q : emilia) {
int s = Q.s, w = Q.w, i = Q.i;
while(!rem.empty() && rem.back().w >= w) {
join(rem.back().u, rem.back().v, 0);
rem.pop_back();
}
forin(o,f,i) if(q[o].t == 1) e[q[o].b].w = q[o].r;
forin(o,f,l) if(q[o].t == 1 && e[q[o].b].w >= w){
join(e[q[o].b].u, e[q[o].b].v, 1);
}
forin(o,f,l) if(q[o].t == 1) e[q[o].b].w = vis[q[o].b];
s = root(s);
ans[i] = abs(par[s]);
relife();
}
forin(i,f,l) if(q[i].t == 1) e[q[i].b].w = q[i].r;
}
forin(i,1,p) if(q[i].t == 2) cout<<ans[i]<<"\n";
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:77:13: warning: unused variable 'j' [-Wunused-variable]
77 | int j = 0;
| ^
bridges.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen("Task.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen("WA.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
58 ms |
840 KB |
Output is correct |
4 |
Correct |
19 ms |
776 KB |
Output is correct |
5 |
Correct |
64 ms |
776 KB |
Output is correct |
6 |
Correct |
49 ms |
788 KB |
Output is correct |
7 |
Correct |
58 ms |
712 KB |
Output is correct |
8 |
Correct |
66 ms |
724 KB |
Output is correct |
9 |
Correct |
63 ms |
732 KB |
Output is correct |
10 |
Correct |
63 ms |
724 KB |
Output is correct |
11 |
Correct |
65 ms |
776 KB |
Output is correct |
12 |
Correct |
79 ms |
912 KB |
Output is correct |
13 |
Correct |
74 ms |
776 KB |
Output is correct |
14 |
Correct |
69 ms |
812 KB |
Output is correct |
15 |
Correct |
73 ms |
800 KB |
Output is correct |
16 |
Correct |
68 ms |
712 KB |
Output is correct |
17 |
Correct |
74 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1397 ms |
5548 KB |
Output is correct |
2 |
Correct |
1428 ms |
5644 KB |
Output is correct |
3 |
Correct |
1457 ms |
7372 KB |
Output is correct |
4 |
Correct |
1534 ms |
7420 KB |
Output is correct |
5 |
Correct |
1493 ms |
7504 KB |
Output is correct |
6 |
Correct |
2142 ms |
7388 KB |
Output is correct |
7 |
Correct |
2129 ms |
7332 KB |
Output is correct |
8 |
Correct |
2128 ms |
7336 KB |
Output is correct |
9 |
Correct |
197 ms |
4340 KB |
Output is correct |
10 |
Correct |
1461 ms |
7288 KB |
Output is correct |
11 |
Correct |
1315 ms |
7068 KB |
Output is correct |
12 |
Correct |
1268 ms |
8004 KB |
Output is correct |
13 |
Correct |
1077 ms |
8316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1210 ms |
4604 KB |
Output is correct |
2 |
Correct |
1123 ms |
4232 KB |
Output is correct |
3 |
Correct |
1503 ms |
5600 KB |
Output is correct |
4 |
Correct |
1221 ms |
5928 KB |
Output is correct |
5 |
Correct |
199 ms |
3952 KB |
Output is correct |
6 |
Correct |
1357 ms |
6864 KB |
Output is correct |
7 |
Correct |
1138 ms |
6928 KB |
Output is correct |
8 |
Correct |
1008 ms |
6820 KB |
Output is correct |
9 |
Correct |
895 ms |
6900 KB |
Output is correct |
10 |
Correct |
838 ms |
6880 KB |
Output is correct |
11 |
Correct |
720 ms |
6744 KB |
Output is correct |
12 |
Correct |
599 ms |
6804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1343 ms |
7852 KB |
Output is correct |
2 |
Correct |
194 ms |
3236 KB |
Output is correct |
3 |
Correct |
147 ms |
5004 KB |
Output is correct |
4 |
Correct |
106 ms |
4908 KB |
Output is correct |
5 |
Correct |
809 ms |
7620 KB |
Output is correct |
6 |
Correct |
1313 ms |
7728 KB |
Output is correct |
7 |
Correct |
898 ms |
7792 KB |
Output is correct |
8 |
Correct |
713 ms |
5568 KB |
Output is correct |
9 |
Correct |
734 ms |
5532 KB |
Output is correct |
10 |
Correct |
675 ms |
5416 KB |
Output is correct |
11 |
Correct |
1054 ms |
7148 KB |
Output is correct |
12 |
Correct |
1033 ms |
7068 KB |
Output is correct |
13 |
Correct |
1106 ms |
7132 KB |
Output is correct |
14 |
Correct |
798 ms |
7560 KB |
Output is correct |
15 |
Correct |
842 ms |
7592 KB |
Output is correct |
16 |
Correct |
1312 ms |
7680 KB |
Output is correct |
17 |
Correct |
1340 ms |
7668 KB |
Output is correct |
18 |
Correct |
1294 ms |
7836 KB |
Output is correct |
19 |
Correct |
1363 ms |
7732 KB |
Output is correct |
20 |
Correct |
1149 ms |
7256 KB |
Output is correct |
21 |
Correct |
1165 ms |
7356 KB |
Output is correct |
22 |
Correct |
1287 ms |
7508 KB |
Output is correct |
23 |
Correct |
837 ms |
7184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1397 ms |
5548 KB |
Output is correct |
2 |
Correct |
1428 ms |
5644 KB |
Output is correct |
3 |
Correct |
1457 ms |
7372 KB |
Output is correct |
4 |
Correct |
1534 ms |
7420 KB |
Output is correct |
5 |
Correct |
1493 ms |
7504 KB |
Output is correct |
6 |
Correct |
2142 ms |
7388 KB |
Output is correct |
7 |
Correct |
2129 ms |
7332 KB |
Output is correct |
8 |
Correct |
2128 ms |
7336 KB |
Output is correct |
9 |
Correct |
197 ms |
4340 KB |
Output is correct |
10 |
Correct |
1461 ms |
7288 KB |
Output is correct |
11 |
Correct |
1315 ms |
7068 KB |
Output is correct |
12 |
Correct |
1268 ms |
8004 KB |
Output is correct |
13 |
Correct |
1077 ms |
8316 KB |
Output is correct |
14 |
Correct |
1210 ms |
4604 KB |
Output is correct |
15 |
Correct |
1123 ms |
4232 KB |
Output is correct |
16 |
Correct |
1503 ms |
5600 KB |
Output is correct |
17 |
Correct |
1221 ms |
5928 KB |
Output is correct |
18 |
Correct |
199 ms |
3952 KB |
Output is correct |
19 |
Correct |
1357 ms |
6864 KB |
Output is correct |
20 |
Correct |
1138 ms |
6928 KB |
Output is correct |
21 |
Correct |
1008 ms |
6820 KB |
Output is correct |
22 |
Correct |
895 ms |
6900 KB |
Output is correct |
23 |
Correct |
838 ms |
6880 KB |
Output is correct |
24 |
Correct |
720 ms |
6744 KB |
Output is correct |
25 |
Correct |
599 ms |
6804 KB |
Output is correct |
26 |
Correct |
1413 ms |
8284 KB |
Output is correct |
27 |
Correct |
1798 ms |
8076 KB |
Output is correct |
28 |
Correct |
1493 ms |
8280 KB |
Output is correct |
29 |
Correct |
1065 ms |
8228 KB |
Output is correct |
30 |
Correct |
1702 ms |
8156 KB |
Output is correct |
31 |
Correct |
1766 ms |
8016 KB |
Output is correct |
32 |
Correct |
1726 ms |
7980 KB |
Output is correct |
33 |
Correct |
1442 ms |
8340 KB |
Output is correct |
34 |
Correct |
1496 ms |
8212 KB |
Output is correct |
35 |
Correct |
1496 ms |
8332 KB |
Output is correct |
36 |
Correct |
1123 ms |
8356 KB |
Output is correct |
37 |
Correct |
1115 ms |
8272 KB |
Output is correct |
38 |
Correct |
1065 ms |
8464 KB |
Output is correct |
39 |
Correct |
938 ms |
8232 KB |
Output is correct |
40 |
Correct |
932 ms |
8324 KB |
Output is correct |
41 |
Correct |
906 ms |
8244 KB |
Output is correct |
42 |
Correct |
719 ms |
8180 KB |
Output is correct |
43 |
Correct |
696 ms |
8092 KB |
Output is correct |
44 |
Correct |
711 ms |
8144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
58 ms |
840 KB |
Output is correct |
4 |
Correct |
19 ms |
776 KB |
Output is correct |
5 |
Correct |
64 ms |
776 KB |
Output is correct |
6 |
Correct |
49 ms |
788 KB |
Output is correct |
7 |
Correct |
58 ms |
712 KB |
Output is correct |
8 |
Correct |
66 ms |
724 KB |
Output is correct |
9 |
Correct |
63 ms |
732 KB |
Output is correct |
10 |
Correct |
63 ms |
724 KB |
Output is correct |
11 |
Correct |
65 ms |
776 KB |
Output is correct |
12 |
Correct |
79 ms |
912 KB |
Output is correct |
13 |
Correct |
74 ms |
776 KB |
Output is correct |
14 |
Correct |
69 ms |
812 KB |
Output is correct |
15 |
Correct |
73 ms |
800 KB |
Output is correct |
16 |
Correct |
68 ms |
712 KB |
Output is correct |
17 |
Correct |
74 ms |
724 KB |
Output is correct |
18 |
Correct |
1397 ms |
5548 KB |
Output is correct |
19 |
Correct |
1428 ms |
5644 KB |
Output is correct |
20 |
Correct |
1457 ms |
7372 KB |
Output is correct |
21 |
Correct |
1534 ms |
7420 KB |
Output is correct |
22 |
Correct |
1493 ms |
7504 KB |
Output is correct |
23 |
Correct |
2142 ms |
7388 KB |
Output is correct |
24 |
Correct |
2129 ms |
7332 KB |
Output is correct |
25 |
Correct |
2128 ms |
7336 KB |
Output is correct |
26 |
Correct |
197 ms |
4340 KB |
Output is correct |
27 |
Correct |
1461 ms |
7288 KB |
Output is correct |
28 |
Correct |
1315 ms |
7068 KB |
Output is correct |
29 |
Correct |
1268 ms |
8004 KB |
Output is correct |
30 |
Correct |
1077 ms |
8316 KB |
Output is correct |
31 |
Correct |
1210 ms |
4604 KB |
Output is correct |
32 |
Correct |
1123 ms |
4232 KB |
Output is correct |
33 |
Correct |
1503 ms |
5600 KB |
Output is correct |
34 |
Correct |
1221 ms |
5928 KB |
Output is correct |
35 |
Correct |
199 ms |
3952 KB |
Output is correct |
36 |
Correct |
1357 ms |
6864 KB |
Output is correct |
37 |
Correct |
1138 ms |
6928 KB |
Output is correct |
38 |
Correct |
1008 ms |
6820 KB |
Output is correct |
39 |
Correct |
895 ms |
6900 KB |
Output is correct |
40 |
Correct |
838 ms |
6880 KB |
Output is correct |
41 |
Correct |
720 ms |
6744 KB |
Output is correct |
42 |
Correct |
599 ms |
6804 KB |
Output is correct |
43 |
Correct |
1343 ms |
7852 KB |
Output is correct |
44 |
Correct |
194 ms |
3236 KB |
Output is correct |
45 |
Correct |
147 ms |
5004 KB |
Output is correct |
46 |
Correct |
106 ms |
4908 KB |
Output is correct |
47 |
Correct |
809 ms |
7620 KB |
Output is correct |
48 |
Correct |
1313 ms |
7728 KB |
Output is correct |
49 |
Correct |
898 ms |
7792 KB |
Output is correct |
50 |
Correct |
713 ms |
5568 KB |
Output is correct |
51 |
Correct |
734 ms |
5532 KB |
Output is correct |
52 |
Correct |
675 ms |
5416 KB |
Output is correct |
53 |
Correct |
1054 ms |
7148 KB |
Output is correct |
54 |
Correct |
1033 ms |
7068 KB |
Output is correct |
55 |
Correct |
1106 ms |
7132 KB |
Output is correct |
56 |
Correct |
798 ms |
7560 KB |
Output is correct |
57 |
Correct |
842 ms |
7592 KB |
Output is correct |
58 |
Correct |
1312 ms |
7680 KB |
Output is correct |
59 |
Correct |
1340 ms |
7668 KB |
Output is correct |
60 |
Correct |
1294 ms |
7836 KB |
Output is correct |
61 |
Correct |
1363 ms |
7732 KB |
Output is correct |
62 |
Correct |
1149 ms |
7256 KB |
Output is correct |
63 |
Correct |
1165 ms |
7356 KB |
Output is correct |
64 |
Correct |
1287 ms |
7508 KB |
Output is correct |
65 |
Correct |
837 ms |
7184 KB |
Output is correct |
66 |
Correct |
1413 ms |
8284 KB |
Output is correct |
67 |
Correct |
1798 ms |
8076 KB |
Output is correct |
68 |
Correct |
1493 ms |
8280 KB |
Output is correct |
69 |
Correct |
1065 ms |
8228 KB |
Output is correct |
70 |
Correct |
1702 ms |
8156 KB |
Output is correct |
71 |
Correct |
1766 ms |
8016 KB |
Output is correct |
72 |
Correct |
1726 ms |
7980 KB |
Output is correct |
73 |
Correct |
1442 ms |
8340 KB |
Output is correct |
74 |
Correct |
1496 ms |
8212 KB |
Output is correct |
75 |
Correct |
1496 ms |
8332 KB |
Output is correct |
76 |
Correct |
1123 ms |
8356 KB |
Output is correct |
77 |
Correct |
1115 ms |
8272 KB |
Output is correct |
78 |
Correct |
1065 ms |
8464 KB |
Output is correct |
79 |
Correct |
938 ms |
8232 KB |
Output is correct |
80 |
Correct |
932 ms |
8324 KB |
Output is correct |
81 |
Correct |
906 ms |
8244 KB |
Output is correct |
82 |
Correct |
719 ms |
8180 KB |
Output is correct |
83 |
Correct |
696 ms |
8092 KB |
Output is correct |
84 |
Correct |
711 ms |
8144 KB |
Output is correct |
85 |
Correct |
1982 ms |
10616 KB |
Output is correct |
86 |
Correct |
185 ms |
6816 KB |
Output is correct |
87 |
Correct |
136 ms |
6860 KB |
Output is correct |
88 |
Correct |
1384 ms |
9956 KB |
Output is correct |
89 |
Correct |
1875 ms |
10596 KB |
Output is correct |
90 |
Correct |
1401 ms |
9804 KB |
Output is correct |
91 |
Correct |
1505 ms |
8092 KB |
Output is correct |
92 |
Correct |
1482 ms |
8440 KB |
Output is correct |
93 |
Correct |
2175 ms |
8160 KB |
Output is correct |
94 |
Correct |
1677 ms |
10208 KB |
Output is correct |
95 |
Correct |
1691 ms |
10060 KB |
Output is correct |
96 |
Correct |
1844 ms |
10020 KB |
Output is correct |
97 |
Correct |
1094 ms |
10060 KB |
Output is correct |
98 |
Correct |
934 ms |
10012 KB |
Output is correct |
99 |
Correct |
1887 ms |
10668 KB |
Output is correct |
100 |
Correct |
1935 ms |
10648 KB |
Output is correct |
101 |
Correct |
1912 ms |
10680 KB |
Output is correct |
102 |
Correct |
1932 ms |
10680 KB |
Output is correct |
103 |
Correct |
2029 ms |
10608 KB |
Output is correct |
104 |
Correct |
2071 ms |
10292 KB |
Output is correct |
105 |
Correct |
1326 ms |
10268 KB |
Output is correct |
106 |
Correct |
1020 ms |
9968 KB |
Output is correct |
107 |
Correct |
1461 ms |
10328 KB |
Output is correct |
108 |
Correct |
1897 ms |
10720 KB |
Output is correct |
109 |
Correct |
1501 ms |
9108 KB |
Output is correct |