#include <bits/stdc++.h>
using namespace std;
int n,m,qc;
const int n_max = 5e4+10;
const int m_max = 1e5+10;
const int q_max = 1e5+10;
struct edge {
int u,v,w,s,e;
edge() : u(0), v(0), w(0), s(0), e(0) {}
edge(int _u, int _v, int _w, int _s, int _e) : u(_u), v(_v), w(_w), s(_s), e(_e) {}
bool operator < (edge other) const {
return w > other.w; // invert comparator
}
};
struct query {
int time, start, weight, ans;
query() : time(0), start(0), weight(0), ans(0) {}
query(int _t, int _s, int _w) : time(_t), start(_s), weight(_w), ans(0) {}
bool operator < (query other) const {
return weight > other.weight;
}
};
vector<query> q;
vector<edge> init[m_max];
vector<edge> sorted_edge;
int visited[n_max];
int parent[n_max];
int sz[n_max];
// reset the ufds
void reset_ufds() {
for(int i=0; i<n_max; i++) {
parent[i] = i;
sz[i] = 1;
}
}
int findset(int x) {
while(parent[x]!=x) {
x = parent[x] = parent[parent[x]];
}
return x;
}
void onion(int x, int y) {
x = findset(x);
y = findset(y);
if(x!=y) {
if(sz[x]>sz[y]) swap(x,y);
sz[y] += sz[x];
parent[x] = y;
}
}
vector<int> adj[n_max];
vector<pair<int,int>> output;
void ans_query(int first, int last) { // [first,last)
for(int i=0; i<n_max; i++) {
adj[i].clear();
}
if(first>=last) return;
reset_ufds();
int ts = q[first].time;
int te = q[last-1].time;
sort(q.begin()+first, q.begin()+last); // sort by weight
auto it = sorted_edge.begin();
vector<edge> templist;
for(int i=first; i<last; i++) {
//cout << "i: " << i << "\n";
//cout << q[i].time << " " << q[i].weight << "\n";
while(it!=sorted_edge.end() && it->w >= q[i].weight) {
//it->print();
//cout << "weight: " << it->w << " " << it->s << " " << it->e << "\n";
if(it->s < ts && it->e > te) {
onion(it->u, it->v);
} else if((it->s < te && it->s > ts) || (it->e < te && it->e > ts)) {
// add it to the list of edges to process
//cout << "templist: " << it->u << " " << it->v << "\n";
templist.push_back(*it);
}
it++;
}
int starting = findset(q[i].start);
int ans = sz[starting];
for(edge &e: templist) {
e.u = findset(e.u);
e.v = findset(e.v);
adj[e.u].clear();
adj[e.v].clear();
}
for(edge &e: templist) {
if(e.s < q[i].time && e.e>q[i].time) {
adj[e.u].push_back(e.v);
adj[e.v].push_back(e.u);
}
}
visited[starting] = i; // record the visited time
//cout << "starting: " << starting << "\n";
queue<int> bfs;
bfs.push(starting);
while(!bfs.empty()) {
int next = bfs.front();
//cout << "bfs: " << next << "\n";
bfs.pop();
for(int z: adj[next]) {
z = findset(z);
if(visited[z]!=i) {
visited[z] = i;
ans += sz[z];
bfs.push(z);
}
}
}
output.push_back(make_pair(q[i].time, ans));
//cout << "output: " << q[i].time << " " << ans << "\n";
}
}
int main() {
//freopen("../q2/05","r",stdin);
//freopen("05b","w",stdout);
cin>>n>>m;
for(int i=0; i<m; i++) {
edge e;
cin >> e.u >> e.v >> e.w;
e.s = -1;
e.e = 2e5;
init[i].push_back(e);
}
cin >> qc;
const int bucket_size = 500;
vector<int> breakpoints;
for(int i=0; i<qc; i++) {
if(i%bucket_size==0) breakpoints.push_back(q.size());
int a,b,c; cin>>a>>b>>c;
if(a==2) {
q.push_back(query(i, b, c));
} else {
assert(a==1);
init[b-1].back().e = i;
init[b-1].push_back(edge(init[b-1][0].u, init[b-1][0].v, c, i, 2e5));
}
}
for(int i=0; i<m; i++) {
for(edge e: init[i]) {
sorted_edge.push_back(e);
}
}
breakpoints.push_back(q.size());
sort(sorted_edge.begin(), sorted_edge.end());
memset(visited, -1, sizeof(visited));
for(int i=1; i<breakpoints.size(); i++) {
//cout << "?\n";
ans_query(breakpoints[i-1], breakpoints[i]);
}
sort(output.begin(), output.end());
for(int i=1; i<output.size(); i++) {
assert(output[i].first != output[i-1].first);
}
for(auto p: output) {
cout << p.second << "\n";
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:149:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<breakpoints.size(); i++) {
~^~~~~~~~~~~~~~~~~~~
bridges.cpp:154:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<output.size(); i++) {
~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4480 KB |
Output is correct |
2 |
Correct |
7 ms |
4480 KB |
Output is correct |
3 |
Correct |
45 ms |
5120 KB |
Output is correct |
4 |
Correct |
23 ms |
4988 KB |
Output is correct |
5 |
Correct |
38 ms |
5112 KB |
Output is correct |
6 |
Correct |
34 ms |
5120 KB |
Output is correct |
7 |
Correct |
35 ms |
4992 KB |
Output is correct |
8 |
Correct |
36 ms |
5120 KB |
Output is correct |
9 |
Correct |
45 ms |
4992 KB |
Output is correct |
10 |
Correct |
35 ms |
5120 KB |
Output is correct |
11 |
Correct |
35 ms |
5120 KB |
Output is correct |
12 |
Correct |
40 ms |
5120 KB |
Output is correct |
13 |
Correct |
40 ms |
5108 KB |
Output is correct |
14 |
Correct |
38 ms |
5108 KB |
Output is correct |
15 |
Correct |
37 ms |
5120 KB |
Output is correct |
16 |
Correct |
37 ms |
4992 KB |
Output is correct |
17 |
Correct |
38 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1101 ms |
13140 KB |
Output is correct |
2 |
Correct |
967 ms |
12996 KB |
Output is correct |
3 |
Correct |
946 ms |
13052 KB |
Output is correct |
4 |
Correct |
957 ms |
13148 KB |
Output is correct |
5 |
Correct |
954 ms |
13048 KB |
Output is correct |
6 |
Correct |
1390 ms |
12684 KB |
Output is correct |
7 |
Correct |
1328 ms |
12620 KB |
Output is correct |
8 |
Correct |
1259 ms |
12720 KB |
Output is correct |
9 |
Correct |
159 ms |
8548 KB |
Output is correct |
10 |
Correct |
1086 ms |
12976 KB |
Output is correct |
11 |
Correct |
997 ms |
12892 KB |
Output is correct |
12 |
Correct |
686 ms |
12460 KB |
Output is correct |
13 |
Correct |
952 ms |
14692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
844 ms |
11888 KB |
Output is correct |
2 |
Correct |
745 ms |
10600 KB |
Output is correct |
3 |
Correct |
977 ms |
12124 KB |
Output is correct |
4 |
Correct |
865 ms |
11832 KB |
Output is correct |
5 |
Correct |
157 ms |
9036 KB |
Output is correct |
6 |
Correct |
909 ms |
12004 KB |
Output is correct |
7 |
Correct |
771 ms |
11876 KB |
Output is correct |
8 |
Correct |
700 ms |
11836 KB |
Output is correct |
9 |
Correct |
507 ms |
11264 KB |
Output is correct |
10 |
Correct |
476 ms |
11284 KB |
Output is correct |
11 |
Correct |
757 ms |
12812 KB |
Output is correct |
12 |
Correct |
652 ms |
13000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
684 ms |
14432 KB |
Output is correct |
2 |
Correct |
164 ms |
9060 KB |
Output is correct |
3 |
Correct |
176 ms |
11020 KB |
Output is correct |
4 |
Correct |
172 ms |
10984 KB |
Output is correct |
5 |
Correct |
616 ms |
14536 KB |
Output is correct |
6 |
Correct |
702 ms |
14344 KB |
Output is correct |
7 |
Correct |
607 ms |
14436 KB |
Output is correct |
8 |
Correct |
579 ms |
11612 KB |
Output is correct |
9 |
Correct |
527 ms |
11596 KB |
Output is correct |
10 |
Correct |
525 ms |
11880 KB |
Output is correct |
11 |
Correct |
745 ms |
13020 KB |
Output is correct |
12 |
Correct |
709 ms |
13096 KB |
Output is correct |
13 |
Correct |
664 ms |
13280 KB |
Output is correct |
14 |
Correct |
594 ms |
14716 KB |
Output is correct |
15 |
Correct |
618 ms |
14492 KB |
Output is correct |
16 |
Correct |
754 ms |
14472 KB |
Output is correct |
17 |
Correct |
753 ms |
14396 KB |
Output is correct |
18 |
Correct |
876 ms |
14456 KB |
Output is correct |
19 |
Correct |
739 ms |
14280 KB |
Output is correct |
20 |
Correct |
708 ms |
13800 KB |
Output is correct |
21 |
Correct |
713 ms |
13792 KB |
Output is correct |
22 |
Correct |
705 ms |
14304 KB |
Output is correct |
23 |
Correct |
581 ms |
13704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1101 ms |
13140 KB |
Output is correct |
2 |
Correct |
967 ms |
12996 KB |
Output is correct |
3 |
Correct |
946 ms |
13052 KB |
Output is correct |
4 |
Correct |
957 ms |
13148 KB |
Output is correct |
5 |
Correct |
954 ms |
13048 KB |
Output is correct |
6 |
Correct |
1390 ms |
12684 KB |
Output is correct |
7 |
Correct |
1328 ms |
12620 KB |
Output is correct |
8 |
Correct |
1259 ms |
12720 KB |
Output is correct |
9 |
Correct |
159 ms |
8548 KB |
Output is correct |
10 |
Correct |
1086 ms |
12976 KB |
Output is correct |
11 |
Correct |
997 ms |
12892 KB |
Output is correct |
12 |
Correct |
686 ms |
12460 KB |
Output is correct |
13 |
Correct |
952 ms |
14692 KB |
Output is correct |
14 |
Correct |
844 ms |
11888 KB |
Output is correct |
15 |
Correct |
745 ms |
10600 KB |
Output is correct |
16 |
Correct |
977 ms |
12124 KB |
Output is correct |
17 |
Correct |
865 ms |
11832 KB |
Output is correct |
18 |
Correct |
157 ms |
9036 KB |
Output is correct |
19 |
Correct |
909 ms |
12004 KB |
Output is correct |
20 |
Correct |
771 ms |
11876 KB |
Output is correct |
21 |
Correct |
700 ms |
11836 KB |
Output is correct |
22 |
Correct |
507 ms |
11264 KB |
Output is correct |
23 |
Correct |
476 ms |
11284 KB |
Output is correct |
24 |
Correct |
757 ms |
12812 KB |
Output is correct |
25 |
Correct |
652 ms |
13000 KB |
Output is correct |
26 |
Correct |
1024 ms |
13276 KB |
Output is correct |
27 |
Correct |
1167 ms |
12984 KB |
Output is correct |
28 |
Correct |
1012 ms |
13020 KB |
Output is correct |
29 |
Correct |
853 ms |
12900 KB |
Output is correct |
30 |
Correct |
1242 ms |
13004 KB |
Output is correct |
31 |
Correct |
1190 ms |
13028 KB |
Output is correct |
32 |
Correct |
1220 ms |
13236 KB |
Output is correct |
33 |
Correct |
1028 ms |
13148 KB |
Output is correct |
34 |
Correct |
1043 ms |
13072 KB |
Output is correct |
35 |
Correct |
1020 ms |
12932 KB |
Output is correct |
36 |
Correct |
852 ms |
12380 KB |
Output is correct |
37 |
Correct |
832 ms |
12428 KB |
Output is correct |
38 |
Correct |
844 ms |
12196 KB |
Output is correct |
39 |
Correct |
611 ms |
11284 KB |
Output is correct |
40 |
Correct |
643 ms |
11440 KB |
Output is correct |
41 |
Correct |
608 ms |
11432 KB |
Output is correct |
42 |
Correct |
804 ms |
13924 KB |
Output is correct |
43 |
Correct |
787 ms |
13924 KB |
Output is correct |
44 |
Correct |
839 ms |
14056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4480 KB |
Output is correct |
2 |
Correct |
7 ms |
4480 KB |
Output is correct |
3 |
Correct |
45 ms |
5120 KB |
Output is correct |
4 |
Correct |
23 ms |
4988 KB |
Output is correct |
5 |
Correct |
38 ms |
5112 KB |
Output is correct |
6 |
Correct |
34 ms |
5120 KB |
Output is correct |
7 |
Correct |
35 ms |
4992 KB |
Output is correct |
8 |
Correct |
36 ms |
5120 KB |
Output is correct |
9 |
Correct |
45 ms |
4992 KB |
Output is correct |
10 |
Correct |
35 ms |
5120 KB |
Output is correct |
11 |
Correct |
35 ms |
5120 KB |
Output is correct |
12 |
Correct |
40 ms |
5120 KB |
Output is correct |
13 |
Correct |
40 ms |
5108 KB |
Output is correct |
14 |
Correct |
38 ms |
5108 KB |
Output is correct |
15 |
Correct |
37 ms |
5120 KB |
Output is correct |
16 |
Correct |
37 ms |
4992 KB |
Output is correct |
17 |
Correct |
38 ms |
4992 KB |
Output is correct |
18 |
Correct |
1101 ms |
13140 KB |
Output is correct |
19 |
Correct |
967 ms |
12996 KB |
Output is correct |
20 |
Correct |
946 ms |
13052 KB |
Output is correct |
21 |
Correct |
957 ms |
13148 KB |
Output is correct |
22 |
Correct |
954 ms |
13048 KB |
Output is correct |
23 |
Correct |
1390 ms |
12684 KB |
Output is correct |
24 |
Correct |
1328 ms |
12620 KB |
Output is correct |
25 |
Correct |
1259 ms |
12720 KB |
Output is correct |
26 |
Correct |
159 ms |
8548 KB |
Output is correct |
27 |
Correct |
1086 ms |
12976 KB |
Output is correct |
28 |
Correct |
997 ms |
12892 KB |
Output is correct |
29 |
Correct |
686 ms |
12460 KB |
Output is correct |
30 |
Correct |
952 ms |
14692 KB |
Output is correct |
31 |
Correct |
844 ms |
11888 KB |
Output is correct |
32 |
Correct |
745 ms |
10600 KB |
Output is correct |
33 |
Correct |
977 ms |
12124 KB |
Output is correct |
34 |
Correct |
865 ms |
11832 KB |
Output is correct |
35 |
Correct |
157 ms |
9036 KB |
Output is correct |
36 |
Correct |
909 ms |
12004 KB |
Output is correct |
37 |
Correct |
771 ms |
11876 KB |
Output is correct |
38 |
Correct |
700 ms |
11836 KB |
Output is correct |
39 |
Correct |
507 ms |
11264 KB |
Output is correct |
40 |
Correct |
476 ms |
11284 KB |
Output is correct |
41 |
Correct |
757 ms |
12812 KB |
Output is correct |
42 |
Correct |
652 ms |
13000 KB |
Output is correct |
43 |
Correct |
684 ms |
14432 KB |
Output is correct |
44 |
Correct |
164 ms |
9060 KB |
Output is correct |
45 |
Correct |
176 ms |
11020 KB |
Output is correct |
46 |
Correct |
172 ms |
10984 KB |
Output is correct |
47 |
Correct |
616 ms |
14536 KB |
Output is correct |
48 |
Correct |
702 ms |
14344 KB |
Output is correct |
49 |
Correct |
607 ms |
14436 KB |
Output is correct |
50 |
Correct |
579 ms |
11612 KB |
Output is correct |
51 |
Correct |
527 ms |
11596 KB |
Output is correct |
52 |
Correct |
525 ms |
11880 KB |
Output is correct |
53 |
Correct |
745 ms |
13020 KB |
Output is correct |
54 |
Correct |
709 ms |
13096 KB |
Output is correct |
55 |
Correct |
664 ms |
13280 KB |
Output is correct |
56 |
Correct |
594 ms |
14716 KB |
Output is correct |
57 |
Correct |
618 ms |
14492 KB |
Output is correct |
58 |
Correct |
754 ms |
14472 KB |
Output is correct |
59 |
Correct |
753 ms |
14396 KB |
Output is correct |
60 |
Correct |
876 ms |
14456 KB |
Output is correct |
61 |
Correct |
739 ms |
14280 KB |
Output is correct |
62 |
Correct |
708 ms |
13800 KB |
Output is correct |
63 |
Correct |
713 ms |
13792 KB |
Output is correct |
64 |
Correct |
705 ms |
14304 KB |
Output is correct |
65 |
Correct |
581 ms |
13704 KB |
Output is correct |
66 |
Correct |
1024 ms |
13276 KB |
Output is correct |
67 |
Correct |
1167 ms |
12984 KB |
Output is correct |
68 |
Correct |
1012 ms |
13020 KB |
Output is correct |
69 |
Correct |
853 ms |
12900 KB |
Output is correct |
70 |
Correct |
1242 ms |
13004 KB |
Output is correct |
71 |
Correct |
1190 ms |
13028 KB |
Output is correct |
72 |
Correct |
1220 ms |
13236 KB |
Output is correct |
73 |
Correct |
1028 ms |
13148 KB |
Output is correct |
74 |
Correct |
1043 ms |
13072 KB |
Output is correct |
75 |
Correct |
1020 ms |
12932 KB |
Output is correct |
76 |
Correct |
852 ms |
12380 KB |
Output is correct |
77 |
Correct |
832 ms |
12428 KB |
Output is correct |
78 |
Correct |
844 ms |
12196 KB |
Output is correct |
79 |
Correct |
611 ms |
11284 KB |
Output is correct |
80 |
Correct |
643 ms |
11440 KB |
Output is correct |
81 |
Correct |
608 ms |
11432 KB |
Output is correct |
82 |
Correct |
804 ms |
13924 KB |
Output is correct |
83 |
Correct |
787 ms |
13924 KB |
Output is correct |
84 |
Correct |
839 ms |
14056 KB |
Output is correct |
85 |
Correct |
1113 ms |
15712 KB |
Output is correct |
86 |
Correct |
193 ms |
10364 KB |
Output is correct |
87 |
Correct |
207 ms |
10368 KB |
Output is correct |
88 |
Correct |
1020 ms |
15588 KB |
Output is correct |
89 |
Correct |
1109 ms |
15332 KB |
Output is correct |
90 |
Correct |
1053 ms |
15204 KB |
Output is correct |
91 |
Correct |
1049 ms |
11996 KB |
Output is correct |
92 |
Correct |
1055 ms |
11992 KB |
Output is correct |
93 |
Correct |
1279 ms |
11560 KB |
Output is correct |
94 |
Correct |
1219 ms |
13300 KB |
Output is correct |
95 |
Correct |
1148 ms |
13256 KB |
Output is correct |
96 |
Correct |
1236 ms |
13012 KB |
Output is correct |
97 |
Correct |
723 ms |
13836 KB |
Output is correct |
98 |
Correct |
982 ms |
15240 KB |
Output is correct |
99 |
Correct |
1139 ms |
15284 KB |
Output is correct |
100 |
Correct |
1171 ms |
15588 KB |
Output is correct |
101 |
Correct |
1173 ms |
15568 KB |
Output is correct |
102 |
Correct |
1212 ms |
15692 KB |
Output is correct |
103 |
Correct |
1276 ms |
14948 KB |
Output is correct |
104 |
Correct |
1306 ms |
15012 KB |
Output is correct |
105 |
Correct |
1170 ms |
15080 KB |
Output is correct |
106 |
Correct |
1049 ms |
14952 KB |
Output is correct |
107 |
Correct |
879 ms |
13448 KB |
Output is correct |
108 |
Correct |
1255 ms |
15556 KB |
Output is correct |
109 |
Correct |
1143 ms |
13552 KB |
Output is correct |