#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#define N 50000
#define M 100000
#define Q 100000
#define B 1000
unsigned int X;
void srand_() {
struct timeval tv;
gettimeofday(&tv, NULL);
X = tv.tv_sec ^ tv.tv_usec | 1;
}
int rand_() {
return (X *= 3) >> 1;
}
int *aa;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = aa[i_] - aa[ii[j]];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
struct R {
int i, j, i_ds, j_ds;
} rr[N];
int ds[N], r_cnt;
int find(int i) {
return ds[i] < 0 ? i : find(ds[i]);
}
int join(int i, int j, int r) {
int k;
i = find(i), j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
k = i, i = j, j = k;
if (r)
rr[r_cnt].i = i, rr[r_cnt].j = j, rr[r_cnt].i_ds = ds[i], rr[r_cnt].j_ds = ds[j], r_cnt++;
ds[i] += ds[j], ds[j] = i;
return 1;
}
int main() {
int n, m, q, h, i, j, k, u_cnt, q_cnt;
static int hh[M], ii[M], jj[M], ww[M], ww_[M], changed[M];
static int q_ii[Q], q_ww[Q], uu[Q], qq[Q], ans[Q];
srand_();
r_cnt = u_cnt = q_cnt = 0;
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);
for (h = 0; h < q; h++) {
int t;
scanf("%d%d%d", &t, &q_ii[h], &q_ww[h]), q_ii[h]--;
if (t == 1)
uu[u_cnt++] = h;
else
qq[q_cnt++] = h;
if ((h + 1) % B == 0 || h + 1 == q) {
aa = ww, sort(hh, 0, m);
aa = q_ww, sort(qq, 0, q_cnt);
memset(ds, -1, n * sizeof *ds);
memset(changed, 0, m * sizeof *changed);
for (i = 0; i < u_cnt; i++)
changed[q_ii[uu[i]]] = 1;
j = 0;
for (i = 0; i < q_cnt; i++) {
while (j < m && ww[hh[j]] >= q_ww[qq[i]]) {
if (changed[hh[j]] == 0)
join(ii[hh[j]], jj[hh[j]], 0);
j++;
}
for (k = 0; k < u_cnt; k++)
ww_[q_ii[uu[k]]] = ww[q_ii[uu[k]]];
for (k = 0; k < u_cnt; k++)
if (uu[k] < qq[i])
ww_[q_ii[uu[k]]] = q_ww[uu[k]];
for (k = 0; k < u_cnt; k++)
if (ww_[q_ii[uu[k]]] >= q_ww[qq[i]])
join(ii[q_ii[uu[k]]], jj[q_ii[uu[k]]], 1);
ans[qq[i]] = -ds[find(q_ii[qq[i]])];
while (r_cnt > 0) {
r_cnt--;
ds[rr[r_cnt].i] = rr[r_cnt].i_ds;
ds[rr[r_cnt].j] = rr[r_cnt].j_ds;
}
}
for (i = 0; i < u_cnt; i++)
ww[q_ii[uu[i]]] = q_ww[uu[i]];
u_cnt = 0;
q_cnt = 0;
}
}
for (h = 0; h < q; h++)
if (ans[h] > 0)
printf("%d\n", ans[h]);
return 0;
}
Compilation message
bridges.c: In function 'srand_':
bridges.c:16:16: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
16 | X = tv.tv_sec ^ tv.tv_usec | 1;
| ~~~~~~~~~~^~~~~~~~~~~~
bridges.c: In function 'main':
bridges.c:78:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
bridges.c:80:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
bridges.c:87:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d%d%d", &t, &q_ii[h], &q_ww[h]), q_ii[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
288 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
43 ms |
572 KB |
Output is correct |
4 |
Correct |
4 ms |
588 KB |
Output is correct |
5 |
Correct |
45 ms |
548 KB |
Output is correct |
6 |
Correct |
39 ms |
540 KB |
Output is correct |
7 |
Correct |
43 ms |
464 KB |
Output is correct |
8 |
Correct |
51 ms |
536 KB |
Output is correct |
9 |
Correct |
48 ms |
496 KB |
Output is correct |
10 |
Correct |
46 ms |
564 KB |
Output is correct |
11 |
Correct |
48 ms |
548 KB |
Output is correct |
12 |
Correct |
55 ms |
580 KB |
Output is correct |
13 |
Correct |
54 ms |
588 KB |
Output is correct |
14 |
Correct |
52 ms |
580 KB |
Output is correct |
15 |
Correct |
58 ms |
580 KB |
Output is correct |
16 |
Correct |
49 ms |
516 KB |
Output is correct |
17 |
Correct |
49 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1268 ms |
5696 KB |
Output is correct |
2 |
Correct |
1230 ms |
5592 KB |
Output is correct |
3 |
Correct |
1233 ms |
5624 KB |
Output is correct |
4 |
Correct |
1291 ms |
5756 KB |
Output is correct |
5 |
Correct |
1276 ms |
5684 KB |
Output is correct |
6 |
Correct |
1814 ms |
5652 KB |
Output is correct |
7 |
Correct |
1814 ms |
5740 KB |
Output is correct |
8 |
Correct |
1810 ms |
5644 KB |
Output is correct |
9 |
Correct |
50 ms |
3140 KB |
Output is correct |
10 |
Correct |
988 ms |
4588 KB |
Output is correct |
11 |
Correct |
928 ms |
4628 KB |
Output is correct |
12 |
Correct |
975 ms |
5800 KB |
Output is correct |
13 |
Correct |
1018 ms |
5608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
990 ms |
4848 KB |
Output is correct |
2 |
Correct |
857 ms |
3488 KB |
Output is correct |
3 |
Correct |
1209 ms |
4808 KB |
Output is correct |
4 |
Correct |
969 ms |
4888 KB |
Output is correct |
5 |
Correct |
41 ms |
2980 KB |
Output is correct |
6 |
Correct |
1089 ms |
4780 KB |
Output is correct |
7 |
Correct |
977 ms |
4816 KB |
Output is correct |
8 |
Correct |
835 ms |
4696 KB |
Output is correct |
9 |
Correct |
601 ms |
4868 KB |
Output is correct |
10 |
Correct |
576 ms |
4864 KB |
Output is correct |
11 |
Correct |
655 ms |
4672 KB |
Output is correct |
12 |
Correct |
584 ms |
4672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1161 ms |
7760 KB |
Output is correct |
2 |
Correct |
41 ms |
3012 KB |
Output is correct |
3 |
Correct |
134 ms |
4220 KB |
Output is correct |
4 |
Correct |
53 ms |
4260 KB |
Output is correct |
5 |
Correct |
369 ms |
6384 KB |
Output is correct |
6 |
Correct |
1265 ms |
7868 KB |
Output is correct |
7 |
Correct |
395 ms |
6292 KB |
Output is correct |
8 |
Correct |
532 ms |
5572 KB |
Output is correct |
9 |
Correct |
520 ms |
5652 KB |
Output is correct |
10 |
Correct |
558 ms |
5440 KB |
Output is correct |
11 |
Correct |
877 ms |
6484 KB |
Output is correct |
12 |
Correct |
872 ms |
6796 KB |
Output is correct |
13 |
Correct |
855 ms |
6616 KB |
Output is correct |
14 |
Correct |
379 ms |
6416 KB |
Output is correct |
15 |
Correct |
353 ms |
6352 KB |
Output is correct |
16 |
Correct |
1192 ms |
7708 KB |
Output is correct |
17 |
Correct |
1195 ms |
7756 KB |
Output is correct |
18 |
Correct |
1282 ms |
7748 KB |
Output is correct |
19 |
Correct |
1226 ms |
7968 KB |
Output is correct |
20 |
Correct |
965 ms |
7020 KB |
Output is correct |
21 |
Correct |
1002 ms |
6920 KB |
Output is correct |
22 |
Correct |
1187 ms |
7720 KB |
Output is correct |
23 |
Correct |
510 ms |
5784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1268 ms |
5696 KB |
Output is correct |
2 |
Correct |
1230 ms |
5592 KB |
Output is correct |
3 |
Correct |
1233 ms |
5624 KB |
Output is correct |
4 |
Correct |
1291 ms |
5756 KB |
Output is correct |
5 |
Correct |
1276 ms |
5684 KB |
Output is correct |
6 |
Correct |
1814 ms |
5652 KB |
Output is correct |
7 |
Correct |
1814 ms |
5740 KB |
Output is correct |
8 |
Correct |
1810 ms |
5644 KB |
Output is correct |
9 |
Correct |
50 ms |
3140 KB |
Output is correct |
10 |
Correct |
988 ms |
4588 KB |
Output is correct |
11 |
Correct |
928 ms |
4628 KB |
Output is correct |
12 |
Correct |
975 ms |
5800 KB |
Output is correct |
13 |
Correct |
1018 ms |
5608 KB |
Output is correct |
14 |
Correct |
990 ms |
4848 KB |
Output is correct |
15 |
Correct |
857 ms |
3488 KB |
Output is correct |
16 |
Correct |
1209 ms |
4808 KB |
Output is correct |
17 |
Correct |
969 ms |
4888 KB |
Output is correct |
18 |
Correct |
41 ms |
2980 KB |
Output is correct |
19 |
Correct |
1089 ms |
4780 KB |
Output is correct |
20 |
Correct |
977 ms |
4816 KB |
Output is correct |
21 |
Correct |
835 ms |
4696 KB |
Output is correct |
22 |
Correct |
601 ms |
4868 KB |
Output is correct |
23 |
Correct |
576 ms |
4864 KB |
Output is correct |
24 |
Correct |
655 ms |
4672 KB |
Output is correct |
25 |
Correct |
584 ms |
4672 KB |
Output is correct |
26 |
Correct |
1187 ms |
5732 KB |
Output is correct |
27 |
Correct |
1525 ms |
5520 KB |
Output is correct |
28 |
Correct |
1221 ms |
5732 KB |
Output is correct |
29 |
Correct |
1004 ms |
5684 KB |
Output is correct |
30 |
Correct |
1443 ms |
5588 KB |
Output is correct |
31 |
Correct |
1491 ms |
5504 KB |
Output is correct |
32 |
Correct |
1480 ms |
5664 KB |
Output is correct |
33 |
Correct |
1239 ms |
5724 KB |
Output is correct |
34 |
Correct |
1231 ms |
5692 KB |
Output is correct |
35 |
Correct |
1329 ms |
5640 KB |
Output is correct |
36 |
Correct |
977 ms |
5776 KB |
Output is correct |
37 |
Correct |
1046 ms |
5608 KB |
Output is correct |
38 |
Correct |
996 ms |
5800 KB |
Output is correct |
39 |
Correct |
700 ms |
5800 KB |
Output is correct |
40 |
Correct |
707 ms |
5728 KB |
Output is correct |
41 |
Correct |
691 ms |
5744 KB |
Output is correct |
42 |
Correct |
830 ms |
5576 KB |
Output is correct |
43 |
Correct |
724 ms |
5556 KB |
Output is correct |
44 |
Correct |
709 ms |
5640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
288 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
43 ms |
572 KB |
Output is correct |
4 |
Correct |
4 ms |
588 KB |
Output is correct |
5 |
Correct |
45 ms |
548 KB |
Output is correct |
6 |
Correct |
39 ms |
540 KB |
Output is correct |
7 |
Correct |
43 ms |
464 KB |
Output is correct |
8 |
Correct |
51 ms |
536 KB |
Output is correct |
9 |
Correct |
48 ms |
496 KB |
Output is correct |
10 |
Correct |
46 ms |
564 KB |
Output is correct |
11 |
Correct |
48 ms |
548 KB |
Output is correct |
12 |
Correct |
55 ms |
580 KB |
Output is correct |
13 |
Correct |
54 ms |
588 KB |
Output is correct |
14 |
Correct |
52 ms |
580 KB |
Output is correct |
15 |
Correct |
58 ms |
580 KB |
Output is correct |
16 |
Correct |
49 ms |
516 KB |
Output is correct |
17 |
Correct |
49 ms |
468 KB |
Output is correct |
18 |
Correct |
1268 ms |
5696 KB |
Output is correct |
19 |
Correct |
1230 ms |
5592 KB |
Output is correct |
20 |
Correct |
1233 ms |
5624 KB |
Output is correct |
21 |
Correct |
1291 ms |
5756 KB |
Output is correct |
22 |
Correct |
1276 ms |
5684 KB |
Output is correct |
23 |
Correct |
1814 ms |
5652 KB |
Output is correct |
24 |
Correct |
1814 ms |
5740 KB |
Output is correct |
25 |
Correct |
1810 ms |
5644 KB |
Output is correct |
26 |
Correct |
50 ms |
3140 KB |
Output is correct |
27 |
Correct |
988 ms |
4588 KB |
Output is correct |
28 |
Correct |
928 ms |
4628 KB |
Output is correct |
29 |
Correct |
975 ms |
5800 KB |
Output is correct |
30 |
Correct |
1018 ms |
5608 KB |
Output is correct |
31 |
Correct |
990 ms |
4848 KB |
Output is correct |
32 |
Correct |
857 ms |
3488 KB |
Output is correct |
33 |
Correct |
1209 ms |
4808 KB |
Output is correct |
34 |
Correct |
969 ms |
4888 KB |
Output is correct |
35 |
Correct |
41 ms |
2980 KB |
Output is correct |
36 |
Correct |
1089 ms |
4780 KB |
Output is correct |
37 |
Correct |
977 ms |
4816 KB |
Output is correct |
38 |
Correct |
835 ms |
4696 KB |
Output is correct |
39 |
Correct |
601 ms |
4868 KB |
Output is correct |
40 |
Correct |
576 ms |
4864 KB |
Output is correct |
41 |
Correct |
655 ms |
4672 KB |
Output is correct |
42 |
Correct |
584 ms |
4672 KB |
Output is correct |
43 |
Correct |
1161 ms |
7760 KB |
Output is correct |
44 |
Correct |
41 ms |
3012 KB |
Output is correct |
45 |
Correct |
134 ms |
4220 KB |
Output is correct |
46 |
Correct |
53 ms |
4260 KB |
Output is correct |
47 |
Correct |
369 ms |
6384 KB |
Output is correct |
48 |
Correct |
1265 ms |
7868 KB |
Output is correct |
49 |
Correct |
395 ms |
6292 KB |
Output is correct |
50 |
Correct |
532 ms |
5572 KB |
Output is correct |
51 |
Correct |
520 ms |
5652 KB |
Output is correct |
52 |
Correct |
558 ms |
5440 KB |
Output is correct |
53 |
Correct |
877 ms |
6484 KB |
Output is correct |
54 |
Correct |
872 ms |
6796 KB |
Output is correct |
55 |
Correct |
855 ms |
6616 KB |
Output is correct |
56 |
Correct |
379 ms |
6416 KB |
Output is correct |
57 |
Correct |
353 ms |
6352 KB |
Output is correct |
58 |
Correct |
1192 ms |
7708 KB |
Output is correct |
59 |
Correct |
1195 ms |
7756 KB |
Output is correct |
60 |
Correct |
1282 ms |
7748 KB |
Output is correct |
61 |
Correct |
1226 ms |
7968 KB |
Output is correct |
62 |
Correct |
965 ms |
7020 KB |
Output is correct |
63 |
Correct |
1002 ms |
6920 KB |
Output is correct |
64 |
Correct |
1187 ms |
7720 KB |
Output is correct |
65 |
Correct |
510 ms |
5784 KB |
Output is correct |
66 |
Correct |
1187 ms |
5732 KB |
Output is correct |
67 |
Correct |
1525 ms |
5520 KB |
Output is correct |
68 |
Correct |
1221 ms |
5732 KB |
Output is correct |
69 |
Correct |
1004 ms |
5684 KB |
Output is correct |
70 |
Correct |
1443 ms |
5588 KB |
Output is correct |
71 |
Correct |
1491 ms |
5504 KB |
Output is correct |
72 |
Correct |
1480 ms |
5664 KB |
Output is correct |
73 |
Correct |
1239 ms |
5724 KB |
Output is correct |
74 |
Correct |
1231 ms |
5692 KB |
Output is correct |
75 |
Correct |
1329 ms |
5640 KB |
Output is correct |
76 |
Correct |
977 ms |
5776 KB |
Output is correct |
77 |
Correct |
1046 ms |
5608 KB |
Output is correct |
78 |
Correct |
996 ms |
5800 KB |
Output is correct |
79 |
Correct |
700 ms |
5800 KB |
Output is correct |
80 |
Correct |
707 ms |
5728 KB |
Output is correct |
81 |
Correct |
691 ms |
5744 KB |
Output is correct |
82 |
Correct |
830 ms |
5576 KB |
Output is correct |
83 |
Correct |
724 ms |
5556 KB |
Output is correct |
84 |
Correct |
709 ms |
5640 KB |
Output is correct |
85 |
Correct |
1735 ms |
8072 KB |
Output is correct |
86 |
Correct |
175 ms |
4616 KB |
Output is correct |
87 |
Correct |
103 ms |
4672 KB |
Output is correct |
88 |
Correct |
958 ms |
6604 KB |
Output is correct |
89 |
Correct |
1727 ms |
8048 KB |
Output is correct |
90 |
Correct |
936 ms |
6316 KB |
Output is correct |
91 |
Correct |
1333 ms |
5712 KB |
Output is correct |
92 |
Correct |
1249 ms |
5648 KB |
Output is correct |
93 |
Correct |
1795 ms |
5596 KB |
Output is correct |
94 |
Correct |
1553 ms |
6748 KB |
Output is correct |
95 |
Correct |
1565 ms |
6760 KB |
Output is correct |
96 |
Correct |
1767 ms |
6732 KB |
Output is correct |
97 |
Correct |
586 ms |
6480 KB |
Output is correct |
98 |
Correct |
638 ms |
6036 KB |
Output is correct |
99 |
Correct |
1741 ms |
7960 KB |
Output is correct |
100 |
Correct |
1745 ms |
7920 KB |
Output is correct |
101 |
Correct |
1791 ms |
8028 KB |
Output is correct |
102 |
Correct |
1752 ms |
7944 KB |
Output is correct |
103 |
Correct |
1895 ms |
6944 KB |
Output is correct |
104 |
Correct |
1892 ms |
6952 KB |
Output is correct |
105 |
Correct |
1318 ms |
6996 KB |
Output is correct |
106 |
Correct |
1039 ms |
6672 KB |
Output is correct |
107 |
Correct |
1196 ms |
7224 KB |
Output is correct |
108 |
Correct |
1734 ms |
7652 KB |
Output is correct |
109 |
Correct |
1134 ms |
5952 KB |
Output is correct |