#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
//C++17 when
constexpr int N = 50005, M = 100005;
constexpr int Q = 100005, T = 444;
int n, m;
int u[M], v[M], w[M];
vector<int> idx;
auto comp = [](int x, int y) {
return mp(w[x], x) > mp(w[y], y);
};
int cur_w[M];
bool changed[M];
bool tmp_vis[N];
int d[N];
//fwd-star
constexpr int MX = 2000;
int lst[N];
int to[MX], edge[MX], nxt[MX];
int sz = 0;
void add_edge(int u, int v, int i) {
nxt[++sz] = lst[u];
to[sz] = v;
edge[sz] = i;
lst[u] = sz;
}
int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
void join(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(d[x] > d[y]) swap(x, y);
d[x] += d[y]; d[y] = x;
}
int comp_sz(int x) {
return -d[find(x)];
}
struct query {
int t, u, w;
query(int t, int u, int w): t(t), u(u), w(w) {}
bool operator < (const query& oth) {return w > oth.w;}
};
struct update {
int t, id, w;
update(int t, int id, int w): t(t), id(id), w(w) {}
};
vi merge(const vi& a, const vi& b) {
vi ans; ans.reserve(m);
int ptra = 0, ptrb = 0;
while(ptra < a.size() || ptrb < b.size()) {
if(ptra < a.size() && (ptrb == b.size() || comp(a[ptra], b[ptrb]))) ans.pb(a[ptra++]);
else ans.pb(b[ptrb++]);
}
return ans;
}
void process_queries(const vector<update>& upd, vector<query> qry) {
sort(all(qry));
vector<int> updated;
memset(changed, 0, m * sizeof(bool));
memset(d, -1, n * sizeof(int));
memset(tmp_vis, 0, n * sizeof(bool));
memset(lst, 0, n * sizeof(int));
sz = 0;
for(auto& u: upd) if(!changed[u.id]) {
updated.pb(u.id);
idx.erase(lower_bound(all(idx), u.id, comp));
//idx.erase(find(all(idx), u.id));
changed[u.id] = 1;
}
vector<pii> ans;
int ptr = 0;
for(auto& q: qry) {
//cout << "processing " << q.t << ' ' << q.u << ' ' << q.w << endl;
while(ptr < idx.size() && w[idx[ptr]] >= q.w) {
//if(!changed[idx[ptr]]) cout << "joining " << idx[ptr] << ' ' << u[idx[ptr]] << ' ' << v[idx[ptr]] << endl;
join(u[idx[ptr]], v[idx[ptr]]);
ptr++;
}
sz = 0;
for(int id: updated) {
lst[find(u[id])] = 0;
lst[find(v[id])] = 0;
cur_w[id] = w[id];
}
for(int i = 0; i < upd.size() && upd[i].t <= q.t; i++) {
cur_w[upd[i].id] = upd[i].w;
}
for(int id: updated) {
int x = find(u[id]), y = find(v[id]);
//cout << "insert edge " << id << ' ' << x << ' ' << y << ' ' << cur_w[id] << endl;
add_edge(x, y, id);
add_edge(y, x, id);
}
int res = 0;
for(int id: updated) {
tmp_vis[find(u[id])] = 0;
tmp_vis[find(v[id])] = 0;
}
q.u = find(q.u);
function<void(int)> dfs = [&](int u) -> void {
tmp_vis[u] = 1;
res += comp_sz(u);
for(int id = lst[u]; id; id = nxt[id]) {
int v = to[id], i = edge[id];
if(cur_w[i] >= q.w && !tmp_vis[v]) dfs(v);
}
};
dfs(q.u);
ans.eb(q.t, res);
}
for(auto& u: upd) w[u.id] = u.w;
vi erased_idx;
for(int x: updated) erased_idx.pb(x);
sort(all(erased_idx), comp);
idx = merge(idx, erased_idx);
sort(all(ans));
for(auto& [_, v]: ans) cout << v << endl;
//cout << "end block\n";
//rep(i, m) cout << w[i] << ' '; cout << endl;
//rep(i, m) cout << idx[i] << ' '; cout << endl;
}
int32_t main() {
fastio;
cin >> n >> m;
rep(i, m) {
cin >> u[i] >> v[i] >> w[i];
--u[i], --v[i];
}
idx.resize(m);
iota(all(idx), 0);
sort(all(idx), comp);
int q; cin >> q;
for(int i = 0; i < q; i += T) {
vector<query> queries;
vector<update> updates;
for(int j = i; j < min(i + T, q); j++) {
int T; cin >> T;
if(T == 1) {
int x, w; cin >> x >> w; --x;
updates.eb(j, x, w);
}
else {
int u, w; cin >> u >> w; --u;
queries.eb(j, u, w);
}
}
process_queries(updates, queries);
}
}
Compilation message
bridges.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization("unroll-loops, no-stack-protector")
|
bridges.cpp: In function 'vi merge(const vi&, const vi&)':
bridges.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | while(ptra < a.size() || ptrb < b.size()) {
| ~~~~~^~~~~~~~~~
bridges.cpp:105:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | while(ptra < a.size() || ptrb < b.size()) {
| ~~~~~^~~~~~~~~~
bridges.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if(ptra < a.size() && (ptrb == b.size() || comp(a[ptra], b[ptrb]))) ans.pb(a[ptra++]);
| ~~~~~^~~~~~~~~~
bridges.cpp:106:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if(ptra < a.size() && (ptrb == b.size() || comp(a[ptra], b[ptrb]))) ans.pb(a[ptra++]);
| ~~~~~^~~~~~~~~~~
bridges.cpp: In function 'void process_queries(const std::vector<update>&, std::vector<query>)':
bridges.cpp:130:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | while(ptr < idx.size() && w[idx[ptr]] >= q.w) {
| ~~~~^~~~~~~~~~~~
bridges.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<update>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int i = 0; i < upd.size() && upd[i].t <= q.t; i++) {
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
57 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
372 KB |
Output is correct |
5 |
Correct |
25 ms |
392 KB |
Output is correct |
6 |
Correct |
25 ms |
392 KB |
Output is correct |
7 |
Correct |
23 ms |
380 KB |
Output is correct |
8 |
Correct |
21 ms |
332 KB |
Output is correct |
9 |
Correct |
26 ms |
392 KB |
Output is correct |
10 |
Correct |
20 ms |
396 KB |
Output is correct |
11 |
Correct |
20 ms |
392 KB |
Output is correct |
12 |
Correct |
20 ms |
400 KB |
Output is correct |
13 |
Correct |
28 ms |
388 KB |
Output is correct |
14 |
Correct |
27 ms |
392 KB |
Output is correct |
15 |
Correct |
25 ms |
396 KB |
Output is correct |
16 |
Correct |
23 ms |
388 KB |
Output is correct |
17 |
Correct |
23 ms |
388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1546 ms |
2540 KB |
Output is correct |
2 |
Correct |
1538 ms |
2360 KB |
Output is correct |
3 |
Correct |
1536 ms |
2328 KB |
Output is correct |
4 |
Correct |
1524 ms |
2540 KB |
Output is correct |
5 |
Correct |
1541 ms |
2700 KB |
Output is correct |
6 |
Correct |
1917 ms |
2804 KB |
Output is correct |
7 |
Correct |
1814 ms |
2640 KB |
Output is correct |
8 |
Correct |
1742 ms |
2660 KB |
Output is correct |
9 |
Correct |
53 ms |
592 KB |
Output is correct |
10 |
Correct |
1574 ms |
2532 KB |
Output is correct |
11 |
Correct |
1485 ms |
2424 KB |
Output is correct |
12 |
Correct |
950 ms |
2812 KB |
Output is correct |
13 |
Correct |
1297 ms |
2492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1155 ms |
1884 KB |
Output is correct |
2 |
Correct |
837 ms |
964 KB |
Output is correct |
3 |
Correct |
1280 ms |
1988 KB |
Output is correct |
4 |
Correct |
1190 ms |
1744 KB |
Output is correct |
5 |
Correct |
53 ms |
616 KB |
Output is correct |
6 |
Correct |
1197 ms |
1960 KB |
Output is correct |
7 |
Correct |
1159 ms |
1784 KB |
Output is correct |
8 |
Correct |
1129 ms |
1752 KB |
Output is correct |
9 |
Correct |
606 ms |
1844 KB |
Output is correct |
10 |
Correct |
597 ms |
2008 KB |
Output is correct |
11 |
Correct |
864 ms |
1632 KB |
Output is correct |
12 |
Correct |
837 ms |
1716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1139 ms |
3492 KB |
Output is correct |
2 |
Correct |
52 ms |
452 KB |
Output is correct |
3 |
Correct |
126 ms |
2432 KB |
Output is correct |
4 |
Correct |
78 ms |
2432 KB |
Output is correct |
5 |
Correct |
798 ms |
3364 KB |
Output is correct |
6 |
Correct |
1138 ms |
3312 KB |
Output is correct |
7 |
Correct |
795 ms |
3236 KB |
Output is correct |
8 |
Correct |
615 ms |
1912 KB |
Output is correct |
9 |
Correct |
602 ms |
1964 KB |
Output is correct |
10 |
Correct |
623 ms |
2224 KB |
Output is correct |
11 |
Correct |
1040 ms |
2684 KB |
Output is correct |
12 |
Correct |
994 ms |
2568 KB |
Output is correct |
13 |
Correct |
1048 ms |
2788 KB |
Output is correct |
14 |
Correct |
781 ms |
3448 KB |
Output is correct |
15 |
Correct |
786 ms |
3492 KB |
Output is correct |
16 |
Correct |
1273 ms |
3376 KB |
Output is correct |
17 |
Correct |
1280 ms |
3244 KB |
Output is correct |
18 |
Correct |
1276 ms |
3352 KB |
Output is correct |
19 |
Correct |
1266 ms |
3248 KB |
Output is correct |
20 |
Correct |
1173 ms |
3236 KB |
Output is correct |
21 |
Correct |
1180 ms |
3092 KB |
Output is correct |
22 |
Correct |
1230 ms |
3388 KB |
Output is correct |
23 |
Correct |
944 ms |
3012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1546 ms |
2540 KB |
Output is correct |
2 |
Correct |
1538 ms |
2360 KB |
Output is correct |
3 |
Correct |
1536 ms |
2328 KB |
Output is correct |
4 |
Correct |
1524 ms |
2540 KB |
Output is correct |
5 |
Correct |
1541 ms |
2700 KB |
Output is correct |
6 |
Correct |
1917 ms |
2804 KB |
Output is correct |
7 |
Correct |
1814 ms |
2640 KB |
Output is correct |
8 |
Correct |
1742 ms |
2660 KB |
Output is correct |
9 |
Correct |
53 ms |
592 KB |
Output is correct |
10 |
Correct |
1574 ms |
2532 KB |
Output is correct |
11 |
Correct |
1485 ms |
2424 KB |
Output is correct |
12 |
Correct |
950 ms |
2812 KB |
Output is correct |
13 |
Correct |
1297 ms |
2492 KB |
Output is correct |
14 |
Correct |
1155 ms |
1884 KB |
Output is correct |
15 |
Correct |
837 ms |
964 KB |
Output is correct |
16 |
Correct |
1280 ms |
1988 KB |
Output is correct |
17 |
Correct |
1190 ms |
1744 KB |
Output is correct |
18 |
Correct |
53 ms |
616 KB |
Output is correct |
19 |
Correct |
1197 ms |
1960 KB |
Output is correct |
20 |
Correct |
1159 ms |
1784 KB |
Output is correct |
21 |
Correct |
1129 ms |
1752 KB |
Output is correct |
22 |
Correct |
606 ms |
1844 KB |
Output is correct |
23 |
Correct |
597 ms |
2008 KB |
Output is correct |
24 |
Correct |
864 ms |
1632 KB |
Output is correct |
25 |
Correct |
837 ms |
1716 KB |
Output is correct |
26 |
Correct |
1446 ms |
2420 KB |
Output is correct |
27 |
Correct |
1804 ms |
2500 KB |
Output is correct |
28 |
Correct |
1684 ms |
2584 KB |
Output is correct |
29 |
Correct |
1500 ms |
2652 KB |
Output is correct |
30 |
Correct |
1807 ms |
2460 KB |
Output is correct |
31 |
Correct |
1792 ms |
2692 KB |
Output is correct |
32 |
Correct |
1798 ms |
2492 KB |
Output is correct |
33 |
Correct |
1639 ms |
2392 KB |
Output is correct |
34 |
Correct |
1640 ms |
2596 KB |
Output is correct |
35 |
Correct |
1638 ms |
2404 KB |
Output is correct |
36 |
Correct |
1503 ms |
2436 KB |
Output is correct |
37 |
Correct |
1501 ms |
2500 KB |
Output is correct |
38 |
Correct |
1504 ms |
2604 KB |
Output is correct |
39 |
Correct |
900 ms |
2456 KB |
Output is correct |
40 |
Correct |
902 ms |
2484 KB |
Output is correct |
41 |
Correct |
901 ms |
2480 KB |
Output is correct |
42 |
Correct |
1219 ms |
2232 KB |
Output is correct |
43 |
Correct |
1229 ms |
2332 KB |
Output is correct |
44 |
Correct |
1217 ms |
2236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
57 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
372 KB |
Output is correct |
5 |
Correct |
25 ms |
392 KB |
Output is correct |
6 |
Correct |
25 ms |
392 KB |
Output is correct |
7 |
Correct |
23 ms |
380 KB |
Output is correct |
8 |
Correct |
21 ms |
332 KB |
Output is correct |
9 |
Correct |
26 ms |
392 KB |
Output is correct |
10 |
Correct |
20 ms |
396 KB |
Output is correct |
11 |
Correct |
20 ms |
392 KB |
Output is correct |
12 |
Correct |
20 ms |
400 KB |
Output is correct |
13 |
Correct |
28 ms |
388 KB |
Output is correct |
14 |
Correct |
27 ms |
392 KB |
Output is correct |
15 |
Correct |
25 ms |
396 KB |
Output is correct |
16 |
Correct |
23 ms |
388 KB |
Output is correct |
17 |
Correct |
23 ms |
388 KB |
Output is correct |
18 |
Correct |
1546 ms |
2540 KB |
Output is correct |
19 |
Correct |
1538 ms |
2360 KB |
Output is correct |
20 |
Correct |
1536 ms |
2328 KB |
Output is correct |
21 |
Correct |
1524 ms |
2540 KB |
Output is correct |
22 |
Correct |
1541 ms |
2700 KB |
Output is correct |
23 |
Correct |
1917 ms |
2804 KB |
Output is correct |
24 |
Correct |
1814 ms |
2640 KB |
Output is correct |
25 |
Correct |
1742 ms |
2660 KB |
Output is correct |
26 |
Correct |
53 ms |
592 KB |
Output is correct |
27 |
Correct |
1574 ms |
2532 KB |
Output is correct |
28 |
Correct |
1485 ms |
2424 KB |
Output is correct |
29 |
Correct |
950 ms |
2812 KB |
Output is correct |
30 |
Correct |
1297 ms |
2492 KB |
Output is correct |
31 |
Correct |
1155 ms |
1884 KB |
Output is correct |
32 |
Correct |
837 ms |
964 KB |
Output is correct |
33 |
Correct |
1280 ms |
1988 KB |
Output is correct |
34 |
Correct |
1190 ms |
1744 KB |
Output is correct |
35 |
Correct |
53 ms |
616 KB |
Output is correct |
36 |
Correct |
1197 ms |
1960 KB |
Output is correct |
37 |
Correct |
1159 ms |
1784 KB |
Output is correct |
38 |
Correct |
1129 ms |
1752 KB |
Output is correct |
39 |
Correct |
606 ms |
1844 KB |
Output is correct |
40 |
Correct |
597 ms |
2008 KB |
Output is correct |
41 |
Correct |
864 ms |
1632 KB |
Output is correct |
42 |
Correct |
837 ms |
1716 KB |
Output is correct |
43 |
Correct |
1139 ms |
3492 KB |
Output is correct |
44 |
Correct |
52 ms |
452 KB |
Output is correct |
45 |
Correct |
126 ms |
2432 KB |
Output is correct |
46 |
Correct |
78 ms |
2432 KB |
Output is correct |
47 |
Correct |
798 ms |
3364 KB |
Output is correct |
48 |
Correct |
1138 ms |
3312 KB |
Output is correct |
49 |
Correct |
795 ms |
3236 KB |
Output is correct |
50 |
Correct |
615 ms |
1912 KB |
Output is correct |
51 |
Correct |
602 ms |
1964 KB |
Output is correct |
52 |
Correct |
623 ms |
2224 KB |
Output is correct |
53 |
Correct |
1040 ms |
2684 KB |
Output is correct |
54 |
Correct |
994 ms |
2568 KB |
Output is correct |
55 |
Correct |
1048 ms |
2788 KB |
Output is correct |
56 |
Correct |
781 ms |
3448 KB |
Output is correct |
57 |
Correct |
786 ms |
3492 KB |
Output is correct |
58 |
Correct |
1273 ms |
3376 KB |
Output is correct |
59 |
Correct |
1280 ms |
3244 KB |
Output is correct |
60 |
Correct |
1276 ms |
3352 KB |
Output is correct |
61 |
Correct |
1266 ms |
3248 KB |
Output is correct |
62 |
Correct |
1173 ms |
3236 KB |
Output is correct |
63 |
Correct |
1180 ms |
3092 KB |
Output is correct |
64 |
Correct |
1230 ms |
3388 KB |
Output is correct |
65 |
Correct |
944 ms |
3012 KB |
Output is correct |
66 |
Correct |
1446 ms |
2420 KB |
Output is correct |
67 |
Correct |
1804 ms |
2500 KB |
Output is correct |
68 |
Correct |
1684 ms |
2584 KB |
Output is correct |
69 |
Correct |
1500 ms |
2652 KB |
Output is correct |
70 |
Correct |
1807 ms |
2460 KB |
Output is correct |
71 |
Correct |
1792 ms |
2692 KB |
Output is correct |
72 |
Correct |
1798 ms |
2492 KB |
Output is correct |
73 |
Correct |
1639 ms |
2392 KB |
Output is correct |
74 |
Correct |
1640 ms |
2596 KB |
Output is correct |
75 |
Correct |
1638 ms |
2404 KB |
Output is correct |
76 |
Correct |
1503 ms |
2436 KB |
Output is correct |
77 |
Correct |
1501 ms |
2500 KB |
Output is correct |
78 |
Correct |
1504 ms |
2604 KB |
Output is correct |
79 |
Correct |
900 ms |
2456 KB |
Output is correct |
80 |
Correct |
902 ms |
2484 KB |
Output is correct |
81 |
Correct |
901 ms |
2480 KB |
Output is correct |
82 |
Correct |
1219 ms |
2232 KB |
Output is correct |
83 |
Correct |
1229 ms |
2332 KB |
Output is correct |
84 |
Correct |
1217 ms |
2236 KB |
Output is correct |
85 |
Correct |
2610 ms |
3996 KB |
Output is correct |
86 |
Correct |
244 ms |
5004 KB |
Output is correct |
87 |
Correct |
196 ms |
5164 KB |
Output is correct |
88 |
Correct |
2202 ms |
6428 KB |
Output is correct |
89 |
Correct |
2617 ms |
8080 KB |
Output is correct |
90 |
Correct |
2164 ms |
6248 KB |
Output is correct |
91 |
Correct |
1630 ms |
5028 KB |
Output is correct |
92 |
Correct |
1631 ms |
5224 KB |
Output is correct |
93 |
Correct |
1789 ms |
5044 KB |
Output is correct |
94 |
Correct |
2251 ms |
6252 KB |
Output is correct |
95 |
Correct |
2244 ms |
6488 KB |
Output is correct |
96 |
Correct |
2349 ms |
6392 KB |
Output is correct |
97 |
Correct |
1199 ms |
6172 KB |
Output is correct |
98 |
Correct |
1848 ms |
5452 KB |
Output is correct |
99 |
Correct |
2731 ms |
7808 KB |
Output is correct |
100 |
Correct |
2615 ms |
7788 KB |
Output is correct |
101 |
Correct |
2731 ms |
8060 KB |
Output is correct |
102 |
Correct |
2693 ms |
7652 KB |
Output is correct |
103 |
Correct |
2523 ms |
6756 KB |
Output is correct |
104 |
Correct |
2407 ms |
6896 KB |
Output is correct |
105 |
Correct |
2122 ms |
6336 KB |
Output is correct |
106 |
Correct |
1839 ms |
6008 KB |
Output is correct |
107 |
Correct |
1563 ms |
6916 KB |
Output is correct |
108 |
Correct |
2684 ms |
7124 KB |
Output is correct |
109 |
Correct |
2311 ms |
5508 KB |
Output is correct |