#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5, B = 1044;
struct Edge
{
int x, y, c;
};
struct Query
{
int t, x, c;
};
int n, m, nq, lim;
int last[Nmax], nxt[Nmax], prv[Nmax];
Edge edge[Nmax];
Query q[Nmax];
int ans[Nmax];
vector<int> modif, query[Nmax], when[Nmax];
static void read()
{
int i;
cin >> n >> m;
for(i=1; i<=m; ++i)
cin >> edge[i].x >> edge[i].y >> edge[i].c;
cin >> nq;
for(i=1; i<=nq; ++i) cin >> q[i].t >> q[i].x >> q[i].c;
for(i=1; i<=nq; ++i)
if(q[i].t == 1)
{
prv[i] = last[q[i].x];
last[q[i].x] = i;
}
for(i=1; i<=m; ++i) last[i] = 1e9;
for(i=nq; i; --i)
if(q[i].t == 1)
{
nxt[i] = last[q[i].x];
last[q[i].x] = i;
}
for(i=1; i<=m; ++i) last[i] = 0;
}
static void normalize()
{
vector<int> all;
int i;
for(i=1; i<=m; ++i) all.push_back(edge[i].c);
for(i=1; i<=nq; ++i)
if(q[i].t == 1)
all.push_back(q[i].c);
sort(all.begin(), all.end());
all.erase( unique(all.begin(), all.end()), all.end() );
lim = all.size();
for(i=1; i<=m; ++i)
edge[i].c = lower_bound(all.begin(), all.end(), edge[i].c) - all.begin();
for(i=1; i<=nq; ++i)
q[i].c = lower_bound(all.begin(), all.end(), q[i].c) - all.begin();
}
struct DisjDataSet
{
int t[Nmax];
int s[Nmax];
int tip;
vector<int> who, old_size;
int boss(int x)
{
if(x == t[x]) return x;
int dad = boss(t[x]);
if(tip == 1) t[x] = dad;
return dad;
}
void reset()
{
int i; tip = -1;
for(i=1; i<=n; ++i) t[i] = i, s[i] = 1;
}
void unite(int x, int y)
{
x = boss(x); y = boss(y);
if(x == y) return;
if(s[x] > s[y]) swap(x, y);
if(tip == 2)
who.push_back(x), old_size.push_back(s[x]);
t[x] = y;
s[y] += s[x];
}
void undo()
{
int i;
for(i=who.size()-1; i>=0; --i)
s[t[who[i]]] -= old_size[i], t[who[i]] = who[i];
who.clear(); old_size.clear();
}
int get_size(int x)
{
x = boss(x);
return s[x];
}
} forest;
static void solve(int start)
{
int i;
///
modif.clear();
for(i=0; i<=lim; ++i)
when[i].clear(), query[i].clear();
forest.reset();
///
for(i=start; i<start+B && i<=nq; ++i)
if(q[i].t == 1)
{
last[q[i].x] = i;
modif.push_back(i);
}
else query[q[i].c].push_back(i);
for(i=1; i<=m; ++i)
if(last[i] < start)
when[edge[i].c].push_back(i);
for(i=lim; i>=0; --i)
{
///
forest.tip = 1;
for(auto &it : when[i])
forest.unite(edge[it].x, edge[it].y);
///
forest.tip = 2;
for(auto &it : query[i])
{
for(auto &j : modif)
if( (j < it && nxt[j] > it && q[j].c >= i) || (prv[j] < start && j > it && edge[q[j].x].c >= i) )
forest.unite(edge[q[j].x].x, edge[q[j].x].y);
ans[it] = forest.get_size(q[it].x);
forest.undo();
}
}
for(auto &j : modif)
edge[q[j].x].c = q[j].c;
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false); cin.tie(0);
read();
normalize();
int i;
for(i=1; i<=nq; i+=B)
solve(i);
for(i=1; i<=nq; ++i)
if(q[i].t == 2)
cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
11 ms |
9848 KB |
Output is correct |
3 |
Correct |
33 ms |
10232 KB |
Output is correct |
4 |
Correct |
16 ms |
9976 KB |
Output is correct |
5 |
Correct |
30 ms |
10104 KB |
Output is correct |
6 |
Correct |
26 ms |
10104 KB |
Output is correct |
7 |
Correct |
29 ms |
10104 KB |
Output is correct |
8 |
Correct |
32 ms |
10104 KB |
Output is correct |
9 |
Correct |
32 ms |
10104 KB |
Output is correct |
10 |
Correct |
33 ms |
10104 KB |
Output is correct |
11 |
Correct |
33 ms |
10232 KB |
Output is correct |
12 |
Correct |
34 ms |
10104 KB |
Output is correct |
13 |
Correct |
41 ms |
10108 KB |
Output is correct |
14 |
Correct |
37 ms |
10104 KB |
Output is correct |
15 |
Correct |
34 ms |
10104 KB |
Output is correct |
16 |
Correct |
30 ms |
10104 KB |
Output is correct |
17 |
Correct |
30 ms |
10104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1760 ms |
17652 KB |
Output is correct |
2 |
Correct |
1725 ms |
17632 KB |
Output is correct |
3 |
Correct |
1729 ms |
17516 KB |
Output is correct |
4 |
Correct |
1820 ms |
17520 KB |
Output is correct |
5 |
Correct |
1761 ms |
17664 KB |
Output is correct |
6 |
Correct |
2437 ms |
16776 KB |
Output is correct |
7 |
Correct |
2521 ms |
16928 KB |
Output is correct |
8 |
Correct |
2443 ms |
16848 KB |
Output is correct |
9 |
Correct |
45 ms |
11512 KB |
Output is correct |
10 |
Correct |
1150 ms |
13920 KB |
Output is correct |
11 |
Correct |
1057 ms |
14044 KB |
Output is correct |
12 |
Correct |
1188 ms |
15704 KB |
Output is correct |
13 |
Correct |
1667 ms |
17580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1340 ms |
16704 KB |
Output is correct |
2 |
Correct |
1020 ms |
14896 KB |
Output is correct |
3 |
Correct |
1532 ms |
16288 KB |
Output is correct |
4 |
Correct |
1269 ms |
16676 KB |
Output is correct |
5 |
Correct |
46 ms |
11512 KB |
Output is correct |
6 |
Correct |
1475 ms |
16548 KB |
Output is correct |
7 |
Correct |
1180 ms |
16672 KB |
Output is correct |
8 |
Correct |
1054 ms |
16400 KB |
Output is correct |
9 |
Correct |
697 ms |
15556 KB |
Output is correct |
10 |
Correct |
626 ms |
15276 KB |
Output is correct |
11 |
Correct |
1053 ms |
16900 KB |
Output is correct |
12 |
Correct |
945 ms |
16904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1641 ms |
18456 KB |
Output is correct |
2 |
Correct |
46 ms |
12920 KB |
Output is correct |
3 |
Correct |
206 ms |
16476 KB |
Output is correct |
4 |
Correct |
69 ms |
13916 KB |
Output is correct |
5 |
Correct |
414 ms |
15968 KB |
Output is correct |
6 |
Correct |
1653 ms |
20080 KB |
Output is correct |
7 |
Correct |
413 ms |
15968 KB |
Output is correct |
8 |
Correct |
659 ms |
16916 KB |
Output is correct |
9 |
Correct |
633 ms |
16836 KB |
Output is correct |
10 |
Correct |
633 ms |
16056 KB |
Output is correct |
11 |
Correct |
1162 ms |
18624 KB |
Output is correct |
12 |
Correct |
1141 ms |
18496 KB |
Output is correct |
13 |
Correct |
1118 ms |
17464 KB |
Output is correct |
14 |
Correct |
402 ms |
16356 KB |
Output is correct |
15 |
Correct |
409 ms |
16092 KB |
Output is correct |
16 |
Correct |
1793 ms |
20036 KB |
Output is correct |
17 |
Correct |
1732 ms |
20192 KB |
Output is correct |
18 |
Correct |
1750 ms |
20192 KB |
Output is correct |
19 |
Correct |
1710 ms |
19936 KB |
Output is correct |
20 |
Correct |
1265 ms |
17984 KB |
Output is correct |
21 |
Correct |
1262 ms |
17952 KB |
Output is correct |
22 |
Correct |
1610 ms |
19204 KB |
Output is correct |
23 |
Correct |
475 ms |
15532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1760 ms |
17652 KB |
Output is correct |
2 |
Correct |
1725 ms |
17632 KB |
Output is correct |
3 |
Correct |
1729 ms |
17516 KB |
Output is correct |
4 |
Correct |
1820 ms |
17520 KB |
Output is correct |
5 |
Correct |
1761 ms |
17664 KB |
Output is correct |
6 |
Correct |
2437 ms |
16776 KB |
Output is correct |
7 |
Correct |
2521 ms |
16928 KB |
Output is correct |
8 |
Correct |
2443 ms |
16848 KB |
Output is correct |
9 |
Correct |
45 ms |
11512 KB |
Output is correct |
10 |
Correct |
1150 ms |
13920 KB |
Output is correct |
11 |
Correct |
1057 ms |
14044 KB |
Output is correct |
12 |
Correct |
1188 ms |
15704 KB |
Output is correct |
13 |
Correct |
1667 ms |
17580 KB |
Output is correct |
14 |
Correct |
1340 ms |
16704 KB |
Output is correct |
15 |
Correct |
1020 ms |
14896 KB |
Output is correct |
16 |
Correct |
1532 ms |
16288 KB |
Output is correct |
17 |
Correct |
1269 ms |
16676 KB |
Output is correct |
18 |
Correct |
46 ms |
11512 KB |
Output is correct |
19 |
Correct |
1475 ms |
16548 KB |
Output is correct |
20 |
Correct |
1180 ms |
16672 KB |
Output is correct |
21 |
Correct |
1054 ms |
16400 KB |
Output is correct |
22 |
Correct |
697 ms |
15556 KB |
Output is correct |
23 |
Correct |
626 ms |
15276 KB |
Output is correct |
24 |
Correct |
1053 ms |
16900 KB |
Output is correct |
25 |
Correct |
945 ms |
16904 KB |
Output is correct |
26 |
Correct |
1725 ms |
17652 KB |
Output is correct |
27 |
Correct |
2009 ms |
17248 KB |
Output is correct |
28 |
Correct |
1756 ms |
17760 KB |
Output is correct |
29 |
Correct |
1302 ms |
17176 KB |
Output is correct |
30 |
Correct |
2099 ms |
17348 KB |
Output is correct |
31 |
Correct |
2098 ms |
17572 KB |
Output is correct |
32 |
Correct |
2058 ms |
17608 KB |
Output is correct |
33 |
Correct |
1750 ms |
17508 KB |
Output is correct |
34 |
Correct |
1778 ms |
17536 KB |
Output is correct |
35 |
Correct |
1773 ms |
17692 KB |
Output is correct |
36 |
Correct |
1560 ms |
17244 KB |
Output is correct |
37 |
Correct |
1403 ms |
17164 KB |
Output is correct |
38 |
Correct |
1358 ms |
17228 KB |
Output is correct |
39 |
Correct |
866 ms |
16272 KB |
Output is correct |
40 |
Correct |
883 ms |
16352 KB |
Output is correct |
41 |
Correct |
1053 ms |
16104 KB |
Output is correct |
42 |
Correct |
1513 ms |
17932 KB |
Output is correct |
43 |
Correct |
1377 ms |
17852 KB |
Output is correct |
44 |
Correct |
1628 ms |
17804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
11 ms |
9848 KB |
Output is correct |
3 |
Correct |
33 ms |
10232 KB |
Output is correct |
4 |
Correct |
16 ms |
9976 KB |
Output is correct |
5 |
Correct |
30 ms |
10104 KB |
Output is correct |
6 |
Correct |
26 ms |
10104 KB |
Output is correct |
7 |
Correct |
29 ms |
10104 KB |
Output is correct |
8 |
Correct |
32 ms |
10104 KB |
Output is correct |
9 |
Correct |
32 ms |
10104 KB |
Output is correct |
10 |
Correct |
33 ms |
10104 KB |
Output is correct |
11 |
Correct |
33 ms |
10232 KB |
Output is correct |
12 |
Correct |
34 ms |
10104 KB |
Output is correct |
13 |
Correct |
41 ms |
10108 KB |
Output is correct |
14 |
Correct |
37 ms |
10104 KB |
Output is correct |
15 |
Correct |
34 ms |
10104 KB |
Output is correct |
16 |
Correct |
30 ms |
10104 KB |
Output is correct |
17 |
Correct |
30 ms |
10104 KB |
Output is correct |
18 |
Correct |
1760 ms |
17652 KB |
Output is correct |
19 |
Correct |
1725 ms |
17632 KB |
Output is correct |
20 |
Correct |
1729 ms |
17516 KB |
Output is correct |
21 |
Correct |
1820 ms |
17520 KB |
Output is correct |
22 |
Correct |
1761 ms |
17664 KB |
Output is correct |
23 |
Correct |
2437 ms |
16776 KB |
Output is correct |
24 |
Correct |
2521 ms |
16928 KB |
Output is correct |
25 |
Correct |
2443 ms |
16848 KB |
Output is correct |
26 |
Correct |
45 ms |
11512 KB |
Output is correct |
27 |
Correct |
1150 ms |
13920 KB |
Output is correct |
28 |
Correct |
1057 ms |
14044 KB |
Output is correct |
29 |
Correct |
1188 ms |
15704 KB |
Output is correct |
30 |
Correct |
1667 ms |
17580 KB |
Output is correct |
31 |
Correct |
1340 ms |
16704 KB |
Output is correct |
32 |
Correct |
1020 ms |
14896 KB |
Output is correct |
33 |
Correct |
1532 ms |
16288 KB |
Output is correct |
34 |
Correct |
1269 ms |
16676 KB |
Output is correct |
35 |
Correct |
46 ms |
11512 KB |
Output is correct |
36 |
Correct |
1475 ms |
16548 KB |
Output is correct |
37 |
Correct |
1180 ms |
16672 KB |
Output is correct |
38 |
Correct |
1054 ms |
16400 KB |
Output is correct |
39 |
Correct |
697 ms |
15556 KB |
Output is correct |
40 |
Correct |
626 ms |
15276 KB |
Output is correct |
41 |
Correct |
1053 ms |
16900 KB |
Output is correct |
42 |
Correct |
945 ms |
16904 KB |
Output is correct |
43 |
Correct |
1641 ms |
18456 KB |
Output is correct |
44 |
Correct |
46 ms |
12920 KB |
Output is correct |
45 |
Correct |
206 ms |
16476 KB |
Output is correct |
46 |
Correct |
69 ms |
13916 KB |
Output is correct |
47 |
Correct |
414 ms |
15968 KB |
Output is correct |
48 |
Correct |
1653 ms |
20080 KB |
Output is correct |
49 |
Correct |
413 ms |
15968 KB |
Output is correct |
50 |
Correct |
659 ms |
16916 KB |
Output is correct |
51 |
Correct |
633 ms |
16836 KB |
Output is correct |
52 |
Correct |
633 ms |
16056 KB |
Output is correct |
53 |
Correct |
1162 ms |
18624 KB |
Output is correct |
54 |
Correct |
1141 ms |
18496 KB |
Output is correct |
55 |
Correct |
1118 ms |
17464 KB |
Output is correct |
56 |
Correct |
402 ms |
16356 KB |
Output is correct |
57 |
Correct |
409 ms |
16092 KB |
Output is correct |
58 |
Correct |
1793 ms |
20036 KB |
Output is correct |
59 |
Correct |
1732 ms |
20192 KB |
Output is correct |
60 |
Correct |
1750 ms |
20192 KB |
Output is correct |
61 |
Correct |
1710 ms |
19936 KB |
Output is correct |
62 |
Correct |
1265 ms |
17984 KB |
Output is correct |
63 |
Correct |
1262 ms |
17952 KB |
Output is correct |
64 |
Correct |
1610 ms |
19204 KB |
Output is correct |
65 |
Correct |
475 ms |
15532 KB |
Output is correct |
66 |
Correct |
1725 ms |
17652 KB |
Output is correct |
67 |
Correct |
2009 ms |
17248 KB |
Output is correct |
68 |
Correct |
1756 ms |
17760 KB |
Output is correct |
69 |
Correct |
1302 ms |
17176 KB |
Output is correct |
70 |
Correct |
2099 ms |
17348 KB |
Output is correct |
71 |
Correct |
2098 ms |
17572 KB |
Output is correct |
72 |
Correct |
2058 ms |
17608 KB |
Output is correct |
73 |
Correct |
1750 ms |
17508 KB |
Output is correct |
74 |
Correct |
1778 ms |
17536 KB |
Output is correct |
75 |
Correct |
1773 ms |
17692 KB |
Output is correct |
76 |
Correct |
1560 ms |
17244 KB |
Output is correct |
77 |
Correct |
1403 ms |
17164 KB |
Output is correct |
78 |
Correct |
1358 ms |
17228 KB |
Output is correct |
79 |
Correct |
866 ms |
16272 KB |
Output is correct |
80 |
Correct |
883 ms |
16352 KB |
Output is correct |
81 |
Correct |
1053 ms |
16104 KB |
Output is correct |
82 |
Correct |
1513 ms |
17932 KB |
Output is correct |
83 |
Correct |
1377 ms |
17852 KB |
Output is correct |
84 |
Correct |
1628 ms |
17804 KB |
Output is correct |
85 |
Correct |
2994 ms |
24268 KB |
Output is correct |
86 |
Correct |
241 ms |
17076 KB |
Output is correct |
87 |
Correct |
87 ms |
14540 KB |
Output is correct |
88 |
Correct |
711 ms |
17604 KB |
Output is correct |
89 |
Correct |
2834 ms |
24072 KB |
Output is correct |
90 |
Correct |
736 ms |
17300 KB |
Output is correct |
91 |
Correct |
2051 ms |
20476 KB |
Output is correct |
92 |
Correct |
1918 ms |
20620 KB |
Output is correct |
93 |
Correct |
2606 ms |
19548 KB |
Output is correct |
94 |
Correct |
2149 ms |
22008 KB |
Output is correct |
95 |
Correct |
2176 ms |
22148 KB |
Output is correct |
96 |
Correct |
2031 ms |
21240 KB |
Output is correct |
97 |
Correct |
519 ms |
17464 KB |
Output is correct |
98 |
Correct |
556 ms |
17324 KB |
Output is correct |
99 |
Correct |
2644 ms |
23832 KB |
Output is correct |
100 |
Correct |
2491 ms |
23928 KB |
Output is correct |
101 |
Correct |
2718 ms |
23956 KB |
Output is correct |
102 |
Correct |
2657 ms |
24132 KB |
Output is correct |
103 |
Correct |
2209 ms |
21644 KB |
Output is correct |
104 |
Correct |
2143 ms |
21716 KB |
Output is correct |
105 |
Correct |
2266 ms |
22716 KB |
Output is correct |
106 |
Correct |
1937 ms |
22472 KB |
Output is correct |
107 |
Correct |
1474 ms |
20468 KB |
Output is correct |
108 |
Correct |
2444 ms |
23272 KB |
Output is correct |
109 |
Correct |
752 ms |
16636 KB |
Output is correct |