// APIO19_bridges
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'
#define MAXN 50100
#define MAXE 100100
#define SQ 1000
int n, m, q;
int efrom[MAXE], eto[MAXE], ew[MAXE];
int ans[MAXE];
int tp[MAXE], qx[MAXE], qy[MAXE];
vector<int> asks[MAXE / SQ + 10]; // indexes of asks sorted by w
unordered_set<int> upds[MAXE / SQ + 10]; // edges that get updated
vector<int> edge;
int curw[MAXE];
// dsu
vector<int> undo_stk;
int dsu[MAXN];
int sz[MAXN];
int getroot(int x)
{
return dsu[x] == x ? x : getroot(dsu[x]);
}
void merge(int x, int y)
{
x = getroot(x);
y = getroot(y);
if (x == y)
{
undo_stk.pb(-1);
return;
}
if (sz[x] > sz[y]) swap(x, y);
dsu[x] = y;
sz[y] += sz[x];
undo_stk.pb(x);
}
void undo(void)
{
int x = undo_stk.back();
undo_stk.pop_back();
if (x < 0) return;
sz[dsu[x]] -= sz[x];
dsu[x] = x;
}
void rebuild(int b)
{
// clear dsu
undo_stk.clear();
iota(dsu, dsu + n + 10, 0);
fill(sz, sz + n + 10, 1);
// sort edges
edge.clear();
FOR(i, 0, m)
if (upds[b].find(i) == upds[b].end())
edge.pb(i);
sort(all(edge), [&](int x, int y){ return ew[x] < ew[y]; });
// sort asks
sort(all(asks[b]), [&](int x, int y){ return qy[x] > qy[y]; });
}
int32_t main(void)
{
fast_io;
cin >> n >> m;
FOR(i, 0, m)
{
cin >> efrom[i] >> eto[i] >> ew[i];
}
cin >> q;
FOR(i, 0, q)
{
cin >> tp[i] >> qx[i] >> qy[i];
if (tp[i] == 2) asks[i/SQ].pb(i);
else
{
qx[i]--;
upds[i / SQ].insert(qx[i]);
}
}
for (int b = 0; b <= q/SQ; b++)
{
rebuild(b);
int ptr = edge.size() - 1;
for (int i : asks[b])
{
while (ptr >= 0 && ew[edge[ptr]] >= qy[i])
{
merge(efrom[edge[ptr]], eto[edge[ptr]]);
ptr--;
}
// merge recent edges
vector<int> upe;
for (int e : upds[b]) upe.pb(e);
for (int e : upe) curw[e] = ew[e];
FOR(j, b * SQ, i)
{
if (tp[j] == 2) continue;
curw[qx[j]] = qy[j];
}
int cnt = 0;
for (int e : upe) if (curw[e] >= qy[i]) merge(efrom[e], eto[e]), cnt++;;
// answer the query
ans[i] = sz[getroot(qx[i])];
// undo dsu
FOR(j, 0, cnt)
undo();
}
FOR(i, b * SQ, min(q + 1, (b +1) * SQ)) if (tp[i] == 1) ew[qx[i]] = qy[i];
}
FOR(i, 0, q) if (tp[i] == 2)
cout << ans[i] << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
55 ms |
720 KB |
Output is correct |
4 |
Correct |
10 ms |
460 KB |
Output is correct |
5 |
Correct |
19 ms |
588 KB |
Output is correct |
6 |
Correct |
17 ms |
572 KB |
Output is correct |
7 |
Correct |
19 ms |
596 KB |
Output is correct |
8 |
Correct |
20 ms |
588 KB |
Output is correct |
9 |
Correct |
21 ms |
600 KB |
Output is correct |
10 |
Correct |
20 ms |
588 KB |
Output is correct |
11 |
Correct |
20 ms |
588 KB |
Output is correct |
12 |
Correct |
22 ms |
600 KB |
Output is correct |
13 |
Correct |
27 ms |
608 KB |
Output is correct |
14 |
Correct |
26 ms |
588 KB |
Output is correct |
15 |
Correct |
22 ms |
592 KB |
Output is correct |
16 |
Correct |
20 ms |
592 KB |
Output is correct |
17 |
Correct |
20 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1734 ms |
6240 KB |
Output is correct |
2 |
Correct |
1688 ms |
6216 KB |
Output is correct |
3 |
Correct |
1680 ms |
6052 KB |
Output is correct |
4 |
Correct |
1728 ms |
6068 KB |
Output is correct |
5 |
Correct |
1725 ms |
6052 KB |
Output is correct |
6 |
Correct |
2441 ms |
6540 KB |
Output is correct |
7 |
Correct |
2461 ms |
6300 KB |
Output is correct |
8 |
Correct |
2422 ms |
6364 KB |
Output is correct |
9 |
Correct |
111 ms |
2376 KB |
Output is correct |
10 |
Correct |
1529 ms |
6160 KB |
Output is correct |
11 |
Correct |
1393 ms |
6228 KB |
Output is correct |
12 |
Correct |
1439 ms |
4960 KB |
Output is correct |
13 |
Correct |
1419 ms |
7832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1462 ms |
5704 KB |
Output is correct |
2 |
Correct |
1120 ms |
4760 KB |
Output is correct |
3 |
Correct |
1698 ms |
5672 KB |
Output is correct |
4 |
Correct |
1397 ms |
5568 KB |
Output is correct |
5 |
Correct |
95 ms |
2372 KB |
Output is correct |
6 |
Correct |
1559 ms |
5688 KB |
Output is correct |
7 |
Correct |
1310 ms |
5572 KB |
Output is correct |
8 |
Correct |
1179 ms |
5740 KB |
Output is correct |
9 |
Correct |
932 ms |
4292 KB |
Output is correct |
10 |
Correct |
863 ms |
4140 KB |
Output is correct |
11 |
Correct |
943 ms |
7416 KB |
Output is correct |
12 |
Correct |
837 ms |
7264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1734 ms |
5212 KB |
Output is correct |
2 |
Correct |
91 ms |
3908 KB |
Output is correct |
3 |
Correct |
190 ms |
4688 KB |
Output is correct |
4 |
Correct |
92 ms |
4796 KB |
Output is correct |
5 |
Correct |
899 ms |
7476 KB |
Output is correct |
6 |
Correct |
1715 ms |
9044 KB |
Output is correct |
7 |
Correct |
921 ms |
7644 KB |
Output is correct |
8 |
Correct |
866 ms |
6748 KB |
Output is correct |
9 |
Correct |
855 ms |
6772 KB |
Output is correct |
10 |
Correct |
863 ms |
6740 KB |
Output is correct |
11 |
Correct |
1315 ms |
7884 KB |
Output is correct |
12 |
Correct |
1307 ms |
7880 KB |
Output is correct |
13 |
Correct |
1306 ms |
7848 KB |
Output is correct |
14 |
Correct |
811 ms |
7596 KB |
Output is correct |
15 |
Correct |
877 ms |
7880 KB |
Output is correct |
16 |
Correct |
1725 ms |
8924 KB |
Output is correct |
17 |
Correct |
1760 ms |
9088 KB |
Output is correct |
18 |
Correct |
1752 ms |
9088 KB |
Output is correct |
19 |
Correct |
1743 ms |
9144 KB |
Output is correct |
20 |
Correct |
1496 ms |
8148 KB |
Output is correct |
21 |
Correct |
1482 ms |
8088 KB |
Output is correct |
22 |
Correct |
1691 ms |
8904 KB |
Output is correct |
23 |
Correct |
987 ms |
6980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1734 ms |
6240 KB |
Output is correct |
2 |
Correct |
1688 ms |
6216 KB |
Output is correct |
3 |
Correct |
1680 ms |
6052 KB |
Output is correct |
4 |
Correct |
1728 ms |
6068 KB |
Output is correct |
5 |
Correct |
1725 ms |
6052 KB |
Output is correct |
6 |
Correct |
2441 ms |
6540 KB |
Output is correct |
7 |
Correct |
2461 ms |
6300 KB |
Output is correct |
8 |
Correct |
2422 ms |
6364 KB |
Output is correct |
9 |
Correct |
111 ms |
2376 KB |
Output is correct |
10 |
Correct |
1529 ms |
6160 KB |
Output is correct |
11 |
Correct |
1393 ms |
6228 KB |
Output is correct |
12 |
Correct |
1439 ms |
4960 KB |
Output is correct |
13 |
Correct |
1419 ms |
7832 KB |
Output is correct |
14 |
Correct |
1462 ms |
5704 KB |
Output is correct |
15 |
Correct |
1120 ms |
4760 KB |
Output is correct |
16 |
Correct |
1698 ms |
5672 KB |
Output is correct |
17 |
Correct |
1397 ms |
5568 KB |
Output is correct |
18 |
Correct |
95 ms |
2372 KB |
Output is correct |
19 |
Correct |
1559 ms |
5688 KB |
Output is correct |
20 |
Correct |
1310 ms |
5572 KB |
Output is correct |
21 |
Correct |
1179 ms |
5740 KB |
Output is correct |
22 |
Correct |
932 ms |
4292 KB |
Output is correct |
23 |
Correct |
863 ms |
4140 KB |
Output is correct |
24 |
Correct |
943 ms |
7416 KB |
Output is correct |
25 |
Correct |
837 ms |
7264 KB |
Output is correct |
26 |
Correct |
1827 ms |
6112 KB |
Output is correct |
27 |
Correct |
2088 ms |
6288 KB |
Output is correct |
28 |
Correct |
1788 ms |
6296 KB |
Output is correct |
29 |
Correct |
1372 ms |
6132 KB |
Output is correct |
30 |
Correct |
2031 ms |
6284 KB |
Output is correct |
31 |
Correct |
2033 ms |
6124 KB |
Output is correct |
32 |
Correct |
2060 ms |
6208 KB |
Output is correct |
33 |
Correct |
1810 ms |
6156 KB |
Output is correct |
34 |
Correct |
1777 ms |
6108 KB |
Output is correct |
35 |
Correct |
1760 ms |
6068 KB |
Output is correct |
36 |
Correct |
1428 ms |
6208 KB |
Output is correct |
37 |
Correct |
1405 ms |
6208 KB |
Output is correct |
38 |
Correct |
1415 ms |
6076 KB |
Output is correct |
39 |
Correct |
1107 ms |
4544 KB |
Output is correct |
40 |
Correct |
1113 ms |
4752 KB |
Output is correct |
41 |
Correct |
1101 ms |
4580 KB |
Output is correct |
42 |
Correct |
1096 ms |
7808 KB |
Output is correct |
43 |
Correct |
1057 ms |
7924 KB |
Output is correct |
44 |
Correct |
1050 ms |
8032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
55 ms |
720 KB |
Output is correct |
4 |
Correct |
10 ms |
460 KB |
Output is correct |
5 |
Correct |
19 ms |
588 KB |
Output is correct |
6 |
Correct |
17 ms |
572 KB |
Output is correct |
7 |
Correct |
19 ms |
596 KB |
Output is correct |
8 |
Correct |
20 ms |
588 KB |
Output is correct |
9 |
Correct |
21 ms |
600 KB |
Output is correct |
10 |
Correct |
20 ms |
588 KB |
Output is correct |
11 |
Correct |
20 ms |
588 KB |
Output is correct |
12 |
Correct |
22 ms |
600 KB |
Output is correct |
13 |
Correct |
27 ms |
608 KB |
Output is correct |
14 |
Correct |
26 ms |
588 KB |
Output is correct |
15 |
Correct |
22 ms |
592 KB |
Output is correct |
16 |
Correct |
20 ms |
592 KB |
Output is correct |
17 |
Correct |
20 ms |
588 KB |
Output is correct |
18 |
Correct |
1734 ms |
6240 KB |
Output is correct |
19 |
Correct |
1688 ms |
6216 KB |
Output is correct |
20 |
Correct |
1680 ms |
6052 KB |
Output is correct |
21 |
Correct |
1728 ms |
6068 KB |
Output is correct |
22 |
Correct |
1725 ms |
6052 KB |
Output is correct |
23 |
Correct |
2441 ms |
6540 KB |
Output is correct |
24 |
Correct |
2461 ms |
6300 KB |
Output is correct |
25 |
Correct |
2422 ms |
6364 KB |
Output is correct |
26 |
Correct |
111 ms |
2376 KB |
Output is correct |
27 |
Correct |
1529 ms |
6160 KB |
Output is correct |
28 |
Correct |
1393 ms |
6228 KB |
Output is correct |
29 |
Correct |
1439 ms |
4960 KB |
Output is correct |
30 |
Correct |
1419 ms |
7832 KB |
Output is correct |
31 |
Correct |
1462 ms |
5704 KB |
Output is correct |
32 |
Correct |
1120 ms |
4760 KB |
Output is correct |
33 |
Correct |
1698 ms |
5672 KB |
Output is correct |
34 |
Correct |
1397 ms |
5568 KB |
Output is correct |
35 |
Correct |
95 ms |
2372 KB |
Output is correct |
36 |
Correct |
1559 ms |
5688 KB |
Output is correct |
37 |
Correct |
1310 ms |
5572 KB |
Output is correct |
38 |
Correct |
1179 ms |
5740 KB |
Output is correct |
39 |
Correct |
932 ms |
4292 KB |
Output is correct |
40 |
Correct |
863 ms |
4140 KB |
Output is correct |
41 |
Correct |
943 ms |
7416 KB |
Output is correct |
42 |
Correct |
837 ms |
7264 KB |
Output is correct |
43 |
Correct |
1734 ms |
5212 KB |
Output is correct |
44 |
Correct |
91 ms |
3908 KB |
Output is correct |
45 |
Correct |
190 ms |
4688 KB |
Output is correct |
46 |
Correct |
92 ms |
4796 KB |
Output is correct |
47 |
Correct |
899 ms |
7476 KB |
Output is correct |
48 |
Correct |
1715 ms |
9044 KB |
Output is correct |
49 |
Correct |
921 ms |
7644 KB |
Output is correct |
50 |
Correct |
866 ms |
6748 KB |
Output is correct |
51 |
Correct |
855 ms |
6772 KB |
Output is correct |
52 |
Correct |
863 ms |
6740 KB |
Output is correct |
53 |
Correct |
1315 ms |
7884 KB |
Output is correct |
54 |
Correct |
1307 ms |
7880 KB |
Output is correct |
55 |
Correct |
1306 ms |
7848 KB |
Output is correct |
56 |
Correct |
811 ms |
7596 KB |
Output is correct |
57 |
Correct |
877 ms |
7880 KB |
Output is correct |
58 |
Correct |
1725 ms |
8924 KB |
Output is correct |
59 |
Correct |
1760 ms |
9088 KB |
Output is correct |
60 |
Correct |
1752 ms |
9088 KB |
Output is correct |
61 |
Correct |
1743 ms |
9144 KB |
Output is correct |
62 |
Correct |
1496 ms |
8148 KB |
Output is correct |
63 |
Correct |
1482 ms |
8088 KB |
Output is correct |
64 |
Correct |
1691 ms |
8904 KB |
Output is correct |
65 |
Correct |
987 ms |
6980 KB |
Output is correct |
66 |
Correct |
1827 ms |
6112 KB |
Output is correct |
67 |
Correct |
2088 ms |
6288 KB |
Output is correct |
68 |
Correct |
1788 ms |
6296 KB |
Output is correct |
69 |
Correct |
1372 ms |
6132 KB |
Output is correct |
70 |
Correct |
2031 ms |
6284 KB |
Output is correct |
71 |
Correct |
2033 ms |
6124 KB |
Output is correct |
72 |
Correct |
2060 ms |
6208 KB |
Output is correct |
73 |
Correct |
1810 ms |
6156 KB |
Output is correct |
74 |
Correct |
1777 ms |
6108 KB |
Output is correct |
75 |
Correct |
1760 ms |
6068 KB |
Output is correct |
76 |
Correct |
1428 ms |
6208 KB |
Output is correct |
77 |
Correct |
1405 ms |
6208 KB |
Output is correct |
78 |
Correct |
1415 ms |
6076 KB |
Output is correct |
79 |
Correct |
1107 ms |
4544 KB |
Output is correct |
80 |
Correct |
1113 ms |
4752 KB |
Output is correct |
81 |
Correct |
1101 ms |
4580 KB |
Output is correct |
82 |
Correct |
1096 ms |
7808 KB |
Output is correct |
83 |
Correct |
1057 ms |
7924 KB |
Output is correct |
84 |
Correct |
1050 ms |
8032 KB |
Output is correct |
85 |
Correct |
2584 ms |
11316 KB |
Output is correct |
86 |
Correct |
254 ms |
5188 KB |
Output is correct |
87 |
Correct |
180 ms |
5220 KB |
Output is correct |
88 |
Correct |
1734 ms |
9972 KB |
Output is correct |
89 |
Correct |
2556 ms |
11348 KB |
Output is correct |
90 |
Correct |
1725 ms |
9536 KB |
Output is correct |
91 |
Correct |
1818 ms |
8740 KB |
Output is correct |
92 |
Correct |
1823 ms |
9012 KB |
Output is correct |
93 |
Correct |
2495 ms |
8804 KB |
Output is correct |
94 |
Correct |
2203 ms |
9876 KB |
Output is correct |
95 |
Correct |
2210 ms |
10208 KB |
Output is correct |
96 |
Correct |
2629 ms |
9876 KB |
Output is correct |
97 |
Correct |
1267 ms |
8128 KB |
Output is correct |
98 |
Correct |
1371 ms |
11084 KB |
Output is correct |
99 |
Correct |
2761 ms |
11084 KB |
Output is correct |
100 |
Correct |
2788 ms |
11092 KB |
Output is correct |
101 |
Correct |
2837 ms |
11244 KB |
Output is correct |
102 |
Correct |
2685 ms |
11252 KB |
Output is correct |
103 |
Correct |
2914 ms |
10208 KB |
Output is correct |
104 |
Correct |
2901 ms |
10264 KB |
Output is correct |
105 |
Correct |
2015 ms |
11988 KB |
Output is correct |
106 |
Correct |
1604 ms |
11664 KB |
Output is correct |
107 |
Correct |
1968 ms |
8812 KB |
Output is correct |
108 |
Correct |
2695 ms |
10860 KB |
Output is correct |
109 |
Correct |
2126 ms |
9144 KB |
Output is correct |