#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
struct edgeNode {
int u, v, d;
};
struct queryNode {
int type, b, r, s, w;
};
int n, m, q;
vector<edgeNode> edge;
vector<queryNode> qu;
bool checkSub1() {
if (n <= 1000 && m <= 1000 && q <= 10000) return true;
return false;
}
namespace subtask1 {
int ans = 0;
vector<int> vis;
vector<vector<int>> adj;
void dfs(int u, int w) {
ans++;
vis[u]++;
FORALL(id, adj[u]) {
int v = edge[id].u + edge[id].v - u;
if (vis[v] || edge[id].d < w) continue;
dfs(v, w);
}
}
void main() {
vis.resize(n + 1);
adj.resize(n + 1);
FOR(i, 1, m) adj[edge[i].u].push_back(i), adj[edge[i].v].push_back(i);
REP(i, q) {
if (qu[i].type == 1) edge[qu[i].b].d = qu[i].r;
else {
ans = 0;
FOR(j, 1, n) vis[j] = 0;
dfs(qu[i].w, qu[i].s);
cout << ans << '\n';
}
}
}
}
bool checkSub2() {
if (m != n - 1) return false;
FOR(i, 1, m) if (edge[i].u != i || edge[i].v != i + 1) return false;
return true;
}
namespace subtask2 {
const int inf = 1e9;
struct segTree {
vector<int> ST;
void init(int n) {
ST.resize(4 * n + 4);
}
void update(int id, int l, int r, int pos, int val) {
if (pos < l || r < pos) return ;
if (l == r) {
ST[id] = val;
return ;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, pos, val);
update(id * 2 + 1, mid + 1, r, pos, val);
ST[id] = min(ST[id * 2], ST[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v) {
if (r < u || v < l) return inf;
if (u <= l && r <= v) return ST[id];
int mid = (l + r) / 2;
return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
} st;
void main() {
st.init(n);
FOR(i, 1, m) st.update(1, 1, n - 1, i, edge[i].d);
REP(i, q) {
if (qu[i].type == 1) st.update(1, 1, n - 1, qu[i].b, qu[i].r);
else {
int w = qu[i].w, s = qu[i].s;
int k = 0;
while ((1 << k) <= w - 1) k++;
k--;
int x = w;
FORD(j, k, 0) if (x - (1 << j) > 0 && st.get(1, 1, n - 1, x - (1 << j), x - 1) >= s) x -= (1 << j);
k = 0;
while ((1 << k) <= n - 1 - w) k++;
k--;
FORD(j, k, 0) if (w + (1 << j) < n && st.get(1, 1, n - 1, w, w + (1 << j)) >= s) w += (1 << j);
if (w == n || st.get(1, 1, n - 1, w, w) < s) w--;
cout << w + 1 - x + 1 << '\n';
}
}
}
}
bool checkSub4() {
REP(i, q) if (qu[i].type == 1) return false;
return true;
}
namespace subtask4 {
vector<int> root, sz;
int getroot(int u) {
return root[u] == u ? u : (root[u] = getroot(root[u]));
}
bool unite(int u, int v) {
u = getroot(u), v = getroot(v);
if (u == v) return false;
root[v] = u;
sz[u] += sz[v];
return true;
}
void main() {
root.resize(n + 1), sz.resize(n + 1);
FOR(i, 1, n) root[i] = i, sz[i] = 1;
vector<pair<int, int>> cost;
FOR(i, 1, m) cost.push_back({edge[i].d, i});
sort(cost.begin(), cost.end(), [&] (const pair<int, int> a, pair<int, int> b) { return a.fi > b.fi; });
vector<pair<int, int>> g;
REP(i, q) g.push_back({qu[i].s, i});
sort(g.begin(), g.end(), [&] (const pair<int, int> a, pair<int, int> b) { return a.fi > b.fi; });
vector<int> ans(q);
int j = 0;
REP(i, q) {
int id = g[i].se;
while (j < _size(cost) && cost[j].fi >= g[i].fi) unite(edge[cost[j].se].u, edge[cost[j].se].v), j++;
ans[id] = sz[getroot(qu[id].w)];
}
REP(i, q) cout << ans[i] << '\n';
}
}
namespace fullsubtask {
stack<int> _st;
vector<int> root, sz;
int getroot(int u) {
while (root[u] != u) u = root[u];
return u;
}
bool unite(int u, int v) {
u = getroot(u), v = getroot(v);
if (u == v) return false;
if (sz[v] > sz[u]) swap(u, v);
_st.push(v);
root[v] = u;
sz[u] += sz[v];
return true;
}
void main() {
/***
chia thanh sqrt(q) block queries
voi moi block, update thi cap nhat trong so moi, calculation thi duyet lai cac canh changed
*/
root.resize(n + 1);
sz.resize(n + 1);
int blockSz = 1000;
int cnt = q / blockSz + (q % blockSz ? 1 : 0);
vector<int> cntChange(m + 1), ans(q);
vector<vector<int>> to_join(q);
REP(l, cnt) {
while (!_st.empty()) _st.pop();
FOR(i, 1, n) root[i] = i, sz[i] = 1;
FOR(i, 1, m) cntChange[i] = 0;
int st = l * blockSz, en = min(q - 1, (l + 1) * blockSz - 1);
vector<int> unchanged, changed, ask;
FOR(i, st, en) {
if (qu[i].type == 1) {
cntChange[qu[i].b]++;
changed.push_back(i);
}
else ask.push_back(i);
}
FOR(i, 1, m) if (!cntChange[i]) unchanged.push_back(i);
FOR(i, st, en) {
if (qu[i].type == 1) edge[qu[i].b].d = qu[i].r;
else {
FORALL(id, changed) if (edge[qu[id].b].d >= qu[i].s) to_join[i].push_back(qu[id].b);
}
}
sort(unchanged.begin(), unchanged.end(), [&] (const int i, int j) { return edge[i].d > edge[j].d; });
sort(ask.begin(), ask.end(), [&] (const int i, int j) { return qu[i].s > qu[j].s; });
int i = 0;
FORALL(id, ask) {
while (i < _size(unchanged) && edge[unchanged[i]].d >= qu[id].s) {
unite(edge[unchanged[i]].u, edge[unchanged[i]].v);
i++;
}
int _sz = _size(_st);
FORALL(_id, to_join[id]) unite(edge[_id].u, edge[_id].v);
ans[id] = sz[getroot(qu[id].w)];
while (_size(_st) > _sz) {
int v = _st.top();
_st.pop();
sz[root[v]] -= sz[v];
root[v] = v;
}
}
}
REP(i, q) if (qu[i].type == 2) cout << ans[i] << '\n';
}
}
int main() {
fastio;
cin >> n >> m;
edge.resize(m + 1);
FOR(i, 1, m) {
int u, v, d;
cin >> u >> v >> d;
edge[i] = {u, v, d};
}
cin >> q;
qu.resize(q);
REP(i, q) {
cin >> qu[i].type;
if (qu[i].type == 1) cin >> qu[i].b >> qu[i].r;
else cin >> qu[i].w >> qu[i].s;
}
if (checkSub1()) subtask1::main();
else if (checkSub2()) subtask2::main();
else if (checkSub4()) subtask4::main();
else fullsubtask::main();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
35 ms |
704 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
5 ms |
604 KB |
Output is correct |
6 |
Correct |
4 ms |
656 KB |
Output is correct |
7 |
Correct |
4 ms |
600 KB |
Output is correct |
8 |
Correct |
4 ms |
604 KB |
Output is correct |
9 |
Correct |
5 ms |
604 KB |
Output is correct |
10 |
Correct |
3 ms |
672 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
12 |
Correct |
3 ms |
604 KB |
Output is correct |
13 |
Correct |
5 ms |
604 KB |
Output is correct |
14 |
Correct |
4 ms |
680 KB |
Output is correct |
15 |
Correct |
6 ms |
600 KB |
Output is correct |
16 |
Correct |
4 ms |
604 KB |
Output is correct |
17 |
Correct |
4 ms |
680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
289 ms |
3828 KB |
Output is correct |
2 |
Correct |
284 ms |
3988 KB |
Output is correct |
3 |
Correct |
280 ms |
3668 KB |
Output is correct |
4 |
Correct |
278 ms |
3776 KB |
Output is correct |
5 |
Correct |
277 ms |
3664 KB |
Output is correct |
6 |
Correct |
241 ms |
3976 KB |
Output is correct |
7 |
Correct |
263 ms |
3924 KB |
Output is correct |
8 |
Correct |
266 ms |
3924 KB |
Output is correct |
9 |
Correct |
20 ms |
2396 KB |
Output is correct |
10 |
Correct |
222 ms |
3980 KB |
Output is correct |
11 |
Correct |
239 ms |
4156 KB |
Output is correct |
12 |
Correct |
440 ms |
4260 KB |
Output is correct |
13 |
Correct |
91 ms |
3668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
767 ms |
73468 KB |
Output is correct |
2 |
Correct |
493 ms |
98732 KB |
Output is correct |
3 |
Correct |
803 ms |
101616 KB |
Output is correct |
4 |
Correct |
761 ms |
73100 KB |
Output is correct |
5 |
Correct |
20 ms |
2396 KB |
Output is correct |
6 |
Correct |
804 ms |
92928 KB |
Output is correct |
7 |
Correct |
711 ms |
65276 KB |
Output is correct |
8 |
Correct |
630 ms |
49268 KB |
Output is correct |
9 |
Correct |
530 ms |
41076 KB |
Output is correct |
10 |
Correct |
503 ms |
29648 KB |
Output is correct |
11 |
Correct |
570 ms |
38752 KB |
Output is correct |
12 |
Correct |
489 ms |
28624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
6264 KB |
Output is correct |
2 |
Correct |
21 ms |
2572 KB |
Output is correct |
3 |
Correct |
29 ms |
2780 KB |
Output is correct |
4 |
Correct |
26 ms |
2780 KB |
Output is correct |
5 |
Correct |
46 ms |
6240 KB |
Output is correct |
6 |
Correct |
63 ms |
6272 KB |
Output is correct |
7 |
Correct |
47 ms |
6196 KB |
Output is correct |
8 |
Correct |
47 ms |
4944 KB |
Output is correct |
9 |
Correct |
50 ms |
5136 KB |
Output is correct |
10 |
Correct |
51 ms |
5316 KB |
Output is correct |
11 |
Correct |
56 ms |
5712 KB |
Output is correct |
12 |
Correct |
55 ms |
5708 KB |
Output is correct |
13 |
Correct |
57 ms |
5716 KB |
Output is correct |
14 |
Correct |
45 ms |
6484 KB |
Output is correct |
15 |
Correct |
46 ms |
6428 KB |
Output is correct |
16 |
Correct |
64 ms |
6228 KB |
Output is correct |
17 |
Correct |
64 ms |
6224 KB |
Output is correct |
18 |
Correct |
64 ms |
6272 KB |
Output is correct |
19 |
Correct |
70 ms |
6224 KB |
Output is correct |
20 |
Correct |
57 ms |
6048 KB |
Output is correct |
21 |
Correct |
55 ms |
6144 KB |
Output is correct |
22 |
Correct |
65 ms |
6220 KB |
Output is correct |
23 |
Correct |
43 ms |
5972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
289 ms |
3828 KB |
Output is correct |
2 |
Correct |
284 ms |
3988 KB |
Output is correct |
3 |
Correct |
280 ms |
3668 KB |
Output is correct |
4 |
Correct |
278 ms |
3776 KB |
Output is correct |
5 |
Correct |
277 ms |
3664 KB |
Output is correct |
6 |
Correct |
241 ms |
3976 KB |
Output is correct |
7 |
Correct |
263 ms |
3924 KB |
Output is correct |
8 |
Correct |
266 ms |
3924 KB |
Output is correct |
9 |
Correct |
20 ms |
2396 KB |
Output is correct |
10 |
Correct |
222 ms |
3980 KB |
Output is correct |
11 |
Correct |
239 ms |
4156 KB |
Output is correct |
12 |
Correct |
440 ms |
4260 KB |
Output is correct |
13 |
Correct |
91 ms |
3668 KB |
Output is correct |
14 |
Correct |
767 ms |
73468 KB |
Output is correct |
15 |
Correct |
493 ms |
98732 KB |
Output is correct |
16 |
Correct |
803 ms |
101616 KB |
Output is correct |
17 |
Correct |
761 ms |
73100 KB |
Output is correct |
18 |
Correct |
20 ms |
2396 KB |
Output is correct |
19 |
Correct |
804 ms |
92928 KB |
Output is correct |
20 |
Correct |
711 ms |
65276 KB |
Output is correct |
21 |
Correct |
630 ms |
49268 KB |
Output is correct |
22 |
Correct |
530 ms |
41076 KB |
Output is correct |
23 |
Correct |
503 ms |
29648 KB |
Output is correct |
24 |
Correct |
570 ms |
38752 KB |
Output is correct |
25 |
Correct |
489 ms |
28624 KB |
Output is correct |
26 |
Correct |
1002 ms |
74024 KB |
Output is correct |
27 |
Correct |
1126 ms |
103208 KB |
Output is correct |
28 |
Correct |
1032 ms |
74192 KB |
Output is correct |
29 |
Correct |
784 ms |
31300 KB |
Output is correct |
30 |
Correct |
1076 ms |
91656 KB |
Output is correct |
31 |
Correct |
1124 ms |
94476 KB |
Output is correct |
32 |
Correct |
1128 ms |
94736 KB |
Output is correct |
33 |
Correct |
1006 ms |
74572 KB |
Output is correct |
34 |
Correct |
1012 ms |
75072 KB |
Output is correct |
35 |
Correct |
1022 ms |
75052 KB |
Output is correct |
36 |
Correct |
847 ms |
38412 KB |
Output is correct |
37 |
Correct |
810 ms |
37116 KB |
Output is correct |
38 |
Correct |
807 ms |
35472 KB |
Output is correct |
39 |
Correct |
688 ms |
21932 KB |
Output is correct |
40 |
Correct |
680 ms |
21008 KB |
Output is correct |
41 |
Correct |
687 ms |
20104 KB |
Output is correct |
42 |
Correct |
665 ms |
20084 KB |
Output is correct |
43 |
Correct |
673 ms |
19312 KB |
Output is correct |
44 |
Correct |
654 ms |
18704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
35 ms |
704 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
5 ms |
604 KB |
Output is correct |
6 |
Correct |
4 ms |
656 KB |
Output is correct |
7 |
Correct |
4 ms |
600 KB |
Output is correct |
8 |
Correct |
4 ms |
604 KB |
Output is correct |
9 |
Correct |
5 ms |
604 KB |
Output is correct |
10 |
Correct |
3 ms |
672 KB |
Output is correct |
11 |
Correct |
3 ms |
604 KB |
Output is correct |
12 |
Correct |
3 ms |
604 KB |
Output is correct |
13 |
Correct |
5 ms |
604 KB |
Output is correct |
14 |
Correct |
4 ms |
680 KB |
Output is correct |
15 |
Correct |
6 ms |
600 KB |
Output is correct |
16 |
Correct |
4 ms |
604 KB |
Output is correct |
17 |
Correct |
4 ms |
680 KB |
Output is correct |
18 |
Correct |
289 ms |
3828 KB |
Output is correct |
19 |
Correct |
284 ms |
3988 KB |
Output is correct |
20 |
Correct |
280 ms |
3668 KB |
Output is correct |
21 |
Correct |
278 ms |
3776 KB |
Output is correct |
22 |
Correct |
277 ms |
3664 KB |
Output is correct |
23 |
Correct |
241 ms |
3976 KB |
Output is correct |
24 |
Correct |
263 ms |
3924 KB |
Output is correct |
25 |
Correct |
266 ms |
3924 KB |
Output is correct |
26 |
Correct |
20 ms |
2396 KB |
Output is correct |
27 |
Correct |
222 ms |
3980 KB |
Output is correct |
28 |
Correct |
239 ms |
4156 KB |
Output is correct |
29 |
Correct |
440 ms |
4260 KB |
Output is correct |
30 |
Correct |
91 ms |
3668 KB |
Output is correct |
31 |
Correct |
767 ms |
73468 KB |
Output is correct |
32 |
Correct |
493 ms |
98732 KB |
Output is correct |
33 |
Correct |
803 ms |
101616 KB |
Output is correct |
34 |
Correct |
761 ms |
73100 KB |
Output is correct |
35 |
Correct |
20 ms |
2396 KB |
Output is correct |
36 |
Correct |
804 ms |
92928 KB |
Output is correct |
37 |
Correct |
711 ms |
65276 KB |
Output is correct |
38 |
Correct |
630 ms |
49268 KB |
Output is correct |
39 |
Correct |
530 ms |
41076 KB |
Output is correct |
40 |
Correct |
503 ms |
29648 KB |
Output is correct |
41 |
Correct |
570 ms |
38752 KB |
Output is correct |
42 |
Correct |
489 ms |
28624 KB |
Output is correct |
43 |
Correct |
67 ms |
6264 KB |
Output is correct |
44 |
Correct |
21 ms |
2572 KB |
Output is correct |
45 |
Correct |
29 ms |
2780 KB |
Output is correct |
46 |
Correct |
26 ms |
2780 KB |
Output is correct |
47 |
Correct |
46 ms |
6240 KB |
Output is correct |
48 |
Correct |
63 ms |
6272 KB |
Output is correct |
49 |
Correct |
47 ms |
6196 KB |
Output is correct |
50 |
Correct |
47 ms |
4944 KB |
Output is correct |
51 |
Correct |
50 ms |
5136 KB |
Output is correct |
52 |
Correct |
51 ms |
5316 KB |
Output is correct |
53 |
Correct |
56 ms |
5712 KB |
Output is correct |
54 |
Correct |
55 ms |
5708 KB |
Output is correct |
55 |
Correct |
57 ms |
5716 KB |
Output is correct |
56 |
Correct |
45 ms |
6484 KB |
Output is correct |
57 |
Correct |
46 ms |
6428 KB |
Output is correct |
58 |
Correct |
64 ms |
6228 KB |
Output is correct |
59 |
Correct |
64 ms |
6224 KB |
Output is correct |
60 |
Correct |
64 ms |
6272 KB |
Output is correct |
61 |
Correct |
70 ms |
6224 KB |
Output is correct |
62 |
Correct |
57 ms |
6048 KB |
Output is correct |
63 |
Correct |
55 ms |
6144 KB |
Output is correct |
64 |
Correct |
65 ms |
6220 KB |
Output is correct |
65 |
Correct |
43 ms |
5972 KB |
Output is correct |
66 |
Correct |
1002 ms |
74024 KB |
Output is correct |
67 |
Correct |
1126 ms |
103208 KB |
Output is correct |
68 |
Correct |
1032 ms |
74192 KB |
Output is correct |
69 |
Correct |
784 ms |
31300 KB |
Output is correct |
70 |
Correct |
1076 ms |
91656 KB |
Output is correct |
71 |
Correct |
1124 ms |
94476 KB |
Output is correct |
72 |
Correct |
1128 ms |
94736 KB |
Output is correct |
73 |
Correct |
1006 ms |
74572 KB |
Output is correct |
74 |
Correct |
1012 ms |
75072 KB |
Output is correct |
75 |
Correct |
1022 ms |
75052 KB |
Output is correct |
76 |
Correct |
847 ms |
38412 KB |
Output is correct |
77 |
Correct |
810 ms |
37116 KB |
Output is correct |
78 |
Correct |
807 ms |
35472 KB |
Output is correct |
79 |
Correct |
688 ms |
21932 KB |
Output is correct |
80 |
Correct |
680 ms |
21008 KB |
Output is correct |
81 |
Correct |
687 ms |
20104 KB |
Output is correct |
82 |
Correct |
665 ms |
20084 KB |
Output is correct |
83 |
Correct |
673 ms |
19312 KB |
Output is correct |
84 |
Correct |
654 ms |
18704 KB |
Output is correct |
85 |
Correct |
1666 ms |
74964 KB |
Output is correct |
86 |
Correct |
166 ms |
9468 KB |
Output is correct |
87 |
Correct |
90 ms |
13888 KB |
Output is correct |
88 |
Correct |
919 ms |
88648 KB |
Output is correct |
89 |
Correct |
1630 ms |
73664 KB |
Output is correct |
90 |
Correct |
940 ms |
97160 KB |
Output is correct |
91 |
Correct |
1040 ms |
74044 KB |
Output is correct |
92 |
Correct |
1032 ms |
73500 KB |
Output is correct |
93 |
Correct |
1256 ms |
111588 KB |
Output is correct |
94 |
Correct |
1387 ms |
74380 KB |
Output is correct |
95 |
Correct |
1376 ms |
74524 KB |
Output is correct |
96 |
Correct |
1450 ms |
115112 KB |
Output is correct |
97 |
Correct |
760 ms |
41100 KB |
Output is correct |
98 |
Correct |
750 ms |
37936 KB |
Output is correct |
99 |
Correct |
1714 ms |
75988 KB |
Output is correct |
100 |
Correct |
1720 ms |
74952 KB |
Output is correct |
101 |
Correct |
1719 ms |
74708 KB |
Output is correct |
102 |
Correct |
1667 ms |
74744 KB |
Output is correct |
103 |
Correct |
1583 ms |
120648 KB |
Output is correct |
104 |
Correct |
1592 ms |
119836 KB |
Output is correct |
105 |
Correct |
1272 ms |
47716 KB |
Output is correct |
106 |
Correct |
1064 ms |
27756 KB |
Output is correct |
107 |
Correct |
1333 ms |
54456 KB |
Output is correct |
108 |
Correct |
1692 ms |
110292 KB |
Output is correct |
109 |
Correct |
1160 ms |
115252 KB |
Output is correct |