#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) {
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:148:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<breakpoints.size(); i++) {
~^~~~~~~~~~~~~~~~~~~
bridges.cpp:153: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 |
46 ms |
5216 KB |
Output is correct |
4 |
Correct |
31 ms |
4988 KB |
Output is correct |
5 |
Correct |
37 ms |
5112 KB |
Output is correct |
6 |
Correct |
35 ms |
5088 KB |
Output is correct |
7 |
Correct |
37 ms |
4992 KB |
Output is correct |
8 |
Correct |
36 ms |
5120 KB |
Output is correct |
9 |
Correct |
46 ms |
4992 KB |
Output is correct |
10 |
Correct |
36 ms |
5112 KB |
Output is correct |
11 |
Correct |
41 ms |
5120 KB |
Output is correct |
12 |
Correct |
39 ms |
5120 KB |
Output is correct |
13 |
Correct |
41 ms |
5108 KB |
Output is correct |
14 |
Correct |
39 ms |
5108 KB |
Output is correct |
15 |
Correct |
37 ms |
5120 KB |
Output is correct |
16 |
Correct |
38 ms |
4992 KB |
Output is correct |
17 |
Correct |
37 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
892 ms |
12776 KB |
Output is correct |
2 |
Correct |
868 ms |
12640 KB |
Output is correct |
3 |
Correct |
864 ms |
12644 KB |
Output is correct |
4 |
Correct |
851 ms |
12764 KB |
Output is correct |
5 |
Correct |
860 ms |
12636 KB |
Output is correct |
6 |
Correct |
1299 ms |
12488 KB |
Output is correct |
7 |
Correct |
1218 ms |
12340 KB |
Output is correct |
8 |
Correct |
1167 ms |
12420 KB |
Output is correct |
9 |
Correct |
156 ms |
8420 KB |
Output is correct |
10 |
Correct |
1004 ms |
12604 KB |
Output is correct |
11 |
Correct |
934 ms |
12700 KB |
Output is correct |
12 |
Correct |
605 ms |
11860 KB |
Output is correct |
13 |
Correct |
878 ms |
14308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
903 ms |
13864 KB |
Output is correct |
2 |
Correct |
800 ms |
12332 KB |
Output is correct |
3 |
Correct |
1136 ms |
16720 KB |
Output is correct |
4 |
Correct |
988 ms |
19248 KB |
Output is correct |
5 |
Correct |
169 ms |
8548 KB |
Output is correct |
6 |
Correct |
1091 ms |
18220 KB |
Output is correct |
7 |
Correct |
942 ms |
17472 KB |
Output is correct |
8 |
Correct |
828 ms |
15588 KB |
Output is correct |
9 |
Correct |
641 ms |
12136 KB |
Output is correct |
10 |
Correct |
594 ms |
11608 KB |
Output is correct |
11 |
Correct |
846 ms |
18380 KB |
Output is correct |
12 |
Correct |
801 ms |
16056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1144 ms |
13964 KB |
Output is correct |
2 |
Correct |
158 ms |
8676 KB |
Output is correct |
3 |
Correct |
170 ms |
10476 KB |
Output is correct |
4 |
Correct |
172 ms |
10600 KB |
Output is correct |
5 |
Correct |
1037 ms |
14204 KB |
Output is correct |
6 |
Correct |
1103 ms |
14048 KB |
Output is correct |
7 |
Correct |
1044 ms |
14308 KB |
Output is correct |
8 |
Correct |
452 ms |
11240 KB |
Output is correct |
9 |
Correct |
457 ms |
11244 KB |
Output is correct |
10 |
Correct |
446 ms |
11496 KB |
Output is correct |
11 |
Correct |
715 ms |
12684 KB |
Output is correct |
12 |
Correct |
681 ms |
12768 KB |
Output is correct |
13 |
Correct |
709 ms |
12896 KB |
Output is correct |
14 |
Correct |
1043 ms |
14200 KB |
Output is correct |
15 |
Correct |
1025 ms |
14176 KB |
Output is correct |
16 |
Correct |
1098 ms |
14044 KB |
Output is correct |
17 |
Correct |
1125 ms |
13996 KB |
Output is correct |
18 |
Correct |
1004 ms |
13916 KB |
Output is correct |
19 |
Correct |
1014 ms |
14108 KB |
Output is correct |
20 |
Correct |
830 ms |
13280 KB |
Output is correct |
21 |
Correct |
809 ms |
13280 KB |
Output is correct |
22 |
Correct |
1069 ms |
14048 KB |
Output is correct |
23 |
Correct |
831 ms |
13292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
892 ms |
12776 KB |
Output is correct |
2 |
Correct |
868 ms |
12640 KB |
Output is correct |
3 |
Correct |
864 ms |
12644 KB |
Output is correct |
4 |
Correct |
851 ms |
12764 KB |
Output is correct |
5 |
Correct |
860 ms |
12636 KB |
Output is correct |
6 |
Correct |
1299 ms |
12488 KB |
Output is correct |
7 |
Correct |
1218 ms |
12340 KB |
Output is correct |
8 |
Correct |
1167 ms |
12420 KB |
Output is correct |
9 |
Correct |
156 ms |
8420 KB |
Output is correct |
10 |
Correct |
1004 ms |
12604 KB |
Output is correct |
11 |
Correct |
934 ms |
12700 KB |
Output is correct |
12 |
Correct |
605 ms |
11860 KB |
Output is correct |
13 |
Correct |
878 ms |
14308 KB |
Output is correct |
14 |
Correct |
903 ms |
13864 KB |
Output is correct |
15 |
Correct |
800 ms |
12332 KB |
Output is correct |
16 |
Correct |
1136 ms |
16720 KB |
Output is correct |
17 |
Correct |
988 ms |
19248 KB |
Output is correct |
18 |
Correct |
169 ms |
8548 KB |
Output is correct |
19 |
Correct |
1091 ms |
18220 KB |
Output is correct |
20 |
Correct |
942 ms |
17472 KB |
Output is correct |
21 |
Correct |
828 ms |
15588 KB |
Output is correct |
22 |
Correct |
641 ms |
12136 KB |
Output is correct |
23 |
Correct |
594 ms |
11608 KB |
Output is correct |
24 |
Correct |
846 ms |
18380 KB |
Output is correct |
25 |
Correct |
801 ms |
16056 KB |
Output is correct |
26 |
Correct |
1190 ms |
16232 KB |
Output is correct |
27 |
Correct |
1290 ms |
14556 KB |
Output is correct |
28 |
Correct |
1184 ms |
17432 KB |
Output is correct |
29 |
Correct |
927 ms |
14308 KB |
Output is correct |
30 |
Correct |
1184 ms |
12648 KB |
Output is correct |
31 |
Correct |
1215 ms |
12888 KB |
Output is correct |
32 |
Correct |
1203 ms |
12832 KB |
Output is correct |
33 |
Correct |
980 ms |
12612 KB |
Output is correct |
34 |
Correct |
1008 ms |
12636 KB |
Output is correct |
35 |
Correct |
1022 ms |
12776 KB |
Output is correct |
36 |
Correct |
794 ms |
12632 KB |
Output is correct |
37 |
Correct |
836 ms |
12648 KB |
Output is correct |
38 |
Correct |
857 ms |
12644 KB |
Output is correct |
39 |
Correct |
575 ms |
11664 KB |
Output is correct |
40 |
Correct |
609 ms |
11592 KB |
Output is correct |
41 |
Correct |
599 ms |
11664 KB |
Output is correct |
42 |
Correct |
784 ms |
14180 KB |
Output is correct |
43 |
Correct |
780 ms |
14180 KB |
Output is correct |
44 |
Correct |
771 ms |
14308 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 |
46 ms |
5216 KB |
Output is correct |
4 |
Correct |
31 ms |
4988 KB |
Output is correct |
5 |
Correct |
37 ms |
5112 KB |
Output is correct |
6 |
Correct |
35 ms |
5088 KB |
Output is correct |
7 |
Correct |
37 ms |
4992 KB |
Output is correct |
8 |
Correct |
36 ms |
5120 KB |
Output is correct |
9 |
Correct |
46 ms |
4992 KB |
Output is correct |
10 |
Correct |
36 ms |
5112 KB |
Output is correct |
11 |
Correct |
41 ms |
5120 KB |
Output is correct |
12 |
Correct |
39 ms |
5120 KB |
Output is correct |
13 |
Correct |
41 ms |
5108 KB |
Output is correct |
14 |
Correct |
39 ms |
5108 KB |
Output is correct |
15 |
Correct |
37 ms |
5120 KB |
Output is correct |
16 |
Correct |
38 ms |
4992 KB |
Output is correct |
17 |
Correct |
37 ms |
4992 KB |
Output is correct |
18 |
Correct |
892 ms |
12776 KB |
Output is correct |
19 |
Correct |
868 ms |
12640 KB |
Output is correct |
20 |
Correct |
864 ms |
12644 KB |
Output is correct |
21 |
Correct |
851 ms |
12764 KB |
Output is correct |
22 |
Correct |
860 ms |
12636 KB |
Output is correct |
23 |
Correct |
1299 ms |
12488 KB |
Output is correct |
24 |
Correct |
1218 ms |
12340 KB |
Output is correct |
25 |
Correct |
1167 ms |
12420 KB |
Output is correct |
26 |
Correct |
156 ms |
8420 KB |
Output is correct |
27 |
Correct |
1004 ms |
12604 KB |
Output is correct |
28 |
Correct |
934 ms |
12700 KB |
Output is correct |
29 |
Correct |
605 ms |
11860 KB |
Output is correct |
30 |
Correct |
878 ms |
14308 KB |
Output is correct |
31 |
Correct |
903 ms |
13864 KB |
Output is correct |
32 |
Correct |
800 ms |
12332 KB |
Output is correct |
33 |
Correct |
1136 ms |
16720 KB |
Output is correct |
34 |
Correct |
988 ms |
19248 KB |
Output is correct |
35 |
Correct |
169 ms |
8548 KB |
Output is correct |
36 |
Correct |
1091 ms |
18220 KB |
Output is correct |
37 |
Correct |
942 ms |
17472 KB |
Output is correct |
38 |
Correct |
828 ms |
15588 KB |
Output is correct |
39 |
Correct |
641 ms |
12136 KB |
Output is correct |
40 |
Correct |
594 ms |
11608 KB |
Output is correct |
41 |
Correct |
846 ms |
18380 KB |
Output is correct |
42 |
Correct |
801 ms |
16056 KB |
Output is correct |
43 |
Correct |
1144 ms |
13964 KB |
Output is correct |
44 |
Correct |
158 ms |
8676 KB |
Output is correct |
45 |
Correct |
170 ms |
10476 KB |
Output is correct |
46 |
Correct |
172 ms |
10600 KB |
Output is correct |
47 |
Correct |
1037 ms |
14204 KB |
Output is correct |
48 |
Correct |
1103 ms |
14048 KB |
Output is correct |
49 |
Correct |
1044 ms |
14308 KB |
Output is correct |
50 |
Correct |
452 ms |
11240 KB |
Output is correct |
51 |
Correct |
457 ms |
11244 KB |
Output is correct |
52 |
Correct |
446 ms |
11496 KB |
Output is correct |
53 |
Correct |
715 ms |
12684 KB |
Output is correct |
54 |
Correct |
681 ms |
12768 KB |
Output is correct |
55 |
Correct |
709 ms |
12896 KB |
Output is correct |
56 |
Correct |
1043 ms |
14200 KB |
Output is correct |
57 |
Correct |
1025 ms |
14176 KB |
Output is correct |
58 |
Correct |
1098 ms |
14044 KB |
Output is correct |
59 |
Correct |
1125 ms |
13996 KB |
Output is correct |
60 |
Correct |
1004 ms |
13916 KB |
Output is correct |
61 |
Correct |
1014 ms |
14108 KB |
Output is correct |
62 |
Correct |
830 ms |
13280 KB |
Output is correct |
63 |
Correct |
809 ms |
13280 KB |
Output is correct |
64 |
Correct |
1069 ms |
14048 KB |
Output is correct |
65 |
Correct |
831 ms |
13292 KB |
Output is correct |
66 |
Correct |
1190 ms |
16232 KB |
Output is correct |
67 |
Correct |
1290 ms |
14556 KB |
Output is correct |
68 |
Correct |
1184 ms |
17432 KB |
Output is correct |
69 |
Correct |
927 ms |
14308 KB |
Output is correct |
70 |
Correct |
1184 ms |
12648 KB |
Output is correct |
71 |
Correct |
1215 ms |
12888 KB |
Output is correct |
72 |
Correct |
1203 ms |
12832 KB |
Output is correct |
73 |
Correct |
980 ms |
12612 KB |
Output is correct |
74 |
Correct |
1008 ms |
12636 KB |
Output is correct |
75 |
Correct |
1022 ms |
12776 KB |
Output is correct |
76 |
Correct |
794 ms |
12632 KB |
Output is correct |
77 |
Correct |
836 ms |
12648 KB |
Output is correct |
78 |
Correct |
857 ms |
12644 KB |
Output is correct |
79 |
Correct |
575 ms |
11664 KB |
Output is correct |
80 |
Correct |
609 ms |
11592 KB |
Output is correct |
81 |
Correct |
599 ms |
11664 KB |
Output is correct |
82 |
Correct |
784 ms |
14180 KB |
Output is correct |
83 |
Correct |
780 ms |
14180 KB |
Output is correct |
84 |
Correct |
771 ms |
14308 KB |
Output is correct |
85 |
Correct |
1723 ms |
25156 KB |
Output is correct |
86 |
Correct |
200 ms |
10600 KB |
Output is correct |
87 |
Correct |
233 ms |
10720 KB |
Output is correct |
88 |
Correct |
1574 ms |
15840 KB |
Output is correct |
89 |
Correct |
1792 ms |
24816 KB |
Output is correct |
90 |
Correct |
1564 ms |
15328 KB |
Output is correct |
91 |
Correct |
956 ms |
12180 KB |
Output is correct |
92 |
Correct |
954 ms |
12212 KB |
Output is correct |
93 |
Correct |
1208 ms |
11740 KB |
Output is correct |
94 |
Correct |
1226 ms |
13660 KB |
Output is correct |
95 |
Correct |
1162 ms |
13908 KB |
Output is correct |
96 |
Correct |
1266 ms |
13148 KB |
Output is correct |
97 |
Correct |
1175 ms |
14096 KB |
Output is correct |
98 |
Correct |
1403 ms |
15544 KB |
Output is correct |
99 |
Correct |
1684 ms |
23700 KB |
Output is correct |
100 |
Correct |
1667 ms |
23920 KB |
Output is correct |
101 |
Correct |
1584 ms |
20568 KB |
Output is correct |
102 |
Correct |
1556 ms |
20892 KB |
Output is correct |
103 |
Correct |
1379 ms |
14712 KB |
Output is correct |
104 |
Correct |
1372 ms |
14692 KB |
Output is correct |
105 |
Correct |
1268 ms |
14696 KB |
Output is correct |
106 |
Correct |
1100 ms |
14696 KB |
Output is correct |
107 |
Correct |
959 ms |
13064 KB |
Output is correct |
108 |
Correct |
1788 ms |
19156 KB |
Output is correct |
109 |
Correct |
1361 ms |
13156 KB |
Output is correct |