#define _USE_MATH_DEFINES
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("rename-registers")
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <ctime>
#include <numeric>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
//#define int long long
#define uint unsigned long long
#define double long double
#define INF (int) 1e18 / 2
#define all(a) a.begin(), a.end()
#define debug(a) cerr << #a << ": " << a << endl
#define YES return (void) (cout << "Yes\n")
#define NO return (void) (cout << "No\n")
#define ls x << 1
#define rs x << 1 | 1
#ifdef JUSTNIK
#define start cout.setf(ios::fixed); cout.precision(10); int START = clock()
#define finish cout << "\ntime: " << (clock() - START) / (double)(CLOCKS_PER_SEC); return 0
#else
#define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false)
#define finish return 0
#endif
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5, sq = 750;
int n, m, q;
int p[N], sz[N];
int get(int i) { return i == p[i] ? i : get(p[i]); }
vector<int> st;
void merge(int i, int j) {
i = get(i);
j = get(j);
if (i == j) return;
if (sz[i] < sz[j]) swap(i, j);
sz[i] += sz[j];
p[j] = i;
st.push_back(j);
}
void rollback() {
while (!st.empty()) {
int j = st.back();
int i = p[j];
sz[i] -= sz[j];
p[j] = j;
st.pop_back();
}
}
int v[N], u[N], w[N];
int last[N];
int op[N], x[N], y[N];
int res[N];
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> v[i] >> u[i] >> w[i], last[i] = w[i];
cin >> q;
for (int i = 0; i < q; i++) cin >> op[i] >> x[i] >> y[i];
for (int l = 0; l < q; l += sq) {
iota(p, p + N, 0);
fill(sz, sz + N, 1);
int r = min(q, l + sq);
vector<int> used(m + 1);
vector<tuple<int, int, int>> ask;
for (int i = l; i < r; i++) {
if (op[i] == 1) {
used[x[i]] = 1;
} else {
ask.push_back({y[i], x[i], i});
}
}
vector<int> ids;
vector<tuple<int, int, int>> edges;
for (int i = 1; i <= m; i++) {
if (used[i]) ids.push_back(i);
else edges.push_back({w[i], v[i], u[i]});
}
sort(all(edges));
sort(all(ask));
reverse(all(ask));
for (auto[cur, s, i] : ask) {
for (int id : ids)
last[id] = w[id];
while (!edges.empty() && get<0>(edges.back()) >= cur)
merge(get<1>(edges.back()), get<2>(edges.back())), edges.pop_back();
st.clear();
for (int j = l; j < r; j++)
if (op[j] == 1 && j < i) last[x[j]] = y[j];
for (int id : ids)
if (last[id] >= cur) merge(v[id], u[id]);
res[i] = sz[get(s)];
rollback();
}
for (int i = l; i < r; i++)
if (op[i] == 1) w[x[i]] = y[i];
}
for (int i = 0; i < q; i++) if (op[i] == 2) cout << res[i] << '\n';
}
int32_t main() {
start;
solve();
finish;
}
/*
▄▀▀▀▄
▄███▀░◐░░░▌
▌░░░░░▐
▐░░░░░▐
▌░░░░░▐▄▄
▌░░░░▄▀▒▒▀▀▀▀▄
▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
▌▌░▌▌
▌▌░▌▌
▄▄▌▌▄▌▌ */
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
34 ms |
1328 KB |
Output is correct |
4 |
Correct |
17 ms |
1224 KB |
Output is correct |
5 |
Correct |
19 ms |
1288 KB |
Output is correct |
6 |
Correct |
18 ms |
1236 KB |
Output is correct |
7 |
Correct |
21 ms |
1236 KB |
Output is correct |
8 |
Correct |
20 ms |
1280 KB |
Output is correct |
9 |
Correct |
20 ms |
1284 KB |
Output is correct |
10 |
Correct |
20 ms |
1316 KB |
Output is correct |
11 |
Correct |
20 ms |
1300 KB |
Output is correct |
12 |
Correct |
22 ms |
1308 KB |
Output is correct |
13 |
Correct |
30 ms |
1312 KB |
Output is correct |
14 |
Correct |
27 ms |
1304 KB |
Output is correct |
15 |
Correct |
27 ms |
1316 KB |
Output is correct |
16 |
Correct |
23 ms |
1296 KB |
Output is correct |
17 |
Correct |
19 ms |
1300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1417 ms |
5084 KB |
Output is correct |
2 |
Correct |
1458 ms |
5048 KB |
Output is correct |
3 |
Correct |
1451 ms |
5012 KB |
Output is correct |
4 |
Correct |
1470 ms |
5220 KB |
Output is correct |
5 |
Correct |
1457 ms |
5100 KB |
Output is correct |
6 |
Correct |
1826 ms |
5308 KB |
Output is correct |
7 |
Correct |
1755 ms |
5324 KB |
Output is correct |
8 |
Correct |
1697 ms |
5256 KB |
Output is correct |
9 |
Correct |
120 ms |
2892 KB |
Output is correct |
10 |
Correct |
1267 ms |
5268 KB |
Output is correct |
11 |
Correct |
1290 ms |
5192 KB |
Output is correct |
12 |
Correct |
1188 ms |
5476 KB |
Output is correct |
13 |
Correct |
1137 ms |
5296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1051 ms |
4124 KB |
Output is correct |
2 |
Correct |
635 ms |
3128 KB |
Output is correct |
3 |
Correct |
1185 ms |
4160 KB |
Output is correct |
4 |
Correct |
1024 ms |
4072 KB |
Output is correct |
5 |
Correct |
92 ms |
2892 KB |
Output is correct |
6 |
Correct |
1098 ms |
4296 KB |
Output is correct |
7 |
Correct |
982 ms |
4132 KB |
Output is correct |
8 |
Correct |
863 ms |
4236 KB |
Output is correct |
9 |
Correct |
793 ms |
4280 KB |
Output is correct |
10 |
Correct |
744 ms |
4216 KB |
Output is correct |
11 |
Correct |
719 ms |
4160 KB |
Output is correct |
12 |
Correct |
674 ms |
4256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1805 ms |
7632 KB |
Output is correct |
2 |
Correct |
98 ms |
2876 KB |
Output is correct |
3 |
Correct |
187 ms |
6056 KB |
Output is correct |
4 |
Correct |
216 ms |
6056 KB |
Output is correct |
5 |
Correct |
2111 ms |
7600 KB |
Output is correct |
6 |
Correct |
1773 ms |
11400 KB |
Output is correct |
7 |
Correct |
2044 ms |
9780 KB |
Output is correct |
8 |
Correct |
899 ms |
7716 KB |
Output is correct |
9 |
Correct |
913 ms |
7860 KB |
Output is correct |
10 |
Correct |
910 ms |
7884 KB |
Output is correct |
11 |
Correct |
1413 ms |
9832 KB |
Output is correct |
12 |
Correct |
1360 ms |
9908 KB |
Output is correct |
13 |
Correct |
1454 ms |
9912 KB |
Output is correct |
14 |
Correct |
1986 ms |
10028 KB |
Output is correct |
15 |
Correct |
2049 ms |
9980 KB |
Output is correct |
16 |
Correct |
1842 ms |
11180 KB |
Output is correct |
17 |
Correct |
1873 ms |
11304 KB |
Output is correct |
18 |
Correct |
1803 ms |
11180 KB |
Output is correct |
19 |
Correct |
1802 ms |
11292 KB |
Output is correct |
20 |
Correct |
1560 ms |
10388 KB |
Output is correct |
21 |
Correct |
1537 ms |
10244 KB |
Output is correct |
22 |
Correct |
1731 ms |
11188 KB |
Output is correct |
23 |
Correct |
1661 ms |
9396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1417 ms |
5084 KB |
Output is correct |
2 |
Correct |
1458 ms |
5048 KB |
Output is correct |
3 |
Correct |
1451 ms |
5012 KB |
Output is correct |
4 |
Correct |
1470 ms |
5220 KB |
Output is correct |
5 |
Correct |
1457 ms |
5100 KB |
Output is correct |
6 |
Correct |
1826 ms |
5308 KB |
Output is correct |
7 |
Correct |
1755 ms |
5324 KB |
Output is correct |
8 |
Correct |
1697 ms |
5256 KB |
Output is correct |
9 |
Correct |
120 ms |
2892 KB |
Output is correct |
10 |
Correct |
1267 ms |
5268 KB |
Output is correct |
11 |
Correct |
1290 ms |
5192 KB |
Output is correct |
12 |
Correct |
1188 ms |
5476 KB |
Output is correct |
13 |
Correct |
1137 ms |
5296 KB |
Output is correct |
14 |
Correct |
1051 ms |
4124 KB |
Output is correct |
15 |
Correct |
635 ms |
3128 KB |
Output is correct |
16 |
Correct |
1185 ms |
4160 KB |
Output is correct |
17 |
Correct |
1024 ms |
4072 KB |
Output is correct |
18 |
Correct |
92 ms |
2892 KB |
Output is correct |
19 |
Correct |
1098 ms |
4296 KB |
Output is correct |
20 |
Correct |
982 ms |
4132 KB |
Output is correct |
21 |
Correct |
863 ms |
4236 KB |
Output is correct |
22 |
Correct |
793 ms |
4280 KB |
Output is correct |
23 |
Correct |
744 ms |
4216 KB |
Output is correct |
24 |
Correct |
719 ms |
4160 KB |
Output is correct |
25 |
Correct |
674 ms |
4256 KB |
Output is correct |
26 |
Correct |
1315 ms |
5088 KB |
Output is correct |
27 |
Correct |
1597 ms |
5220 KB |
Output is correct |
28 |
Correct |
1415 ms |
5188 KB |
Output is correct |
29 |
Correct |
1117 ms |
5144 KB |
Output is correct |
30 |
Correct |
1511 ms |
5252 KB |
Output is correct |
31 |
Correct |
1516 ms |
5320 KB |
Output is correct |
32 |
Correct |
1539 ms |
5328 KB |
Output is correct |
33 |
Correct |
1340 ms |
5172 KB |
Output is correct |
34 |
Correct |
1381 ms |
5272 KB |
Output is correct |
35 |
Correct |
1363 ms |
5452 KB |
Output is correct |
36 |
Correct |
1182 ms |
5132 KB |
Output is correct |
37 |
Correct |
1124 ms |
5292 KB |
Output is correct |
38 |
Correct |
1121 ms |
5288 KB |
Output is correct |
39 |
Correct |
980 ms |
5164 KB |
Output is correct |
40 |
Correct |
986 ms |
5344 KB |
Output is correct |
41 |
Correct |
978 ms |
5056 KB |
Output is correct |
42 |
Correct |
905 ms |
5240 KB |
Output is correct |
43 |
Correct |
936 ms |
5088 KB |
Output is correct |
44 |
Correct |
901 ms |
5352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
34 ms |
1328 KB |
Output is correct |
4 |
Correct |
17 ms |
1224 KB |
Output is correct |
5 |
Correct |
19 ms |
1288 KB |
Output is correct |
6 |
Correct |
18 ms |
1236 KB |
Output is correct |
7 |
Correct |
21 ms |
1236 KB |
Output is correct |
8 |
Correct |
20 ms |
1280 KB |
Output is correct |
9 |
Correct |
20 ms |
1284 KB |
Output is correct |
10 |
Correct |
20 ms |
1316 KB |
Output is correct |
11 |
Correct |
20 ms |
1300 KB |
Output is correct |
12 |
Correct |
22 ms |
1308 KB |
Output is correct |
13 |
Correct |
30 ms |
1312 KB |
Output is correct |
14 |
Correct |
27 ms |
1304 KB |
Output is correct |
15 |
Correct |
27 ms |
1316 KB |
Output is correct |
16 |
Correct |
23 ms |
1296 KB |
Output is correct |
17 |
Correct |
19 ms |
1300 KB |
Output is correct |
18 |
Correct |
1417 ms |
5084 KB |
Output is correct |
19 |
Correct |
1458 ms |
5048 KB |
Output is correct |
20 |
Correct |
1451 ms |
5012 KB |
Output is correct |
21 |
Correct |
1470 ms |
5220 KB |
Output is correct |
22 |
Correct |
1457 ms |
5100 KB |
Output is correct |
23 |
Correct |
1826 ms |
5308 KB |
Output is correct |
24 |
Correct |
1755 ms |
5324 KB |
Output is correct |
25 |
Correct |
1697 ms |
5256 KB |
Output is correct |
26 |
Correct |
120 ms |
2892 KB |
Output is correct |
27 |
Correct |
1267 ms |
5268 KB |
Output is correct |
28 |
Correct |
1290 ms |
5192 KB |
Output is correct |
29 |
Correct |
1188 ms |
5476 KB |
Output is correct |
30 |
Correct |
1137 ms |
5296 KB |
Output is correct |
31 |
Correct |
1051 ms |
4124 KB |
Output is correct |
32 |
Correct |
635 ms |
3128 KB |
Output is correct |
33 |
Correct |
1185 ms |
4160 KB |
Output is correct |
34 |
Correct |
1024 ms |
4072 KB |
Output is correct |
35 |
Correct |
92 ms |
2892 KB |
Output is correct |
36 |
Correct |
1098 ms |
4296 KB |
Output is correct |
37 |
Correct |
982 ms |
4132 KB |
Output is correct |
38 |
Correct |
863 ms |
4236 KB |
Output is correct |
39 |
Correct |
793 ms |
4280 KB |
Output is correct |
40 |
Correct |
744 ms |
4216 KB |
Output is correct |
41 |
Correct |
719 ms |
4160 KB |
Output is correct |
42 |
Correct |
674 ms |
4256 KB |
Output is correct |
43 |
Correct |
1805 ms |
7632 KB |
Output is correct |
44 |
Correct |
98 ms |
2876 KB |
Output is correct |
45 |
Correct |
187 ms |
6056 KB |
Output is correct |
46 |
Correct |
216 ms |
6056 KB |
Output is correct |
47 |
Correct |
2111 ms |
7600 KB |
Output is correct |
48 |
Correct |
1773 ms |
11400 KB |
Output is correct |
49 |
Correct |
2044 ms |
9780 KB |
Output is correct |
50 |
Correct |
899 ms |
7716 KB |
Output is correct |
51 |
Correct |
913 ms |
7860 KB |
Output is correct |
52 |
Correct |
910 ms |
7884 KB |
Output is correct |
53 |
Correct |
1413 ms |
9832 KB |
Output is correct |
54 |
Correct |
1360 ms |
9908 KB |
Output is correct |
55 |
Correct |
1454 ms |
9912 KB |
Output is correct |
56 |
Correct |
1986 ms |
10028 KB |
Output is correct |
57 |
Correct |
2049 ms |
9980 KB |
Output is correct |
58 |
Correct |
1842 ms |
11180 KB |
Output is correct |
59 |
Correct |
1873 ms |
11304 KB |
Output is correct |
60 |
Correct |
1803 ms |
11180 KB |
Output is correct |
61 |
Correct |
1802 ms |
11292 KB |
Output is correct |
62 |
Correct |
1560 ms |
10388 KB |
Output is correct |
63 |
Correct |
1537 ms |
10244 KB |
Output is correct |
64 |
Correct |
1731 ms |
11188 KB |
Output is correct |
65 |
Correct |
1661 ms |
9396 KB |
Output is correct |
66 |
Correct |
1315 ms |
5088 KB |
Output is correct |
67 |
Correct |
1597 ms |
5220 KB |
Output is correct |
68 |
Correct |
1415 ms |
5188 KB |
Output is correct |
69 |
Correct |
1117 ms |
5144 KB |
Output is correct |
70 |
Correct |
1511 ms |
5252 KB |
Output is correct |
71 |
Correct |
1516 ms |
5320 KB |
Output is correct |
72 |
Correct |
1539 ms |
5328 KB |
Output is correct |
73 |
Correct |
1340 ms |
5172 KB |
Output is correct |
74 |
Correct |
1381 ms |
5272 KB |
Output is correct |
75 |
Correct |
1363 ms |
5452 KB |
Output is correct |
76 |
Correct |
1182 ms |
5132 KB |
Output is correct |
77 |
Correct |
1124 ms |
5292 KB |
Output is correct |
78 |
Correct |
1121 ms |
5288 KB |
Output is correct |
79 |
Correct |
980 ms |
5164 KB |
Output is correct |
80 |
Correct |
986 ms |
5344 KB |
Output is correct |
81 |
Correct |
978 ms |
5056 KB |
Output is correct |
82 |
Correct |
905 ms |
5240 KB |
Output is correct |
83 |
Correct |
936 ms |
5088 KB |
Output is correct |
84 |
Correct |
901 ms |
5352 KB |
Output is correct |
85 |
Correct |
2141 ms |
11584 KB |
Output is correct |
86 |
Correct |
221 ms |
7800 KB |
Output is correct |
87 |
Correct |
218 ms |
7904 KB |
Output is correct |
88 |
Correct |
2358 ms |
9812 KB |
Output is correct |
89 |
Correct |
2130 ms |
11472 KB |
Output is correct |
90 |
Correct |
2312 ms |
10004 KB |
Output is correct |
91 |
Correct |
1387 ms |
7760 KB |
Output is correct |
92 |
Correct |
1419 ms |
8144 KB |
Output is correct |
93 |
Correct |
1766 ms |
7908 KB |
Output is correct |
94 |
Correct |
1779 ms |
10116 KB |
Output is correct |
95 |
Correct |
1741 ms |
10156 KB |
Output is correct |
96 |
Correct |
1882 ms |
10188 KB |
Output is correct |
97 |
Correct |
2091 ms |
9892 KB |
Output is correct |
98 |
Correct |
2088 ms |
9928 KB |
Output is correct |
99 |
Correct |
2112 ms |
11268 KB |
Output is correct |
100 |
Correct |
2145 ms |
11284 KB |
Output is correct |
101 |
Correct |
2155 ms |
11392 KB |
Output is correct |
102 |
Correct |
2154 ms |
11276 KB |
Output is correct |
103 |
Correct |
2064 ms |
10680 KB |
Output is correct |
104 |
Correct |
2062 ms |
10640 KB |
Output is correct |
105 |
Correct |
1677 ms |
10688 KB |
Output is correct |
106 |
Correct |
1414 ms |
10556 KB |
Output is correct |
107 |
Correct |
1655 ms |
10360 KB |
Output is correct |
108 |
Correct |
2055 ms |
11408 KB |
Output is correct |
109 |
Correct |
2033 ms |
9328 KB |
Output is correct |