// ~ Be Name Khoda ~
#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 1e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int ssq = 500;
const ll inf = 1e18;
int a[maxn5], b[maxn5], c[maxn5], ty[maxn5], x[maxn5];
int y[maxn5], inded[maxn5], indqu[maxn5], par[maxn5];
int ver[maxn5], q[maxn5], out[maxn5], last[maxn5];
bool dis[maxn5], seen[maxn5], mark[maxn5];
vector <int> adj[maxn5], wi;
int plc[maxn5], toadd[maxn5], cnt[maxn5 << 1];
inline bool cmp(int i, int j){return y[i] < y[j];}
int get_par(int a){return par[a] < 0 ? a : par[a] = get_par(par[a]);}
inline int bfs(int sr){
int l = 0, r = 1, ret = 0;
dis[sr] = true;
q[0] = sr;
while(l < r){
int v = q[l++];
ret -= par[v];
for(auto u : adj[v]){
if(!dis[u]){
q[r++] = u;
dis[u] = true;
}
}
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i];
a[i]--; b[i]--;
wi.pb(c[i]);
}
int q; cin >> q;
for(int i = 0; i < q; i++){
cin >> ty[i] >> x[i] >> y[i];
x[i]--;
if(ty[i] == 1)
wi.pb(y[i]);
}
sort(all(wi));
wi.resize(unique(all(wi)) - wi.begin());
for(int i = 0; i < m; i++)
inded[i] = lower_bound(all(wi), c[i]) - wi.begin();
for(int i = 0; i < q; i++) if(ty[i] == 1)
indqu[i] = lower_bound(all(wi), y[i]) - wi.begin();
for(int bl = 0; bl < q; bl += ssq){
memset(mark, false, sizeof mark);
memset(last, -1, sizeof last);
memset(par, -1, sizeof par);
memset(cnt, 0, sizeof cnt);
int verind = 0;
for(int i = bl; i < min(q, bl + ssq); i++){
if(ty[i] == 1)
mark[x[i]] = true;
else
ver[verind++] = i;
}
sort(ver, ver + verind, cmp);
verind--;
int edind = 0;
for(int i = bl - 1; i >= 0; i--) if(ty[i] == 1){
if(!mark[x[i]]){
mark[x[i]] = true;
cnt[indqu[i]]++;
last[x[i]] = y[i];
toadd[edind++] = i + 1;
}
else if(last[x[i]] == -1)
last[x[i]] = y[i];
}
for(int i = 0; i < m; i++){
if(!mark[i]){
cnt[inded[i]]++;
toadd[edind++] = -i;
last[i] = c[i];
}
else if(last[i] == -1)
last[i] = c[i];
}
for(int i = 1; i < wi.size(); i++)
cnt[i] += cnt[i - 1];
for(int i = 0; i < edind; i++){
if(toadd[i] <= 0)
plc[--cnt[inded[-toadd[i]]]] = toadd[i];
else
plc[--cnt[indqu[toadd[i] - 1]]] = toadd[i];
}
while(verind >= 0 && edind--){
int edd = -plc[edind];
if(edd < 0)
edd = x[edd * -1 - 1];
while(verind >= 0 && y[ver[verind]] > last[edd]){
int id = ver[verind--];
for(int j = id; j >= bl; j--) if(ty[j] == 1 && !seen[x[j]]){
seen[x[j]] = true;
if(y[j] < y[id])
continue;
adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
}
for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
}
out[id] = bfs(get_par(x[id]));
for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
adj[get_par(a[x[j]])].clear();
adj[get_par(b[x[j]])].clear();
dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
}
for(int j = id; j >= bl; j--) if(ty[j] == 1){
seen[x[j]] = false;
dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
adj[get_par(a[x[j]])].clear();
adj[get_par(b[x[j]])].clear();
}
dis[get_par(x[id])] = false;
}
int u = get_par(a[edd]);
int v = get_par(b[edd]);
if(u == v)
continue;
if(par[u] > par[v])
swap(u, v);
par[u] += par[v];
par[v] = u;
}
while(verind >= 0){
int id = ver[verind--];
for(int j = id; j >= bl; j--) if(ty[j] == 1 && !seen[x[j]]){
seen[x[j]] = true;
if(y[j] < y[id])
continue;
adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
}
for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
}
out[id] = bfs(get_par(x[id]));
for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
adj[get_par(a[x[j]])].clear();
adj[get_par(b[x[j]])].clear();
dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
}
for(int j = id; j >= bl; j--) if(ty[j] == 1){
seen[x[j]] = false;
dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
adj[get_par(a[x[j]])].clear();
adj[get_par(b[x[j]])].clear();
}
dis[get_par(x[id])] = false;
}
}
for(int i = 0; i < q; i++) if(ty[i] == 2)
cout << out[i] << '\n';
}
// Heib!
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 1; i < wi.size(); i++)
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4308 KB |
Output is correct |
2 |
Correct |
2 ms |
4308 KB |
Output is correct |
3 |
Correct |
64 ms |
4864 KB |
Output is correct |
4 |
Correct |
16 ms |
4584 KB |
Output is correct |
5 |
Correct |
49 ms |
4752 KB |
Output is correct |
6 |
Correct |
42 ms |
4768 KB |
Output is correct |
7 |
Correct |
46 ms |
4692 KB |
Output is correct |
8 |
Correct |
45 ms |
4768 KB |
Output is correct |
9 |
Correct |
50 ms |
4692 KB |
Output is correct |
10 |
Correct |
45 ms |
4752 KB |
Output is correct |
11 |
Correct |
44 ms |
4692 KB |
Output is correct |
12 |
Correct |
48 ms |
4760 KB |
Output is correct |
13 |
Correct |
56 ms |
4752 KB |
Output is correct |
14 |
Correct |
51 ms |
4780 KB |
Output is correct |
15 |
Correct |
55 ms |
4764 KB |
Output is correct |
16 |
Correct |
46 ms |
4612 KB |
Output is correct |
17 |
Correct |
47 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1751 ms |
9824 KB |
Output is correct |
2 |
Correct |
1747 ms |
9724 KB |
Output is correct |
3 |
Correct |
1761 ms |
9720 KB |
Output is correct |
4 |
Correct |
1767 ms |
9820 KB |
Output is correct |
5 |
Correct |
1748 ms |
9680 KB |
Output is correct |
6 |
Correct |
2454 ms |
9072 KB |
Output is correct |
7 |
Correct |
2363 ms |
8920 KB |
Output is correct |
8 |
Correct |
2341 ms |
8924 KB |
Output is correct |
9 |
Correct |
148 ms |
6444 KB |
Output is correct |
10 |
Correct |
1726 ms |
9816 KB |
Output is correct |
11 |
Correct |
1582 ms |
9904 KB |
Output is correct |
12 |
Correct |
2321 ms |
8656 KB |
Output is correct |
13 |
Correct |
1258 ms |
9136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1439 ms |
8988 KB |
Output is correct |
2 |
Correct |
1210 ms |
7536 KB |
Output is correct |
3 |
Correct |
1712 ms |
9032 KB |
Output is correct |
4 |
Correct |
1429 ms |
8804 KB |
Output is correct |
5 |
Correct |
138 ms |
6360 KB |
Output is correct |
6 |
Correct |
1589 ms |
8828 KB |
Output is correct |
7 |
Correct |
1332 ms |
9032 KB |
Output is correct |
8 |
Correct |
1189 ms |
8760 KB |
Output is correct |
9 |
Correct |
1623 ms |
8376 KB |
Output is correct |
10 |
Correct |
1319 ms |
8220 KB |
Output is correct |
11 |
Correct |
867 ms |
8828 KB |
Output is correct |
12 |
Correct |
808 ms |
8908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2393 ms |
9764 KB |
Output is correct |
2 |
Correct |
138 ms |
6340 KB |
Output is correct |
3 |
Correct |
221 ms |
7660 KB |
Output is correct |
4 |
Correct |
195 ms |
7600 KB |
Output is correct |
5 |
Correct |
1885 ms |
9688 KB |
Output is correct |
6 |
Correct |
2378 ms |
9572 KB |
Output is correct |
7 |
Correct |
1914 ms |
9656 KB |
Output is correct |
8 |
Correct |
1720 ms |
8272 KB |
Output is correct |
9 |
Correct |
1674 ms |
8396 KB |
Output is correct |
10 |
Correct |
2472 ms |
8272 KB |
Output is correct |
11 |
Correct |
2226 ms |
9128 KB |
Output is correct |
12 |
Correct |
2163 ms |
9068 KB |
Output is correct |
13 |
Correct |
2748 ms |
9052 KB |
Output is correct |
14 |
Correct |
2072 ms |
9552 KB |
Output is correct |
15 |
Correct |
1942 ms |
9676 KB |
Output is correct |
16 |
Correct |
2521 ms |
9748 KB |
Output is correct |
17 |
Correct |
2492 ms |
9652 KB |
Output is correct |
18 |
Correct |
2520 ms |
9564 KB |
Output is correct |
19 |
Correct |
2506 ms |
9624 KB |
Output is correct |
20 |
Correct |
2883 ms |
9144 KB |
Output is correct |
21 |
Correct |
2875 ms |
9156 KB |
Output is correct |
22 |
Correct |
2868 ms |
9496 KB |
Output is correct |
23 |
Correct |
2405 ms |
8984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1751 ms |
9824 KB |
Output is correct |
2 |
Correct |
1747 ms |
9724 KB |
Output is correct |
3 |
Correct |
1761 ms |
9720 KB |
Output is correct |
4 |
Correct |
1767 ms |
9820 KB |
Output is correct |
5 |
Correct |
1748 ms |
9680 KB |
Output is correct |
6 |
Correct |
2454 ms |
9072 KB |
Output is correct |
7 |
Correct |
2363 ms |
8920 KB |
Output is correct |
8 |
Correct |
2341 ms |
8924 KB |
Output is correct |
9 |
Correct |
148 ms |
6444 KB |
Output is correct |
10 |
Correct |
1726 ms |
9816 KB |
Output is correct |
11 |
Correct |
1582 ms |
9904 KB |
Output is correct |
12 |
Correct |
2321 ms |
8656 KB |
Output is correct |
13 |
Correct |
1258 ms |
9136 KB |
Output is correct |
14 |
Correct |
1439 ms |
8988 KB |
Output is correct |
15 |
Correct |
1210 ms |
7536 KB |
Output is correct |
16 |
Correct |
1712 ms |
9032 KB |
Output is correct |
17 |
Correct |
1429 ms |
8804 KB |
Output is correct |
18 |
Correct |
138 ms |
6360 KB |
Output is correct |
19 |
Correct |
1589 ms |
8828 KB |
Output is correct |
20 |
Correct |
1332 ms |
9032 KB |
Output is correct |
21 |
Correct |
1189 ms |
8760 KB |
Output is correct |
22 |
Correct |
1623 ms |
8376 KB |
Output is correct |
23 |
Correct |
1319 ms |
8220 KB |
Output is correct |
24 |
Correct |
867 ms |
8828 KB |
Output is correct |
25 |
Correct |
808 ms |
8908 KB |
Output is correct |
26 |
Correct |
1761 ms |
9768 KB |
Output is correct |
27 |
Correct |
2146 ms |
9876 KB |
Output is correct |
28 |
Correct |
1816 ms |
9800 KB |
Output is correct |
29 |
Correct |
1348 ms |
9844 KB |
Output is correct |
30 |
Correct |
2128 ms |
10020 KB |
Output is correct |
31 |
Correct |
2155 ms |
9896 KB |
Output is correct |
32 |
Correct |
2147 ms |
9992 KB |
Output is correct |
33 |
Correct |
1844 ms |
9888 KB |
Output is correct |
34 |
Correct |
1837 ms |
9820 KB |
Output is correct |
35 |
Correct |
1867 ms |
10032 KB |
Output is correct |
36 |
Correct |
1431 ms |
9788 KB |
Output is correct |
37 |
Correct |
1424 ms |
9892 KB |
Output is correct |
38 |
Correct |
1420 ms |
9752 KB |
Output is correct |
39 |
Correct |
1315 ms |
9372 KB |
Output is correct |
40 |
Correct |
1291 ms |
9220 KB |
Output is correct |
41 |
Correct |
1278 ms |
9124 KB |
Output is correct |
42 |
Correct |
1042 ms |
9992 KB |
Output is correct |
43 |
Correct |
1049 ms |
9960 KB |
Output is correct |
44 |
Correct |
1034 ms |
10100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4308 KB |
Output is correct |
2 |
Correct |
2 ms |
4308 KB |
Output is correct |
3 |
Correct |
64 ms |
4864 KB |
Output is correct |
4 |
Correct |
16 ms |
4584 KB |
Output is correct |
5 |
Correct |
49 ms |
4752 KB |
Output is correct |
6 |
Correct |
42 ms |
4768 KB |
Output is correct |
7 |
Correct |
46 ms |
4692 KB |
Output is correct |
8 |
Correct |
45 ms |
4768 KB |
Output is correct |
9 |
Correct |
50 ms |
4692 KB |
Output is correct |
10 |
Correct |
45 ms |
4752 KB |
Output is correct |
11 |
Correct |
44 ms |
4692 KB |
Output is correct |
12 |
Correct |
48 ms |
4760 KB |
Output is correct |
13 |
Correct |
56 ms |
4752 KB |
Output is correct |
14 |
Correct |
51 ms |
4780 KB |
Output is correct |
15 |
Correct |
55 ms |
4764 KB |
Output is correct |
16 |
Correct |
46 ms |
4612 KB |
Output is correct |
17 |
Correct |
47 ms |
4700 KB |
Output is correct |
18 |
Correct |
1751 ms |
9824 KB |
Output is correct |
19 |
Correct |
1747 ms |
9724 KB |
Output is correct |
20 |
Correct |
1761 ms |
9720 KB |
Output is correct |
21 |
Correct |
1767 ms |
9820 KB |
Output is correct |
22 |
Correct |
1748 ms |
9680 KB |
Output is correct |
23 |
Correct |
2454 ms |
9072 KB |
Output is correct |
24 |
Correct |
2363 ms |
8920 KB |
Output is correct |
25 |
Correct |
2341 ms |
8924 KB |
Output is correct |
26 |
Correct |
148 ms |
6444 KB |
Output is correct |
27 |
Correct |
1726 ms |
9816 KB |
Output is correct |
28 |
Correct |
1582 ms |
9904 KB |
Output is correct |
29 |
Correct |
2321 ms |
8656 KB |
Output is correct |
30 |
Correct |
1258 ms |
9136 KB |
Output is correct |
31 |
Correct |
1439 ms |
8988 KB |
Output is correct |
32 |
Correct |
1210 ms |
7536 KB |
Output is correct |
33 |
Correct |
1712 ms |
9032 KB |
Output is correct |
34 |
Correct |
1429 ms |
8804 KB |
Output is correct |
35 |
Correct |
138 ms |
6360 KB |
Output is correct |
36 |
Correct |
1589 ms |
8828 KB |
Output is correct |
37 |
Correct |
1332 ms |
9032 KB |
Output is correct |
38 |
Correct |
1189 ms |
8760 KB |
Output is correct |
39 |
Correct |
1623 ms |
8376 KB |
Output is correct |
40 |
Correct |
1319 ms |
8220 KB |
Output is correct |
41 |
Correct |
867 ms |
8828 KB |
Output is correct |
42 |
Correct |
808 ms |
8908 KB |
Output is correct |
43 |
Correct |
2393 ms |
9764 KB |
Output is correct |
44 |
Correct |
138 ms |
6340 KB |
Output is correct |
45 |
Correct |
221 ms |
7660 KB |
Output is correct |
46 |
Correct |
195 ms |
7600 KB |
Output is correct |
47 |
Correct |
1885 ms |
9688 KB |
Output is correct |
48 |
Correct |
2378 ms |
9572 KB |
Output is correct |
49 |
Correct |
1914 ms |
9656 KB |
Output is correct |
50 |
Correct |
1720 ms |
8272 KB |
Output is correct |
51 |
Correct |
1674 ms |
8396 KB |
Output is correct |
52 |
Correct |
2472 ms |
8272 KB |
Output is correct |
53 |
Correct |
2226 ms |
9128 KB |
Output is correct |
54 |
Correct |
2163 ms |
9068 KB |
Output is correct |
55 |
Correct |
2748 ms |
9052 KB |
Output is correct |
56 |
Correct |
2072 ms |
9552 KB |
Output is correct |
57 |
Correct |
1942 ms |
9676 KB |
Output is correct |
58 |
Correct |
2521 ms |
9748 KB |
Output is correct |
59 |
Correct |
2492 ms |
9652 KB |
Output is correct |
60 |
Correct |
2520 ms |
9564 KB |
Output is correct |
61 |
Correct |
2506 ms |
9624 KB |
Output is correct |
62 |
Correct |
2883 ms |
9144 KB |
Output is correct |
63 |
Correct |
2875 ms |
9156 KB |
Output is correct |
64 |
Correct |
2868 ms |
9496 KB |
Output is correct |
65 |
Correct |
2405 ms |
8984 KB |
Output is correct |
66 |
Correct |
1761 ms |
9768 KB |
Output is correct |
67 |
Correct |
2146 ms |
9876 KB |
Output is correct |
68 |
Correct |
1816 ms |
9800 KB |
Output is correct |
69 |
Correct |
1348 ms |
9844 KB |
Output is correct |
70 |
Correct |
2128 ms |
10020 KB |
Output is correct |
71 |
Correct |
2155 ms |
9896 KB |
Output is correct |
72 |
Correct |
2147 ms |
9992 KB |
Output is correct |
73 |
Correct |
1844 ms |
9888 KB |
Output is correct |
74 |
Correct |
1837 ms |
9820 KB |
Output is correct |
75 |
Correct |
1867 ms |
10032 KB |
Output is correct |
76 |
Correct |
1431 ms |
9788 KB |
Output is correct |
77 |
Correct |
1424 ms |
9892 KB |
Output is correct |
78 |
Correct |
1420 ms |
9752 KB |
Output is correct |
79 |
Correct |
1315 ms |
9372 KB |
Output is correct |
80 |
Correct |
1291 ms |
9220 KB |
Output is correct |
81 |
Correct |
1278 ms |
9124 KB |
Output is correct |
82 |
Correct |
1042 ms |
9992 KB |
Output is correct |
83 |
Correct |
1049 ms |
9960 KB |
Output is correct |
84 |
Correct |
1034 ms |
10100 KB |
Output is correct |
85 |
Correct |
2570 ms |
10800 KB |
Output is correct |
86 |
Correct |
227 ms |
9372 KB |
Output is correct |
87 |
Correct |
183 ms |
9484 KB |
Output is correct |
88 |
Correct |
1926 ms |
12936 KB |
Output is correct |
89 |
Correct |
2574 ms |
14560 KB |
Output is correct |
90 |
Correct |
1906 ms |
12632 KB |
Output is correct |
91 |
Correct |
1908 ms |
12244 KB |
Output is correct |
92 |
Correct |
1858 ms |
12192 KB |
Output is correct |
93 |
Correct |
2426 ms |
11380 KB |
Output is correct |
94 |
Correct |
2368 ms |
13560 KB |
Output is correct |
95 |
Correct |
2315 ms |
13548 KB |
Output is correct |
96 |
Correct |
2598 ms |
12504 KB |
Output is correct |
97 |
Correct |
1995 ms |
12224 KB |
Output is correct |
98 |
Correct |
1236 ms |
12860 KB |
Output is correct |
99 |
Correct |
2718 ms |
14504 KB |
Output is correct |
100 |
Correct |
2680 ms |
14504 KB |
Output is correct |
101 |
Correct |
2706 ms |
14488 KB |
Output is correct |
102 |
Correct |
2694 ms |
14508 KB |
Output is correct |
103 |
Correct |
2780 ms |
12660 KB |
Output is correct |
104 |
Correct |
2767 ms |
12992 KB |
Output is correct |
105 |
Correct |
1839 ms |
13196 KB |
Output is correct |
106 |
Correct |
1578 ms |
12772 KB |
Output is correct |
107 |
Correct |
2898 ms |
12548 KB |
Output is correct |
108 |
Correct |
2784 ms |
13416 KB |
Output is correct |
109 |
Correct |
2219 ms |
11408 KB |
Output is correct |