#include <bits/stdc++.h>
#define se second
#define fs first
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 500;
const int INF = 2e9 + 7;
const int BASE = 137;
struct Edge {
int u, v, id, w;
Edge (int u = 0, int v = 0, int id = 0, int w = 0) : u(u), v(v), id(id), w(w) {};
};
struct Edge2 {
int u, v, w;
};
struct Query {
int typ, u, v;
};
struct Data {
int id, u, v;
};
struct Disjoin_Set_Union {
struct State {
int labu, labv, szu, szv;
State (int labu = 0, int labv= 0, int szu = 0, int szv= 0) : labu(labu), labv(labv), szu(szu), szv(szv) {};
};
int lab[N], sz[N];
stack<State> op;
void init (int n) {
rep (i, 1, n) lab[i] = i, sz[i] = 1;
stack<State> ().swap(op);
}
int Find (int u) {
if (u == lab[u]) return u;
return Find(lab[u]);
}
bool Join (int u, int v) {
u = Find(u);
v = Find(v);
if (u == v) return 0;
op.push(State(u, v, sz[u], sz[v]));
if (sz[u] < sz[v]) swap(u, v);
lab[v] = u;
sz[u] += sz[v];
return 1;
}
void roll_back() {
assert(!op.empty());
State cur = op.top();
lab[cur.labu] = cur.labu;
lab[cur.labv] = cur.labv;
sz[cur.labu] = cur.szu;
sz[cur.labv] = cur.szv;
op.pop();
}
int get (int u) {
return sz[Find(u)];
}
}DSU;
int n, m, Q;
int a[N];
Edge2 ini_edge[N];
Query qr[N];
bool changed[N];
bool dd[N];
void solution () {
cin >> n >> m;
rep (i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
ini_edge[i] = {u, v, w};
}
cin >> Q;
rep (i, 1, Q) {
cin >> qr[i].typ >> qr[i].u >> qr[i].v;
}
vector<int> Answer(Q + 1, 0);
for (int qi = 1; qi <= Q; qi += szBL) {
static vector<Data> Ans; vector<Data> ().swap(Ans);
static vector<Data> Ask; vector<Data> ().swap(Ask);
static vector<Edge> edges; vector<Edge> ().swap(edges);
DSU.init(n);
rep (i, 1, m) changed[i] = 0, edges.pb({ini_edge[i].u, ini_edge[i].v, i, ini_edge[i].w});
int L = qi, R = min(Q, qi + szBL - 1);
rep (i, L, R) {
if (qr[i].typ == 1) {
Ask.push_back({i, qr[i].u, qr[i].v});
changed[qr[i].u] = 1;
}
else Ans.push_back({i, qr[i].u, qr[i].v});
}
sort (ALL(edges), [] (Edge A, Edge B) { return A.w > B.w; });
sort (ALL(Ans), [] (Data A, Data B) { return A.v > B.v || (A.v == B.v && A.id < B.id); });
int Eptr = 0;
rep (i, 0, SZ(Ans) - 1) {
int cur_values = Ans[i].v;
while (Eptr < m && edges[Eptr].w >= cur_values) {
if (changed[edges[Eptr].id] == 0) {
DSU.Join(edges[Eptr].u, edges[Eptr].v);
// cout << edges[Eptr].u <<" "<<edges[Eptr].v <<" hi\n";
}
++Eptr;
}
static vector<Data> vec;
vec = {Ans[i]};
while (i < SZ(Ans) - 1 && Ans[i].v == Ans[i + 1].v) vec.push_back(Ans[i + 1]), ++i;
int rightmost = -1;
rep (j, 0, SZ(vec) - 1) {
// cout << vec[j].id <<"jijoi\n";
while (rightmost < SZ(Ask) - 1 && Ask[rightmost + 1].id < vec[j].id) ++rightmost;
int num_roll = 0;
reb (k, rightmost, 0) {
if (dd[Ask[k].u]) continue;
if (Ask[k].v >= vec[j].v) {
num_roll += DSU.Join(ini_edge[Ask[k].u].u, ini_edge[Ask[k].u].v);
}
dd[Ask[k].u] = 1;
}
rep (k, rightmost + 1, SZ(Ask) - 1) {
if (!dd[Ask[k].u] && ini_edge[Ask[k].u].w >= vec[j].v) {
num_roll += DSU.Join (ini_edge[Ask[k].u].u, ini_edge[Ask[k].u].v);
// cout << vec[j].id<<" JOIN: "<<ini_edge[Ask[k].u].u<<" "<<ini_edge[Ask[k].u].v <<"\n";
}
}
Answer[vec[j].id] = DSU.get(vec[j].u);
while (num_roll--) DSU.roll_back();
rep (k, 0, rightmost) dd[Ask[k].u] = 0;
}
}
///update lastest_values to Edge.w
rep (i, L, R) if (qr[i].typ == 1) ini_edge[qr[i].u].w = qr[i].v;
}
rep (i, 1, Q) if (qr[i].typ == 2) cout << Answer[i] <<"\n";
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main() {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
12 ms |
2692 KB |
Output is correct |
4 |
Correct |
3 ms |
2652 KB |
Output is correct |
5 |
Correct |
14 ms |
2652 KB |
Output is correct |
6 |
Correct |
11 ms |
2640 KB |
Output is correct |
7 |
Correct |
12 ms |
2648 KB |
Output is correct |
8 |
Correct |
14 ms |
2748 KB |
Output is correct |
9 |
Correct |
12 ms |
2648 KB |
Output is correct |
10 |
Correct |
15 ms |
2652 KB |
Output is correct |
11 |
Correct |
14 ms |
2652 KB |
Output is correct |
12 |
Correct |
15 ms |
2724 KB |
Output is correct |
13 |
Correct |
18 ms |
2652 KB |
Output is correct |
14 |
Correct |
17 ms |
2648 KB |
Output is correct |
15 |
Correct |
17 ms |
2908 KB |
Output is correct |
16 |
Correct |
12 ms |
2596 KB |
Output is correct |
17 |
Correct |
13 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1156 ms |
9188 KB |
Output is correct |
2 |
Correct |
1200 ms |
8728 KB |
Output is correct |
3 |
Correct |
1189 ms |
8996 KB |
Output is correct |
4 |
Correct |
1218 ms |
8480 KB |
Output is correct |
5 |
Correct |
1211 ms |
8636 KB |
Output is correct |
6 |
Correct |
1372 ms |
8380 KB |
Output is correct |
7 |
Correct |
1370 ms |
8596 KB |
Output is correct |
8 |
Correct |
1362 ms |
8584 KB |
Output is correct |
9 |
Correct |
27 ms |
4432 KB |
Output is correct |
10 |
Correct |
716 ms |
7652 KB |
Output is correct |
11 |
Correct |
725 ms |
7676 KB |
Output is correct |
12 |
Correct |
1109 ms |
8788 KB |
Output is correct |
13 |
Correct |
1148 ms |
8528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
804 ms |
7300 KB |
Output is correct |
2 |
Correct |
360 ms |
5168 KB |
Output is correct |
3 |
Correct |
822 ms |
6956 KB |
Output is correct |
4 |
Correct |
803 ms |
7208 KB |
Output is correct |
5 |
Correct |
28 ms |
4436 KB |
Output is correct |
6 |
Correct |
839 ms |
7232 KB |
Output is correct |
7 |
Correct |
781 ms |
7180 KB |
Output is correct |
8 |
Correct |
753 ms |
7616 KB |
Output is correct |
9 |
Correct |
693 ms |
7504 KB |
Output is correct |
10 |
Correct |
681 ms |
6856 KB |
Output is correct |
11 |
Correct |
698 ms |
7096 KB |
Output is correct |
12 |
Correct |
670 ms |
7108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2299 ms |
11644 KB |
Output is correct |
2 |
Correct |
27 ms |
4444 KB |
Output is correct |
3 |
Correct |
228 ms |
8440 KB |
Output is correct |
4 |
Correct |
124 ms |
8588 KB |
Output is correct |
5 |
Correct |
1224 ms |
10176 KB |
Output is correct |
6 |
Correct |
2222 ms |
11780 KB |
Output is correct |
7 |
Correct |
1205 ms |
10056 KB |
Output is correct |
8 |
Correct |
1080 ms |
8244 KB |
Output is correct |
9 |
Correct |
1085 ms |
8072 KB |
Output is correct |
10 |
Correct |
1091 ms |
8076 KB |
Output is correct |
11 |
Correct |
1727 ms |
10164 KB |
Output is correct |
12 |
Correct |
1700 ms |
10224 KB |
Output is correct |
13 |
Correct |
1766 ms |
10504 KB |
Output is correct |
14 |
Correct |
1136 ms |
10660 KB |
Output is correct |
15 |
Correct |
1179 ms |
10384 KB |
Output is correct |
16 |
Correct |
2280 ms |
11556 KB |
Output is correct |
17 |
Correct |
2263 ms |
12024 KB |
Output is correct |
18 |
Correct |
2294 ms |
11900 KB |
Output is correct |
19 |
Correct |
2288 ms |
11388 KB |
Output is correct |
20 |
Correct |
1974 ms |
10696 KB |
Output is correct |
21 |
Correct |
1960 ms |
10464 KB |
Output is correct |
22 |
Correct |
2221 ms |
11412 KB |
Output is correct |
23 |
Correct |
1243 ms |
9556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1156 ms |
9188 KB |
Output is correct |
2 |
Correct |
1200 ms |
8728 KB |
Output is correct |
3 |
Correct |
1189 ms |
8996 KB |
Output is correct |
4 |
Correct |
1218 ms |
8480 KB |
Output is correct |
5 |
Correct |
1211 ms |
8636 KB |
Output is correct |
6 |
Correct |
1372 ms |
8380 KB |
Output is correct |
7 |
Correct |
1370 ms |
8596 KB |
Output is correct |
8 |
Correct |
1362 ms |
8584 KB |
Output is correct |
9 |
Correct |
27 ms |
4432 KB |
Output is correct |
10 |
Correct |
716 ms |
7652 KB |
Output is correct |
11 |
Correct |
725 ms |
7676 KB |
Output is correct |
12 |
Correct |
1109 ms |
8788 KB |
Output is correct |
13 |
Correct |
1148 ms |
8528 KB |
Output is correct |
14 |
Correct |
804 ms |
7300 KB |
Output is correct |
15 |
Correct |
360 ms |
5168 KB |
Output is correct |
16 |
Correct |
822 ms |
6956 KB |
Output is correct |
17 |
Correct |
803 ms |
7208 KB |
Output is correct |
18 |
Correct |
28 ms |
4436 KB |
Output is correct |
19 |
Correct |
839 ms |
7232 KB |
Output is correct |
20 |
Correct |
781 ms |
7180 KB |
Output is correct |
21 |
Correct |
753 ms |
7616 KB |
Output is correct |
22 |
Correct |
693 ms |
7504 KB |
Output is correct |
23 |
Correct |
681 ms |
6856 KB |
Output is correct |
24 |
Correct |
698 ms |
7096 KB |
Output is correct |
25 |
Correct |
670 ms |
7108 KB |
Output is correct |
26 |
Correct |
1164 ms |
8820 KB |
Output is correct |
27 |
Correct |
1275 ms |
8604 KB |
Output is correct |
28 |
Correct |
1228 ms |
8964 KB |
Output is correct |
29 |
Correct |
1115 ms |
8412 KB |
Output is correct |
30 |
Correct |
1284 ms |
9092 KB |
Output is correct |
31 |
Correct |
1263 ms |
8760 KB |
Output is correct |
32 |
Correct |
1271 ms |
8936 KB |
Output is correct |
33 |
Correct |
1276 ms |
8436 KB |
Output is correct |
34 |
Correct |
1221 ms |
8848 KB |
Output is correct |
35 |
Correct |
1210 ms |
8604 KB |
Output is correct |
36 |
Correct |
1121 ms |
8444 KB |
Output is correct |
37 |
Correct |
1118 ms |
8448 KB |
Output is correct |
38 |
Correct |
1107 ms |
8792 KB |
Output is correct |
39 |
Correct |
1048 ms |
8888 KB |
Output is correct |
40 |
Correct |
1039 ms |
8888 KB |
Output is correct |
41 |
Correct |
1048 ms |
8748 KB |
Output is correct |
42 |
Correct |
1008 ms |
8744 KB |
Output is correct |
43 |
Correct |
1028 ms |
8424 KB |
Output is correct |
44 |
Correct |
1004 ms |
8752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
12 ms |
2692 KB |
Output is correct |
4 |
Correct |
3 ms |
2652 KB |
Output is correct |
5 |
Correct |
14 ms |
2652 KB |
Output is correct |
6 |
Correct |
11 ms |
2640 KB |
Output is correct |
7 |
Correct |
12 ms |
2648 KB |
Output is correct |
8 |
Correct |
14 ms |
2748 KB |
Output is correct |
9 |
Correct |
12 ms |
2648 KB |
Output is correct |
10 |
Correct |
15 ms |
2652 KB |
Output is correct |
11 |
Correct |
14 ms |
2652 KB |
Output is correct |
12 |
Correct |
15 ms |
2724 KB |
Output is correct |
13 |
Correct |
18 ms |
2652 KB |
Output is correct |
14 |
Correct |
17 ms |
2648 KB |
Output is correct |
15 |
Correct |
17 ms |
2908 KB |
Output is correct |
16 |
Correct |
12 ms |
2596 KB |
Output is correct |
17 |
Correct |
13 ms |
2652 KB |
Output is correct |
18 |
Correct |
1156 ms |
9188 KB |
Output is correct |
19 |
Correct |
1200 ms |
8728 KB |
Output is correct |
20 |
Correct |
1189 ms |
8996 KB |
Output is correct |
21 |
Correct |
1218 ms |
8480 KB |
Output is correct |
22 |
Correct |
1211 ms |
8636 KB |
Output is correct |
23 |
Correct |
1372 ms |
8380 KB |
Output is correct |
24 |
Correct |
1370 ms |
8596 KB |
Output is correct |
25 |
Correct |
1362 ms |
8584 KB |
Output is correct |
26 |
Correct |
27 ms |
4432 KB |
Output is correct |
27 |
Correct |
716 ms |
7652 KB |
Output is correct |
28 |
Correct |
725 ms |
7676 KB |
Output is correct |
29 |
Correct |
1109 ms |
8788 KB |
Output is correct |
30 |
Correct |
1148 ms |
8528 KB |
Output is correct |
31 |
Correct |
804 ms |
7300 KB |
Output is correct |
32 |
Correct |
360 ms |
5168 KB |
Output is correct |
33 |
Correct |
822 ms |
6956 KB |
Output is correct |
34 |
Correct |
803 ms |
7208 KB |
Output is correct |
35 |
Correct |
28 ms |
4436 KB |
Output is correct |
36 |
Correct |
839 ms |
7232 KB |
Output is correct |
37 |
Correct |
781 ms |
7180 KB |
Output is correct |
38 |
Correct |
753 ms |
7616 KB |
Output is correct |
39 |
Correct |
693 ms |
7504 KB |
Output is correct |
40 |
Correct |
681 ms |
6856 KB |
Output is correct |
41 |
Correct |
698 ms |
7096 KB |
Output is correct |
42 |
Correct |
670 ms |
7108 KB |
Output is correct |
43 |
Correct |
2299 ms |
11644 KB |
Output is correct |
44 |
Correct |
27 ms |
4444 KB |
Output is correct |
45 |
Correct |
228 ms |
8440 KB |
Output is correct |
46 |
Correct |
124 ms |
8588 KB |
Output is correct |
47 |
Correct |
1224 ms |
10176 KB |
Output is correct |
48 |
Correct |
2222 ms |
11780 KB |
Output is correct |
49 |
Correct |
1205 ms |
10056 KB |
Output is correct |
50 |
Correct |
1080 ms |
8244 KB |
Output is correct |
51 |
Correct |
1085 ms |
8072 KB |
Output is correct |
52 |
Correct |
1091 ms |
8076 KB |
Output is correct |
53 |
Correct |
1727 ms |
10164 KB |
Output is correct |
54 |
Correct |
1700 ms |
10224 KB |
Output is correct |
55 |
Correct |
1766 ms |
10504 KB |
Output is correct |
56 |
Correct |
1136 ms |
10660 KB |
Output is correct |
57 |
Correct |
1179 ms |
10384 KB |
Output is correct |
58 |
Correct |
2280 ms |
11556 KB |
Output is correct |
59 |
Correct |
2263 ms |
12024 KB |
Output is correct |
60 |
Correct |
2294 ms |
11900 KB |
Output is correct |
61 |
Correct |
2288 ms |
11388 KB |
Output is correct |
62 |
Correct |
1974 ms |
10696 KB |
Output is correct |
63 |
Correct |
1960 ms |
10464 KB |
Output is correct |
64 |
Correct |
2221 ms |
11412 KB |
Output is correct |
65 |
Correct |
1243 ms |
9556 KB |
Output is correct |
66 |
Correct |
1164 ms |
8820 KB |
Output is correct |
67 |
Correct |
1275 ms |
8604 KB |
Output is correct |
68 |
Correct |
1228 ms |
8964 KB |
Output is correct |
69 |
Correct |
1115 ms |
8412 KB |
Output is correct |
70 |
Correct |
1284 ms |
9092 KB |
Output is correct |
71 |
Correct |
1263 ms |
8760 KB |
Output is correct |
72 |
Correct |
1271 ms |
8936 KB |
Output is correct |
73 |
Correct |
1276 ms |
8436 KB |
Output is correct |
74 |
Correct |
1221 ms |
8848 KB |
Output is correct |
75 |
Correct |
1210 ms |
8604 KB |
Output is correct |
76 |
Correct |
1121 ms |
8444 KB |
Output is correct |
77 |
Correct |
1118 ms |
8448 KB |
Output is correct |
78 |
Correct |
1107 ms |
8792 KB |
Output is correct |
79 |
Correct |
1048 ms |
8888 KB |
Output is correct |
80 |
Correct |
1039 ms |
8888 KB |
Output is correct |
81 |
Correct |
1048 ms |
8748 KB |
Output is correct |
82 |
Correct |
1008 ms |
8744 KB |
Output is correct |
83 |
Correct |
1028 ms |
8424 KB |
Output is correct |
84 |
Correct |
1004 ms |
8752 KB |
Output is correct |
85 |
Correct |
2298 ms |
11948 KB |
Output is correct |
86 |
Correct |
236 ms |
8524 KB |
Output is correct |
87 |
Correct |
132 ms |
8680 KB |
Output is correct |
88 |
Correct |
1333 ms |
10032 KB |
Output is correct |
89 |
Correct |
2227 ms |
11572 KB |
Output is correct |
90 |
Correct |
1331 ms |
10112 KB |
Output is correct |
91 |
Correct |
1233 ms |
8824 KB |
Output is correct |
92 |
Correct |
1228 ms |
8716 KB |
Output is correct |
93 |
Correct |
1392 ms |
8672 KB |
Output is correct |
94 |
Correct |
1911 ms |
10276 KB |
Output is correct |
95 |
Correct |
1905 ms |
10476 KB |
Output is correct |
96 |
Correct |
1906 ms |
10156 KB |
Output is correct |
97 |
Correct |
1270 ms |
10152 KB |
Output is correct |
98 |
Correct |
1378 ms |
10360 KB |
Output is correct |
99 |
Correct |
2459 ms |
11552 KB |
Output is correct |
100 |
Correct |
2457 ms |
11592 KB |
Output is correct |
101 |
Correct |
2470 ms |
11612 KB |
Output is correct |
102 |
Correct |
2448 ms |
11536 KB |
Output is correct |
103 |
Correct |
2136 ms |
10560 KB |
Output is correct |
104 |
Correct |
2106 ms |
11400 KB |
Output is correct |
105 |
Correct |
2032 ms |
10936 KB |
Output is correct |
106 |
Correct |
1766 ms |
10264 KB |
Output is correct |
107 |
Correct |
1997 ms |
10588 KB |
Output is correct |
108 |
Correct |
2346 ms |
11176 KB |
Output is correct |
109 |
Correct |
1367 ms |
9440 KB |
Output is correct |