#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#define N 50000
#define M 100000
#define Q 100000
#define B 750
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 |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
34 ms |
592 KB |
Output is correct |
4 |
Correct |
4 ms |
556 KB |
Output is correct |
5 |
Correct |
35 ms |
544 KB |
Output is correct |
6 |
Correct |
28 ms |
600 KB |
Output is correct |
7 |
Correct |
32 ms |
460 KB |
Output is correct |
8 |
Correct |
35 ms |
572 KB |
Output is correct |
9 |
Correct |
36 ms |
492 KB |
Output is correct |
10 |
Correct |
35 ms |
584 KB |
Output is correct |
11 |
Correct |
36 ms |
592 KB |
Output is correct |
12 |
Correct |
40 ms |
572 KB |
Output is correct |
13 |
Correct |
40 ms |
568 KB |
Output is correct |
14 |
Correct |
39 ms |
620 KB |
Output is correct |
15 |
Correct |
41 ms |
568 KB |
Output is correct |
16 |
Correct |
35 ms |
492 KB |
Output is correct |
17 |
Correct |
36 ms |
432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1190 ms |
5740 KB |
Output is correct |
2 |
Correct |
1172 ms |
5616 KB |
Output is correct |
3 |
Correct |
1199 ms |
5720 KB |
Output is correct |
4 |
Correct |
1207 ms |
5828 KB |
Output is correct |
5 |
Correct |
1223 ms |
5708 KB |
Output is correct |
6 |
Correct |
1629 ms |
5604 KB |
Output is correct |
7 |
Correct |
1679 ms |
5660 KB |
Output is correct |
8 |
Correct |
1615 ms |
5688 KB |
Output is correct |
9 |
Correct |
40 ms |
2980 KB |
Output is correct |
10 |
Correct |
791 ms |
4616 KB |
Output is correct |
11 |
Correct |
757 ms |
4756 KB |
Output is correct |
12 |
Correct |
979 ms |
5956 KB |
Output is correct |
13 |
Correct |
1024 ms |
5584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
914 ms |
4968 KB |
Output is correct |
2 |
Correct |
690 ms |
3440 KB |
Output is correct |
3 |
Correct |
1065 ms |
4652 KB |
Output is correct |
4 |
Correct |
905 ms |
4940 KB |
Output is correct |
5 |
Correct |
40 ms |
3012 KB |
Output is correct |
6 |
Correct |
993 ms |
4924 KB |
Output is correct |
7 |
Correct |
863 ms |
4828 KB |
Output is correct |
8 |
Correct |
805 ms |
4804 KB |
Output is correct |
9 |
Correct |
615 ms |
4952 KB |
Output is correct |
10 |
Correct |
576 ms |
4920 KB |
Output is correct |
11 |
Correct |
660 ms |
4708 KB |
Output is correct |
12 |
Correct |
618 ms |
4636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1474 ms |
7776 KB |
Output is correct |
2 |
Correct |
40 ms |
2916 KB |
Output is correct |
3 |
Correct |
167 ms |
4156 KB |
Output is correct |
4 |
Correct |
60 ms |
4264 KB |
Output is correct |
5 |
Correct |
468 ms |
6292 KB |
Output is correct |
6 |
Correct |
1499 ms |
7908 KB |
Output is correct |
7 |
Correct |
485 ms |
6388 KB |
Output is correct |
8 |
Correct |
682 ms |
5532 KB |
Output is correct |
9 |
Correct |
670 ms |
5568 KB |
Output is correct |
10 |
Correct |
692 ms |
5536 KB |
Output is correct |
11 |
Correct |
1114 ms |
6644 KB |
Output is correct |
12 |
Correct |
1053 ms |
6692 KB |
Output is correct |
13 |
Correct |
1113 ms |
6780 KB |
Output is correct |
14 |
Correct |
448 ms |
6352 KB |
Output is correct |
15 |
Correct |
448 ms |
6372 KB |
Output is correct |
16 |
Correct |
1469 ms |
7892 KB |
Output is correct |
17 |
Correct |
1523 ms |
7728 KB |
Output is correct |
18 |
Correct |
1461 ms |
7816 KB |
Output is correct |
19 |
Correct |
1449 ms |
7752 KB |
Output is correct |
20 |
Correct |
1268 ms |
6968 KB |
Output is correct |
21 |
Correct |
1235 ms |
6972 KB |
Output is correct |
22 |
Correct |
1415 ms |
7964 KB |
Output is correct |
23 |
Correct |
576 ms |
5792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1190 ms |
5740 KB |
Output is correct |
2 |
Correct |
1172 ms |
5616 KB |
Output is correct |
3 |
Correct |
1199 ms |
5720 KB |
Output is correct |
4 |
Correct |
1207 ms |
5828 KB |
Output is correct |
5 |
Correct |
1223 ms |
5708 KB |
Output is correct |
6 |
Correct |
1629 ms |
5604 KB |
Output is correct |
7 |
Correct |
1679 ms |
5660 KB |
Output is correct |
8 |
Correct |
1615 ms |
5688 KB |
Output is correct |
9 |
Correct |
40 ms |
2980 KB |
Output is correct |
10 |
Correct |
791 ms |
4616 KB |
Output is correct |
11 |
Correct |
757 ms |
4756 KB |
Output is correct |
12 |
Correct |
979 ms |
5956 KB |
Output is correct |
13 |
Correct |
1024 ms |
5584 KB |
Output is correct |
14 |
Correct |
914 ms |
4968 KB |
Output is correct |
15 |
Correct |
690 ms |
3440 KB |
Output is correct |
16 |
Correct |
1065 ms |
4652 KB |
Output is correct |
17 |
Correct |
905 ms |
4940 KB |
Output is correct |
18 |
Correct |
40 ms |
3012 KB |
Output is correct |
19 |
Correct |
993 ms |
4924 KB |
Output is correct |
20 |
Correct |
863 ms |
4828 KB |
Output is correct |
21 |
Correct |
805 ms |
4804 KB |
Output is correct |
22 |
Correct |
615 ms |
4952 KB |
Output is correct |
23 |
Correct |
576 ms |
4920 KB |
Output is correct |
24 |
Correct |
660 ms |
4708 KB |
Output is correct |
25 |
Correct |
618 ms |
4636 KB |
Output is correct |
26 |
Correct |
1158 ms |
5696 KB |
Output is correct |
27 |
Correct |
1413 ms |
5504 KB |
Output is correct |
28 |
Correct |
1226 ms |
5736 KB |
Output is correct |
29 |
Correct |
1028 ms |
5708 KB |
Output is correct |
30 |
Correct |
1365 ms |
5588 KB |
Output is correct |
31 |
Correct |
1366 ms |
5592 KB |
Output is correct |
32 |
Correct |
1372 ms |
5596 KB |
Output is correct |
33 |
Correct |
1202 ms |
5756 KB |
Output is correct |
34 |
Correct |
1199 ms |
5636 KB |
Output is correct |
35 |
Correct |
1221 ms |
5724 KB |
Output is correct |
36 |
Correct |
1020 ms |
5660 KB |
Output is correct |
37 |
Correct |
1016 ms |
5700 KB |
Output is correct |
38 |
Correct |
1004 ms |
5640 KB |
Output is correct |
39 |
Correct |
798 ms |
5820 KB |
Output is correct |
40 |
Correct |
795 ms |
5788 KB |
Output is correct |
41 |
Correct |
811 ms |
5676 KB |
Output is correct |
42 |
Correct |
825 ms |
5560 KB |
Output is correct |
43 |
Correct |
814 ms |
5572 KB |
Output is correct |
44 |
Correct |
820 ms |
5528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
34 ms |
592 KB |
Output is correct |
4 |
Correct |
4 ms |
556 KB |
Output is correct |
5 |
Correct |
35 ms |
544 KB |
Output is correct |
6 |
Correct |
28 ms |
600 KB |
Output is correct |
7 |
Correct |
32 ms |
460 KB |
Output is correct |
8 |
Correct |
35 ms |
572 KB |
Output is correct |
9 |
Correct |
36 ms |
492 KB |
Output is correct |
10 |
Correct |
35 ms |
584 KB |
Output is correct |
11 |
Correct |
36 ms |
592 KB |
Output is correct |
12 |
Correct |
40 ms |
572 KB |
Output is correct |
13 |
Correct |
40 ms |
568 KB |
Output is correct |
14 |
Correct |
39 ms |
620 KB |
Output is correct |
15 |
Correct |
41 ms |
568 KB |
Output is correct |
16 |
Correct |
35 ms |
492 KB |
Output is correct |
17 |
Correct |
36 ms |
432 KB |
Output is correct |
18 |
Correct |
1190 ms |
5740 KB |
Output is correct |
19 |
Correct |
1172 ms |
5616 KB |
Output is correct |
20 |
Correct |
1199 ms |
5720 KB |
Output is correct |
21 |
Correct |
1207 ms |
5828 KB |
Output is correct |
22 |
Correct |
1223 ms |
5708 KB |
Output is correct |
23 |
Correct |
1629 ms |
5604 KB |
Output is correct |
24 |
Correct |
1679 ms |
5660 KB |
Output is correct |
25 |
Correct |
1615 ms |
5688 KB |
Output is correct |
26 |
Correct |
40 ms |
2980 KB |
Output is correct |
27 |
Correct |
791 ms |
4616 KB |
Output is correct |
28 |
Correct |
757 ms |
4756 KB |
Output is correct |
29 |
Correct |
979 ms |
5956 KB |
Output is correct |
30 |
Correct |
1024 ms |
5584 KB |
Output is correct |
31 |
Correct |
914 ms |
4968 KB |
Output is correct |
32 |
Correct |
690 ms |
3440 KB |
Output is correct |
33 |
Correct |
1065 ms |
4652 KB |
Output is correct |
34 |
Correct |
905 ms |
4940 KB |
Output is correct |
35 |
Correct |
40 ms |
3012 KB |
Output is correct |
36 |
Correct |
993 ms |
4924 KB |
Output is correct |
37 |
Correct |
863 ms |
4828 KB |
Output is correct |
38 |
Correct |
805 ms |
4804 KB |
Output is correct |
39 |
Correct |
615 ms |
4952 KB |
Output is correct |
40 |
Correct |
576 ms |
4920 KB |
Output is correct |
41 |
Correct |
660 ms |
4708 KB |
Output is correct |
42 |
Correct |
618 ms |
4636 KB |
Output is correct |
43 |
Correct |
1474 ms |
7776 KB |
Output is correct |
44 |
Correct |
40 ms |
2916 KB |
Output is correct |
45 |
Correct |
167 ms |
4156 KB |
Output is correct |
46 |
Correct |
60 ms |
4264 KB |
Output is correct |
47 |
Correct |
468 ms |
6292 KB |
Output is correct |
48 |
Correct |
1499 ms |
7908 KB |
Output is correct |
49 |
Correct |
485 ms |
6388 KB |
Output is correct |
50 |
Correct |
682 ms |
5532 KB |
Output is correct |
51 |
Correct |
670 ms |
5568 KB |
Output is correct |
52 |
Correct |
692 ms |
5536 KB |
Output is correct |
53 |
Correct |
1114 ms |
6644 KB |
Output is correct |
54 |
Correct |
1053 ms |
6692 KB |
Output is correct |
55 |
Correct |
1113 ms |
6780 KB |
Output is correct |
56 |
Correct |
448 ms |
6352 KB |
Output is correct |
57 |
Correct |
448 ms |
6372 KB |
Output is correct |
58 |
Correct |
1469 ms |
7892 KB |
Output is correct |
59 |
Correct |
1523 ms |
7728 KB |
Output is correct |
60 |
Correct |
1461 ms |
7816 KB |
Output is correct |
61 |
Correct |
1449 ms |
7752 KB |
Output is correct |
62 |
Correct |
1268 ms |
6968 KB |
Output is correct |
63 |
Correct |
1235 ms |
6972 KB |
Output is correct |
64 |
Correct |
1415 ms |
7964 KB |
Output is correct |
65 |
Correct |
576 ms |
5792 KB |
Output is correct |
66 |
Correct |
1158 ms |
5696 KB |
Output is correct |
67 |
Correct |
1413 ms |
5504 KB |
Output is correct |
68 |
Correct |
1226 ms |
5736 KB |
Output is correct |
69 |
Correct |
1028 ms |
5708 KB |
Output is correct |
70 |
Correct |
1365 ms |
5588 KB |
Output is correct |
71 |
Correct |
1366 ms |
5592 KB |
Output is correct |
72 |
Correct |
1372 ms |
5596 KB |
Output is correct |
73 |
Correct |
1202 ms |
5756 KB |
Output is correct |
74 |
Correct |
1199 ms |
5636 KB |
Output is correct |
75 |
Correct |
1221 ms |
5724 KB |
Output is correct |
76 |
Correct |
1020 ms |
5660 KB |
Output is correct |
77 |
Correct |
1016 ms |
5700 KB |
Output is correct |
78 |
Correct |
1004 ms |
5640 KB |
Output is correct |
79 |
Correct |
798 ms |
5820 KB |
Output is correct |
80 |
Correct |
795 ms |
5788 KB |
Output is correct |
81 |
Correct |
811 ms |
5676 KB |
Output is correct |
82 |
Correct |
825 ms |
5560 KB |
Output is correct |
83 |
Correct |
814 ms |
5572 KB |
Output is correct |
84 |
Correct |
820 ms |
5528 KB |
Output is correct |
85 |
Correct |
1890 ms |
7928 KB |
Output is correct |
86 |
Correct |
202 ms |
4676 KB |
Output is correct |
87 |
Correct |
95 ms |
4712 KB |
Output is correct |
88 |
Correct |
879 ms |
6468 KB |
Output is correct |
89 |
Correct |
1934 ms |
7956 KB |
Output is correct |
90 |
Correct |
890 ms |
6424 KB |
Output is correct |
91 |
Correct |
1233 ms |
5536 KB |
Output is correct |
92 |
Correct |
1226 ms |
5748 KB |
Output is correct |
93 |
Correct |
1603 ms |
5640 KB |
Output is correct |
94 |
Correct |
1579 ms |
6724 KB |
Output is correct |
95 |
Correct |
1555 ms |
6976 KB |
Output is correct |
96 |
Correct |
1744 ms |
6712 KB |
Output is correct |
97 |
Correct |
619 ms |
6496 KB |
Output is correct |
98 |
Correct |
690 ms |
6040 KB |
Output is correct |
99 |
Correct |
1953 ms |
7996 KB |
Output is correct |
100 |
Correct |
1977 ms |
7956 KB |
Output is correct |
101 |
Correct |
1940 ms |
8144 KB |
Output is correct |
102 |
Correct |
1966 ms |
7932 KB |
Output is correct |
103 |
Correct |
1925 ms |
7036 KB |
Output is correct |
104 |
Correct |
1923 ms |
6964 KB |
Output is correct |
105 |
Correct |
1545 ms |
6840 KB |
Output is correct |
106 |
Correct |
1267 ms |
6808 KB |
Output is correct |
107 |
Correct |
1404 ms |
7140 KB |
Output is correct |
108 |
Correct |
1882 ms |
7564 KB |
Output is correct |
109 |
Correct |
1060 ms |
5784 KB |
Output is correct |