/* https://oj.uz/submission/124660 (Benq) */
#include <stdio.h>
#include <stdlib.h>
#define N 50000
#define M 100000
#define Q 100000
#define M_ (M + Q)
#define B 512
int min(int a, int b) { return a < b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ds[N], sz[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j, sz[j] += sz[i];
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, sz[i] += sz[j];
}
}
int *aa;
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[hh[j]] == aa[h])
j++;
else if (aa[hh[j]] > aa[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int *ej[N], eo[N], eo_[N];
void append(int i, int j) {
int o = eo[i]++;
if (o == eo_[i])
ej[i] = (int *) realloc(ej[i], (eo_[i] *= 2) * sizeof *ej[i]);
ej[i][o] = j;
}
char visited[N]; int qu[N], cnt, n;
int ii[M_], jj[M_], ww[M_], ll[M_], rr[M_], hh[M_], m;
int ii_[Q], ww_[Q], hh_[Q], ans[Q], sum;
void dfs(int i) {
int o;
if (visited[i])
return;
visited[i] = 1;
qu[cnt++] = i;
sum += sz[i];
for (o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
}
}
void solve(int l, int r) {
static int hh1[B * 2];
int m_, g, g_, g1, i, j;
sort(hh_, l, r + 1);
for (i = 0; i < n; i++)
ds[i] = -1, sz[i] = 1;
m_ = 0;
for (g = l, g_ = 0; g <= r && ww_[hh_[g]]; g++) {
int h = hh_[g], h_;
while (g_ < m && ww[hh[g_]] >= ww_[h]) {
h_ = hh[g_++];
if (ll[h_] <= l && r <= rr[h_])
join(ii[h_], jj[h_]);
else if (rr[h_] >= l && r >= ll[h_])
hh1[m_++] = h_;
}
for (g1 = 0; g1 < m_; g1++) {
h_ = hh1[g1];
if (ll[h_] <= h && h <= rr[h_]) {
i = find(ii[h_]), j = find(jj[h_]);
append(i, j), append(j, i);
}
}
cnt = 0, sum = 0, dfs(find(ii_[h]));
while (cnt--)
visited[qu[cnt]] = 0;
ans[h] = sum;
for (g1 = 0; g1 < m_; g1++) {
h_ = hh1[g1];
if (ll[h_] <= h && h <= rr[h_]) {
i = find(ii[h_]), j = find(jj[h_]);
eo[i] = eo[j] = 0;
}
}
}
}
int main() {
int m_, q, g, h, i;
scanf("%d%d", &n, &m);
for (h = 0; h < m; h++) {
scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
hh[h] = h;
}
scanf("%d", &q);
m_ = m;
for (h = 0; h < q; h++) {
int t;
scanf("%d", &t);
if (t == 1) {
int h_, w;
scanf("%d%d", &h_, &w), h_--;
ii_[h] = -1;
rr[hh[h_]] = h - 1;
ii[m_] = ii[h_], jj[m_] = jj[h_], ww[m_] = w, ll[m_] = h, hh[h_] = m_++;
} else
scanf("%d%d", &ii_[h], &ww_[h]), ii_[h]--;
}
for (h = 0; h < m; h++)
rr[hh[h]] = q - 1;
m = m_;
for (h = 0; h < m; h++)
hh[h] = h;
aa = ww, sort(hh, 0, m);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc((eo_[i] = 2) * sizeof *ej[i]);
for (h = 0; h < q; h++)
hh_[h] = h;
aa = ww_;
for (g = 0; g * B < q; g++)
solve(g * B, min((g + 1) * B, q) - 1);
for (h = 0; h < q; h++)
if (ww_[h])
printf("%d\n", ans[h]);
return 0;
}
Compilation message
bridges.c: In function 'main':
bridges.c:131:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
131 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
bridges.c:133:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
133 | scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:136:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
136 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
bridges.c:141:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
141 | scanf("%d", &t);
| ^~~~~~~~~~~~~~~
bridges.c:145:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%d%d", &h_, &w), h_--;
| ^~~~~~~~~~~~~~~~~~~~~~
bridges.c:150:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
150 | scanf("%d%d", &ii_[h], &ww_[h]), ii_[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
42 ms |
748 KB |
Output is correct |
4 |
Correct |
6 ms |
492 KB |
Output is correct |
5 |
Correct |
28 ms |
748 KB |
Output is correct |
6 |
Correct |
20 ms |
748 KB |
Output is correct |
7 |
Correct |
24 ms |
748 KB |
Output is correct |
8 |
Correct |
22 ms |
768 KB |
Output is correct |
9 |
Correct |
40 ms |
748 KB |
Output is correct |
10 |
Correct |
23 ms |
620 KB |
Output is correct |
11 |
Correct |
22 ms |
620 KB |
Output is correct |
12 |
Correct |
26 ms |
620 KB |
Output is correct |
13 |
Correct |
32 ms |
748 KB |
Output is correct |
14 |
Correct |
27 ms |
768 KB |
Output is correct |
15 |
Correct |
27 ms |
748 KB |
Output is correct |
16 |
Correct |
24 ms |
748 KB |
Output is correct |
17 |
Correct |
23 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1373 ms |
7108 KB |
Output is correct |
2 |
Correct |
1402 ms |
7020 KB |
Output is correct |
3 |
Correct |
1394 ms |
7020 KB |
Output is correct |
4 |
Correct |
1410 ms |
7020 KB |
Output is correct |
5 |
Correct |
1419 ms |
7124 KB |
Output is correct |
6 |
Correct |
2170 ms |
7100 KB |
Output is correct |
7 |
Correct |
2039 ms |
7148 KB |
Output is correct |
8 |
Correct |
1992 ms |
7276 KB |
Output is correct |
9 |
Correct |
54 ms |
2156 KB |
Output is correct |
10 |
Correct |
1248 ms |
7200 KB |
Output is correct |
11 |
Correct |
1164 ms |
7532 KB |
Output is correct |
12 |
Correct |
922 ms |
6636 KB |
Output is correct |
13 |
Correct |
1389 ms |
7808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1122 ms |
5996 KB |
Output is correct |
2 |
Correct |
1016 ms |
3976 KB |
Output is correct |
3 |
Correct |
1408 ms |
5800 KB |
Output is correct |
4 |
Correct |
1154 ms |
5900 KB |
Output is correct |
5 |
Correct |
54 ms |
2156 KB |
Output is correct |
6 |
Correct |
1254 ms |
5740 KB |
Output is correct |
7 |
Correct |
1014 ms |
5740 KB |
Output is correct |
8 |
Correct |
897 ms |
5840 KB |
Output is correct |
9 |
Correct |
572 ms |
4972 KB |
Output is correct |
10 |
Correct |
504 ms |
4972 KB |
Output is correct |
11 |
Correct |
971 ms |
6792 KB |
Output is correct |
12 |
Correct |
836 ms |
6636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
904 ms |
6892 KB |
Output is correct |
2 |
Correct |
55 ms |
2156 KB |
Output is correct |
3 |
Correct |
99 ms |
2540 KB |
Output is correct |
4 |
Correct |
56 ms |
2540 KB |
Output is correct |
5 |
Correct |
667 ms |
7020 KB |
Output is correct |
6 |
Correct |
894 ms |
7092 KB |
Output is correct |
7 |
Correct |
654 ms |
7044 KB |
Output is correct |
8 |
Correct |
508 ms |
5740 KB |
Output is correct |
9 |
Correct |
496 ms |
5740 KB |
Output is correct |
10 |
Correct |
502 ms |
5884 KB |
Output is correct |
11 |
Correct |
866 ms |
6396 KB |
Output is correct |
12 |
Correct |
828 ms |
6440 KB |
Output is correct |
13 |
Correct |
866 ms |
6508 KB |
Output is correct |
14 |
Correct |
602 ms |
7020 KB |
Output is correct |
15 |
Correct |
624 ms |
7020 KB |
Output is correct |
16 |
Correct |
1024 ms |
6892 KB |
Output is correct |
17 |
Correct |
1034 ms |
6892 KB |
Output is correct |
18 |
Correct |
1016 ms |
7104 KB |
Output is correct |
19 |
Correct |
1034 ms |
6904 KB |
Output is correct |
20 |
Correct |
976 ms |
6764 KB |
Output is correct |
21 |
Correct |
995 ms |
6892 KB |
Output is correct |
22 |
Correct |
1006 ms |
7020 KB |
Output is correct |
23 |
Correct |
809 ms |
6584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1373 ms |
7108 KB |
Output is correct |
2 |
Correct |
1402 ms |
7020 KB |
Output is correct |
3 |
Correct |
1394 ms |
7020 KB |
Output is correct |
4 |
Correct |
1410 ms |
7020 KB |
Output is correct |
5 |
Correct |
1419 ms |
7124 KB |
Output is correct |
6 |
Correct |
2170 ms |
7100 KB |
Output is correct |
7 |
Correct |
2039 ms |
7148 KB |
Output is correct |
8 |
Correct |
1992 ms |
7276 KB |
Output is correct |
9 |
Correct |
54 ms |
2156 KB |
Output is correct |
10 |
Correct |
1248 ms |
7200 KB |
Output is correct |
11 |
Correct |
1164 ms |
7532 KB |
Output is correct |
12 |
Correct |
922 ms |
6636 KB |
Output is correct |
13 |
Correct |
1389 ms |
7808 KB |
Output is correct |
14 |
Correct |
1122 ms |
5996 KB |
Output is correct |
15 |
Correct |
1016 ms |
3976 KB |
Output is correct |
16 |
Correct |
1408 ms |
5800 KB |
Output is correct |
17 |
Correct |
1154 ms |
5900 KB |
Output is correct |
18 |
Correct |
54 ms |
2156 KB |
Output is correct |
19 |
Correct |
1254 ms |
5740 KB |
Output is correct |
20 |
Correct |
1014 ms |
5740 KB |
Output is correct |
21 |
Correct |
897 ms |
5840 KB |
Output is correct |
22 |
Correct |
572 ms |
4972 KB |
Output is correct |
23 |
Correct |
504 ms |
4972 KB |
Output is correct |
24 |
Correct |
971 ms |
6792 KB |
Output is correct |
25 |
Correct |
836 ms |
6636 KB |
Output is correct |
26 |
Correct |
1354 ms |
7092 KB |
Output is correct |
27 |
Correct |
1800 ms |
7544 KB |
Output is correct |
28 |
Correct |
1470 ms |
7404 KB |
Output is correct |
29 |
Correct |
1043 ms |
7312 KB |
Output is correct |
30 |
Correct |
1764 ms |
7260 KB |
Output is correct |
31 |
Correct |
1831 ms |
7184 KB |
Output is correct |
32 |
Correct |
1795 ms |
7276 KB |
Output is correct |
33 |
Correct |
1482 ms |
7172 KB |
Output is correct |
34 |
Correct |
1484 ms |
7276 KB |
Output is correct |
35 |
Correct |
1480 ms |
7152 KB |
Output is correct |
36 |
Correct |
1128 ms |
7164 KB |
Output is correct |
37 |
Correct |
1085 ms |
7020 KB |
Output is correct |
38 |
Correct |
1069 ms |
7020 KB |
Output is correct |
39 |
Correct |
670 ms |
6220 KB |
Output is correct |
40 |
Correct |
678 ms |
6132 KB |
Output is correct |
41 |
Correct |
660 ms |
6124 KB |
Output is correct |
42 |
Correct |
1008 ms |
7916 KB |
Output is correct |
43 |
Correct |
1028 ms |
7796 KB |
Output is correct |
44 |
Correct |
1047 ms |
7896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
42 ms |
748 KB |
Output is correct |
4 |
Correct |
6 ms |
492 KB |
Output is correct |
5 |
Correct |
28 ms |
748 KB |
Output is correct |
6 |
Correct |
20 ms |
748 KB |
Output is correct |
7 |
Correct |
24 ms |
748 KB |
Output is correct |
8 |
Correct |
22 ms |
768 KB |
Output is correct |
9 |
Correct |
40 ms |
748 KB |
Output is correct |
10 |
Correct |
23 ms |
620 KB |
Output is correct |
11 |
Correct |
22 ms |
620 KB |
Output is correct |
12 |
Correct |
26 ms |
620 KB |
Output is correct |
13 |
Correct |
32 ms |
748 KB |
Output is correct |
14 |
Correct |
27 ms |
768 KB |
Output is correct |
15 |
Correct |
27 ms |
748 KB |
Output is correct |
16 |
Correct |
24 ms |
748 KB |
Output is correct |
17 |
Correct |
23 ms |
748 KB |
Output is correct |
18 |
Correct |
1373 ms |
7108 KB |
Output is correct |
19 |
Correct |
1402 ms |
7020 KB |
Output is correct |
20 |
Correct |
1394 ms |
7020 KB |
Output is correct |
21 |
Correct |
1410 ms |
7020 KB |
Output is correct |
22 |
Correct |
1419 ms |
7124 KB |
Output is correct |
23 |
Correct |
2170 ms |
7100 KB |
Output is correct |
24 |
Correct |
2039 ms |
7148 KB |
Output is correct |
25 |
Correct |
1992 ms |
7276 KB |
Output is correct |
26 |
Correct |
54 ms |
2156 KB |
Output is correct |
27 |
Correct |
1248 ms |
7200 KB |
Output is correct |
28 |
Correct |
1164 ms |
7532 KB |
Output is correct |
29 |
Correct |
922 ms |
6636 KB |
Output is correct |
30 |
Correct |
1389 ms |
7808 KB |
Output is correct |
31 |
Correct |
1122 ms |
5996 KB |
Output is correct |
32 |
Correct |
1016 ms |
3976 KB |
Output is correct |
33 |
Correct |
1408 ms |
5800 KB |
Output is correct |
34 |
Correct |
1154 ms |
5900 KB |
Output is correct |
35 |
Correct |
54 ms |
2156 KB |
Output is correct |
36 |
Correct |
1254 ms |
5740 KB |
Output is correct |
37 |
Correct |
1014 ms |
5740 KB |
Output is correct |
38 |
Correct |
897 ms |
5840 KB |
Output is correct |
39 |
Correct |
572 ms |
4972 KB |
Output is correct |
40 |
Correct |
504 ms |
4972 KB |
Output is correct |
41 |
Correct |
971 ms |
6792 KB |
Output is correct |
42 |
Correct |
836 ms |
6636 KB |
Output is correct |
43 |
Correct |
904 ms |
6892 KB |
Output is correct |
44 |
Correct |
55 ms |
2156 KB |
Output is correct |
45 |
Correct |
99 ms |
2540 KB |
Output is correct |
46 |
Correct |
56 ms |
2540 KB |
Output is correct |
47 |
Correct |
667 ms |
7020 KB |
Output is correct |
48 |
Correct |
894 ms |
7092 KB |
Output is correct |
49 |
Correct |
654 ms |
7044 KB |
Output is correct |
50 |
Correct |
508 ms |
5740 KB |
Output is correct |
51 |
Correct |
496 ms |
5740 KB |
Output is correct |
52 |
Correct |
502 ms |
5884 KB |
Output is correct |
53 |
Correct |
866 ms |
6396 KB |
Output is correct |
54 |
Correct |
828 ms |
6440 KB |
Output is correct |
55 |
Correct |
866 ms |
6508 KB |
Output is correct |
56 |
Correct |
602 ms |
7020 KB |
Output is correct |
57 |
Correct |
624 ms |
7020 KB |
Output is correct |
58 |
Correct |
1024 ms |
6892 KB |
Output is correct |
59 |
Correct |
1034 ms |
6892 KB |
Output is correct |
60 |
Correct |
1016 ms |
7104 KB |
Output is correct |
61 |
Correct |
1034 ms |
6904 KB |
Output is correct |
62 |
Correct |
976 ms |
6764 KB |
Output is correct |
63 |
Correct |
995 ms |
6892 KB |
Output is correct |
64 |
Correct |
1006 ms |
7020 KB |
Output is correct |
65 |
Correct |
809 ms |
6584 KB |
Output is correct |
66 |
Correct |
1354 ms |
7092 KB |
Output is correct |
67 |
Correct |
1800 ms |
7544 KB |
Output is correct |
68 |
Correct |
1470 ms |
7404 KB |
Output is correct |
69 |
Correct |
1043 ms |
7312 KB |
Output is correct |
70 |
Correct |
1764 ms |
7260 KB |
Output is correct |
71 |
Correct |
1831 ms |
7184 KB |
Output is correct |
72 |
Correct |
1795 ms |
7276 KB |
Output is correct |
73 |
Correct |
1482 ms |
7172 KB |
Output is correct |
74 |
Correct |
1484 ms |
7276 KB |
Output is correct |
75 |
Correct |
1480 ms |
7152 KB |
Output is correct |
76 |
Correct |
1128 ms |
7164 KB |
Output is correct |
77 |
Correct |
1085 ms |
7020 KB |
Output is correct |
78 |
Correct |
1069 ms |
7020 KB |
Output is correct |
79 |
Correct |
670 ms |
6220 KB |
Output is correct |
80 |
Correct |
678 ms |
6132 KB |
Output is correct |
81 |
Correct |
660 ms |
6124 KB |
Output is correct |
82 |
Correct |
1008 ms |
7916 KB |
Output is correct |
83 |
Correct |
1028 ms |
7796 KB |
Output is correct |
84 |
Correct |
1047 ms |
7896 KB |
Output is correct |
85 |
Correct |
1933 ms |
8300 KB |
Output is correct |
86 |
Correct |
143 ms |
2796 KB |
Output is correct |
87 |
Correct |
119 ms |
2668 KB |
Output is correct |
88 |
Correct |
1446 ms |
8428 KB |
Output is correct |
89 |
Correct |
1852 ms |
8172 KB |
Output is correct |
90 |
Correct |
1422 ms |
8172 KB |
Output is correct |
91 |
Correct |
1488 ms |
7056 KB |
Output is correct |
92 |
Correct |
1452 ms |
7160 KB |
Output is correct |
93 |
Correct |
1998 ms |
7056 KB |
Output is correct |
94 |
Correct |
1899 ms |
7908 KB |
Output is correct |
95 |
Correct |
1869 ms |
7920 KB |
Output is correct |
96 |
Correct |
2269 ms |
8044 KB |
Output is correct |
97 |
Correct |
1033 ms |
7484 KB |
Output is correct |
98 |
Correct |
1303 ms |
9196 KB |
Output is correct |
99 |
Correct |
2080 ms |
8300 KB |
Output is correct |
100 |
Correct |
2057 ms |
8156 KB |
Output is correct |
101 |
Correct |
2013 ms |
8212 KB |
Output is correct |
102 |
Correct |
2064 ms |
8192 KB |
Output is correct |
103 |
Correct |
2303 ms |
8184 KB |
Output is correct |
104 |
Correct |
2303 ms |
8172 KB |
Output is correct |
105 |
Correct |
1927 ms |
9228 KB |
Output is correct |
106 |
Correct |
1642 ms |
9380 KB |
Output is correct |
107 |
Correct |
1351 ms |
7120 KB |
Output is correct |
108 |
Correct |
2242 ms |
8168 KB |
Output is correct |
109 |
Correct |
2051 ms |
7600 KB |
Output is correct |