#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int B = 800;
using lint = long long;
using pi = pair<int, int>;
int n, m, q;
bool in_must[MAXN];
bool in_quer[MAXN];
struct disj{
int pa[MAXN];
int sz[MAXN];
void init(int n){
iota(pa, pa + n + 1, 0);
fill(sz, sz + n + 1, 1);
}
int find(int x){
return pa[x] == x ? x : find(pa[x]);
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
if(sz[p] < sz[q]) swap(p, q);
pa[q] = p;
sz[p] += sz[q];
return 1;
}
bool uni(int p, int q, vector<pi> &rvt){
p = find(p);
q = find(q);
if(p == q) return 0;
if(sz[p] < sz[q]) swap(p, q);
rvt.emplace_back(q, -1);
pa[q] = p;
rvt.emplace_back(p, sz[p]);
sz[p] += sz[q];
return 1;
}
void revert(vector<pi> &v){
reverse(v.begin(), v.end());
for(auto &i : v){
if(i.second == -1) pa[i.first] = i.first;
else sz[i.first] = i.second;
}
v.clear();
}
int getSz(int x){ return sz[find(x)]; }
}disj;
struct edg{
int s, e, x, idx;
bool operator<(const edg &e)const{
return x < e.x;
}
}e[MAXN];
struct qry{
int pos, idx, thres;
bool operator<(const qry &q)const{
return thres < q.thres;
}
};
int t[MAXN], x[MAXN], y[MAXN];
int rev[MAXN], ret[MAXN];
int aux[MAXN];
int main(){
scanf("%d %d",&n,&m);
for(int i=0; i<m; i++){
scanf("%d %d %d",&e[i].s,&e[i].e,&e[i].x);
e[i].x = 1696969696 - e[i].x;
e[i].idx = i + 1;
}
scanf("%d",&q);
for(int i=0; i<q; i++){
scanf("%d %d %d",&t[i],&x[i],&y[i]);
y[i] = 1696969696 - y[i];
}
sort(e, e + m);
for(int i=0; i<q; i+=B){
for(int i=0; i<m; i++) rev[e[i].idx] = i;
memset(in_must, 0, sizeof(in_must));
vector<int> must;
vector<int> maybe;
disj.init(n);
for(int j=i; j<i+B && j<q; j++){
if(t[j] == 1){
int pos = rev[x[j]];
in_quer[pos] = 1;
}
}
for(int i=0; i<m; i++){
if(in_quer[i]) continue;
if(disj.uni(e[i].s, e[i].e)){
must.push_back(i);
}
}
vector<qry> qr;
vector<int> drog;
for(int j=i; j<i+B && j<q; j++){
if(t[j] == 2){
qr.push_back({x[j], j, y[j]});
}
if(t[j] == 1){
if(in_quer[rev[x[j]]]){
in_quer[rev[x[j]]] = 0;
drog.push_back(x[j]);
}
}
}
sort(qr.begin(), qr.end());
disj.init(n);
int ptr = 0;
for(auto &k : qr){
while(ptr < must.size() && e[must[ptr]].x <= k.thres){
disj.uni(e[must[ptr]].s, e[must[ptr]].e);
ptr++;
}
vector<pi> logs;
for(int j=i; j<k.idx; j++){
if(t[j] == 1){
aux[x[j]] = y[j];
}
}
for(auto &i : maybe){
if(e[i].x <= k.thres){
disj.uni(e[i].s, e[i].e, logs);
}
}
for(auto &i : drog){
int pos = rev[i];
int cost = aux[i];
if(cost == 0) cost = e[pos].x;
if(cost <= k.thres){
disj.uni(e[pos].s, e[pos].e, logs);
}
}
ret[k.idx] = disj.getSz(k.pos);
disj.revert(logs);
for(int j=i; j<k.idx; j++){
if(t[j] == 1){
aux[x[j]] = 0;
}
}
}
for(int j=i; j<q && j<i+B; j++){
if(t[j] == 1) aux[x[j]] = y[j];
}
vector<edg> l, r;
for(int i=0; i<m; i++){
if(aux[e[i].idx]){
e[i].x = aux[e[i].idx];
aux[e[i].idx] = 0;
r.push_back(e[i]);
}
else l.push_back(e[i]);
}
sort(r.begin(), r.end());
merge(l.begin(), l.end(), r.begin(), r.end(), e);
}
for(int i=0; i<q; i++) if(t[i] == 2) printf("%d\n", ret[i]);
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:119:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr < must.size() && e[must[ptr]].x <= k.thres){
~~~~^~~~~~~~~~~~~
bridges.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
bridges.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&e[i].s,&e[i].e,&e[i].x);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
bridges.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&t[i],&x[i],&y[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
24 ms |
768 KB |
Output is correct |
4 |
Correct |
13 ms |
640 KB |
Output is correct |
5 |
Correct |
18 ms |
640 KB |
Output is correct |
6 |
Correct |
16 ms |
640 KB |
Output is correct |
7 |
Correct |
19 ms |
640 KB |
Output is correct |
8 |
Correct |
22 ms |
640 KB |
Output is correct |
9 |
Correct |
21 ms |
640 KB |
Output is correct |
10 |
Correct |
22 ms |
640 KB |
Output is correct |
11 |
Correct |
21 ms |
612 KB |
Output is correct |
12 |
Correct |
23 ms |
640 KB |
Output is correct |
13 |
Correct |
26 ms |
768 KB |
Output is correct |
14 |
Correct |
25 ms |
708 KB |
Output is correct |
15 |
Correct |
22 ms |
640 KB |
Output is correct |
16 |
Correct |
21 ms |
640 KB |
Output is correct |
17 |
Correct |
21 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1204 ms |
5976 KB |
Output is correct |
2 |
Correct |
1262 ms |
6164 KB |
Output is correct |
3 |
Correct |
1272 ms |
5876 KB |
Output is correct |
4 |
Correct |
1497 ms |
6052 KB |
Output is correct |
5 |
Correct |
1439 ms |
5916 KB |
Output is correct |
6 |
Correct |
1873 ms |
6080 KB |
Output is correct |
7 |
Correct |
1865 ms |
6048 KB |
Output is correct |
8 |
Correct |
2060 ms |
5952 KB |
Output is correct |
9 |
Correct |
104 ms |
2172 KB |
Output is correct |
10 |
Correct |
1380 ms |
6068 KB |
Output is correct |
11 |
Correct |
1279 ms |
6028 KB |
Output is correct |
12 |
Correct |
1032 ms |
6040 KB |
Output is correct |
13 |
Correct |
1165 ms |
5980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1002 ms |
4512 KB |
Output is correct |
2 |
Correct |
792 ms |
2792 KB |
Output is correct |
3 |
Correct |
1126 ms |
4564 KB |
Output is correct |
4 |
Correct |
985 ms |
4596 KB |
Output is correct |
5 |
Correct |
106 ms |
2296 KB |
Output is correct |
6 |
Correct |
1012 ms |
4444 KB |
Output is correct |
7 |
Correct |
900 ms |
4396 KB |
Output is correct |
8 |
Correct |
988 ms |
4492 KB |
Output is correct |
9 |
Correct |
613 ms |
4588 KB |
Output is correct |
10 |
Correct |
585 ms |
4332 KB |
Output is correct |
11 |
Correct |
644 ms |
4476 KB |
Output is correct |
12 |
Correct |
517 ms |
4372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1313 ms |
8484 KB |
Output is correct |
2 |
Correct |
107 ms |
2224 KB |
Output is correct |
3 |
Correct |
115 ms |
6260 KB |
Output is correct |
4 |
Correct |
102 ms |
6248 KB |
Output is correct |
5 |
Correct |
1107 ms |
8636 KB |
Output is correct |
6 |
Correct |
1124 ms |
8448 KB |
Output is correct |
7 |
Correct |
1119 ms |
8408 KB |
Output is correct |
8 |
Correct |
636 ms |
5760 KB |
Output is correct |
9 |
Correct |
610 ms |
5624 KB |
Output is correct |
10 |
Correct |
611 ms |
5660 KB |
Output is correct |
11 |
Correct |
949 ms |
7584 KB |
Output is correct |
12 |
Correct |
911 ms |
7636 KB |
Output is correct |
13 |
Correct |
950 ms |
7688 KB |
Output is correct |
14 |
Correct |
1165 ms |
8472 KB |
Output is correct |
15 |
Correct |
1057 ms |
8608 KB |
Output is correct |
16 |
Correct |
1157 ms |
8572 KB |
Output is correct |
17 |
Correct |
1162 ms |
8508 KB |
Output is correct |
18 |
Correct |
1166 ms |
8656 KB |
Output is correct |
19 |
Correct |
1128 ms |
8684 KB |
Output is correct |
20 |
Correct |
1044 ms |
7872 KB |
Output is correct |
21 |
Correct |
1044 ms |
8016 KB |
Output is correct |
22 |
Correct |
1172 ms |
8364 KB |
Output is correct |
23 |
Correct |
1016 ms |
7972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1204 ms |
5976 KB |
Output is correct |
2 |
Correct |
1262 ms |
6164 KB |
Output is correct |
3 |
Correct |
1272 ms |
5876 KB |
Output is correct |
4 |
Correct |
1497 ms |
6052 KB |
Output is correct |
5 |
Correct |
1439 ms |
5916 KB |
Output is correct |
6 |
Correct |
1873 ms |
6080 KB |
Output is correct |
7 |
Correct |
1865 ms |
6048 KB |
Output is correct |
8 |
Correct |
2060 ms |
5952 KB |
Output is correct |
9 |
Correct |
104 ms |
2172 KB |
Output is correct |
10 |
Correct |
1380 ms |
6068 KB |
Output is correct |
11 |
Correct |
1279 ms |
6028 KB |
Output is correct |
12 |
Correct |
1032 ms |
6040 KB |
Output is correct |
13 |
Correct |
1165 ms |
5980 KB |
Output is correct |
14 |
Correct |
1002 ms |
4512 KB |
Output is correct |
15 |
Correct |
792 ms |
2792 KB |
Output is correct |
16 |
Correct |
1126 ms |
4564 KB |
Output is correct |
17 |
Correct |
985 ms |
4596 KB |
Output is correct |
18 |
Correct |
106 ms |
2296 KB |
Output is correct |
19 |
Correct |
1012 ms |
4444 KB |
Output is correct |
20 |
Correct |
900 ms |
4396 KB |
Output is correct |
21 |
Correct |
988 ms |
4492 KB |
Output is correct |
22 |
Correct |
613 ms |
4588 KB |
Output is correct |
23 |
Correct |
585 ms |
4332 KB |
Output is correct |
24 |
Correct |
644 ms |
4476 KB |
Output is correct |
25 |
Correct |
517 ms |
4372 KB |
Output is correct |
26 |
Correct |
1299 ms |
5976 KB |
Output is correct |
27 |
Correct |
1705 ms |
5992 KB |
Output is correct |
28 |
Correct |
1443 ms |
6016 KB |
Output is correct |
29 |
Correct |
1102 ms |
5976 KB |
Output is correct |
30 |
Correct |
1667 ms |
5924 KB |
Output is correct |
31 |
Correct |
1728 ms |
6112 KB |
Output is correct |
32 |
Correct |
1723 ms |
6040 KB |
Output is correct |
33 |
Correct |
1512 ms |
5928 KB |
Output is correct |
34 |
Correct |
1456 ms |
6112 KB |
Output is correct |
35 |
Correct |
1485 ms |
6048 KB |
Output is correct |
36 |
Correct |
1112 ms |
5976 KB |
Output is correct |
37 |
Correct |
1086 ms |
5948 KB |
Output is correct |
38 |
Correct |
1075 ms |
5988 KB |
Output is correct |
39 |
Correct |
889 ms |
5920 KB |
Output is correct |
40 |
Correct |
1054 ms |
5904 KB |
Output is correct |
41 |
Correct |
855 ms |
6072 KB |
Output is correct |
42 |
Correct |
750 ms |
5908 KB |
Output is correct |
43 |
Correct |
748 ms |
6072 KB |
Output is correct |
44 |
Correct |
729 ms |
5800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
24 ms |
768 KB |
Output is correct |
4 |
Correct |
13 ms |
640 KB |
Output is correct |
5 |
Correct |
18 ms |
640 KB |
Output is correct |
6 |
Correct |
16 ms |
640 KB |
Output is correct |
7 |
Correct |
19 ms |
640 KB |
Output is correct |
8 |
Correct |
22 ms |
640 KB |
Output is correct |
9 |
Correct |
21 ms |
640 KB |
Output is correct |
10 |
Correct |
22 ms |
640 KB |
Output is correct |
11 |
Correct |
21 ms |
612 KB |
Output is correct |
12 |
Correct |
23 ms |
640 KB |
Output is correct |
13 |
Correct |
26 ms |
768 KB |
Output is correct |
14 |
Correct |
25 ms |
708 KB |
Output is correct |
15 |
Correct |
22 ms |
640 KB |
Output is correct |
16 |
Correct |
21 ms |
640 KB |
Output is correct |
17 |
Correct |
21 ms |
640 KB |
Output is correct |
18 |
Correct |
1204 ms |
5976 KB |
Output is correct |
19 |
Correct |
1262 ms |
6164 KB |
Output is correct |
20 |
Correct |
1272 ms |
5876 KB |
Output is correct |
21 |
Correct |
1497 ms |
6052 KB |
Output is correct |
22 |
Correct |
1439 ms |
5916 KB |
Output is correct |
23 |
Correct |
1873 ms |
6080 KB |
Output is correct |
24 |
Correct |
1865 ms |
6048 KB |
Output is correct |
25 |
Correct |
2060 ms |
5952 KB |
Output is correct |
26 |
Correct |
104 ms |
2172 KB |
Output is correct |
27 |
Correct |
1380 ms |
6068 KB |
Output is correct |
28 |
Correct |
1279 ms |
6028 KB |
Output is correct |
29 |
Correct |
1032 ms |
6040 KB |
Output is correct |
30 |
Correct |
1165 ms |
5980 KB |
Output is correct |
31 |
Correct |
1002 ms |
4512 KB |
Output is correct |
32 |
Correct |
792 ms |
2792 KB |
Output is correct |
33 |
Correct |
1126 ms |
4564 KB |
Output is correct |
34 |
Correct |
985 ms |
4596 KB |
Output is correct |
35 |
Correct |
106 ms |
2296 KB |
Output is correct |
36 |
Correct |
1012 ms |
4444 KB |
Output is correct |
37 |
Correct |
900 ms |
4396 KB |
Output is correct |
38 |
Correct |
988 ms |
4492 KB |
Output is correct |
39 |
Correct |
613 ms |
4588 KB |
Output is correct |
40 |
Correct |
585 ms |
4332 KB |
Output is correct |
41 |
Correct |
644 ms |
4476 KB |
Output is correct |
42 |
Correct |
517 ms |
4372 KB |
Output is correct |
43 |
Correct |
1313 ms |
8484 KB |
Output is correct |
44 |
Correct |
107 ms |
2224 KB |
Output is correct |
45 |
Correct |
115 ms |
6260 KB |
Output is correct |
46 |
Correct |
102 ms |
6248 KB |
Output is correct |
47 |
Correct |
1107 ms |
8636 KB |
Output is correct |
48 |
Correct |
1124 ms |
8448 KB |
Output is correct |
49 |
Correct |
1119 ms |
8408 KB |
Output is correct |
50 |
Correct |
636 ms |
5760 KB |
Output is correct |
51 |
Correct |
610 ms |
5624 KB |
Output is correct |
52 |
Correct |
611 ms |
5660 KB |
Output is correct |
53 |
Correct |
949 ms |
7584 KB |
Output is correct |
54 |
Correct |
911 ms |
7636 KB |
Output is correct |
55 |
Correct |
950 ms |
7688 KB |
Output is correct |
56 |
Correct |
1165 ms |
8472 KB |
Output is correct |
57 |
Correct |
1057 ms |
8608 KB |
Output is correct |
58 |
Correct |
1157 ms |
8572 KB |
Output is correct |
59 |
Correct |
1162 ms |
8508 KB |
Output is correct |
60 |
Correct |
1166 ms |
8656 KB |
Output is correct |
61 |
Correct |
1128 ms |
8684 KB |
Output is correct |
62 |
Correct |
1044 ms |
7872 KB |
Output is correct |
63 |
Correct |
1044 ms |
8016 KB |
Output is correct |
64 |
Correct |
1172 ms |
8364 KB |
Output is correct |
65 |
Correct |
1016 ms |
7972 KB |
Output is correct |
66 |
Correct |
1299 ms |
5976 KB |
Output is correct |
67 |
Correct |
1705 ms |
5992 KB |
Output is correct |
68 |
Correct |
1443 ms |
6016 KB |
Output is correct |
69 |
Correct |
1102 ms |
5976 KB |
Output is correct |
70 |
Correct |
1667 ms |
5924 KB |
Output is correct |
71 |
Correct |
1728 ms |
6112 KB |
Output is correct |
72 |
Correct |
1723 ms |
6040 KB |
Output is correct |
73 |
Correct |
1512 ms |
5928 KB |
Output is correct |
74 |
Correct |
1456 ms |
6112 KB |
Output is correct |
75 |
Correct |
1485 ms |
6048 KB |
Output is correct |
76 |
Correct |
1112 ms |
5976 KB |
Output is correct |
77 |
Correct |
1086 ms |
5948 KB |
Output is correct |
78 |
Correct |
1075 ms |
5988 KB |
Output is correct |
79 |
Correct |
889 ms |
5920 KB |
Output is correct |
80 |
Correct |
1054 ms |
5904 KB |
Output is correct |
81 |
Correct |
855 ms |
6072 KB |
Output is correct |
82 |
Correct |
750 ms |
5908 KB |
Output is correct |
83 |
Correct |
748 ms |
6072 KB |
Output is correct |
84 |
Correct |
729 ms |
5800 KB |
Output is correct |
85 |
Correct |
1833 ms |
8860 KB |
Output is correct |
86 |
Correct |
164 ms |
6716 KB |
Output is correct |
87 |
Correct |
127 ms |
6740 KB |
Output is correct |
88 |
Correct |
1608 ms |
9072 KB |
Output is correct |
89 |
Correct |
1716 ms |
9016 KB |
Output is correct |
90 |
Correct |
1506 ms |
8916 KB |
Output is correct |
91 |
Correct |
1467 ms |
6076 KB |
Output is correct |
92 |
Correct |
1409 ms |
5956 KB |
Output is correct |
93 |
Correct |
2061 ms |
6096 KB |
Output is correct |
94 |
Correct |
1638 ms |
8028 KB |
Output is correct |
95 |
Correct |
1595 ms |
7948 KB |
Output is correct |
96 |
Correct |
1677 ms |
7852 KB |
Output is correct |
97 |
Correct |
1204 ms |
8796 KB |
Output is correct |
98 |
Correct |
1272 ms |
8788 KB |
Output is correct |
99 |
Correct |
1785 ms |
8864 KB |
Output is correct |
100 |
Correct |
1920 ms |
9128 KB |
Output is correct |
101 |
Correct |
1941 ms |
9060 KB |
Output is correct |
102 |
Correct |
1889 ms |
8872 KB |
Output is correct |
103 |
Correct |
1851 ms |
8292 KB |
Output is correct |
104 |
Correct |
1825 ms |
8168 KB |
Output is correct |
105 |
Correct |
1364 ms |
8384 KB |
Output is correct |
106 |
Correct |
1112 ms |
7892 KB |
Output is correct |
107 |
Correct |
1232 ms |
8356 KB |
Output is correct |
108 |
Correct |
1670 ms |
8680 KB |
Output is correct |
109 |
Correct |
1503 ms |
8064 KB |
Output is correct |