/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10, block = 1010;
struct edge
{
int v, u, d;
edge(int _v = 0, int _u = 0, int _d = 0)
{
v = _v;
u = _u;
d = _d;
}
}e[maxn];
struct query
{
int t, x, y;
query(int _t = 0, int _x = 0, int _y = 0)
{
t = _t;
x = _x;
y = _y;
}
}ask[maxn];
bool cmp_car(int id1, int id2)
{
return ask[id1].y > ask[id2].y;
}
bool cmp_edge(int id1, int id2)
{
return e[id1].d > e[id2].d;
}
int n, m, q, ans[maxn];
bool changed[maxn];
vector < edge > to_join[block + 10];
struct DisjointSetUnion
{
vector < int > par, sz;
stack < pair < int, int > > st;
DisjointSetUnion()
{
par.resize(n + 1);
sz.resize(n + 1);
for (int i = 1; i <= n; i ++)
{
par[i] = i;
sz[i] = 1;
}
};
void reset()
{
while(!st.empty())
st.pop();
for (int i = 1; i <= n; i ++)
{
par[i] = i;
sz[i] = 1;
}
}
int find_leader(int v)
{
while(par[v] != v)
v = par[v];
return v;
}
void unite(int v, int u)
{
///cout << v << " --------- " << u << endl;
v = find_leader(v);
u = find_leader(u);
if (v == u)
return;
if (sz[v] < sz[u])
swap(v, u);
sz[v] += sz[u];
par[u] = v;
st.push({v, u});
}
void rollback()
{
pair < int, int > cur = st.top();
st.pop();
sz[cur.first] -= sz[cur.second];
par[cur.second] = cur.second;
}
};
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
cin >> e[i].v >> e[i].u >> e[i].d;
cin >> q;
for (int i = 1; i <= q; i ++)
cin >> ask[i].t >> ask[i].x >> ask[i].y;
DisjointSetUnion dsu;
for (int l = 1; l <= q; l += block)
{
int r = min(q, l + block - 1);
for (int i = 1; i <= m; i ++)
changed[i] = false;
for (int i = 0; i < block; i ++)
to_join[i].clear();
vector < int > upd, ask_car, unchanged;
for (int i = l; i <= r; i ++)
{
if (ask[i].t == 1)
{
changed[ask[i].x] = 1;
upd.push_back(i);
}
else
{
ask_car.push_back(i);
}
}
for (int i = 1; i <= m; i ++)
if (changed[i] == 0)
unchanged.push_back(i);
for (int i = l; i <= r; i ++)
{
if (ask[i].t == 1)
{
e[ask[i].x].d = ask[i].y;
}
else
{
for (int id : upd)
{
if (e[ask[id].x].d >= ask[i].y)
{
to_join[i - l].push_back(e[ask[id].x]);
}
}
}
}
dsu.reset();
sort(ask_car.begin(), ask_car.end(), cmp_car);
sort(unchanged.begin(), unchanged.end(), cmp_edge);
int ptr = 0;
for (int i = 0; i < ask_car.size(); i ++)
{
///cout << i << " : " << e[unchanged[ptr]].d << " " << ask[ask_car[i]].y << endl;
while(ptr < unchanged.size() && e[unchanged[ptr]].d >= ask[ask_car[i]].y)
dsu.unite(e[unchanged[ptr]].v, e[unchanged[ptr]].u), ptr ++;
int cur_sz = dsu.st.size();
/**for (int i = 1; i <= n; i ++)
cout << dsu.par[i] << " ";
cout << endl;*/
for (edge cur : to_join[ask_car[i] - l])
{
/// cout << i << " yes" << endl;
dsu.unite(cur.v, cur.u);
}
ans[ask_car[i]] = dsu.sz[dsu.find_leader(ask[ask_car[i]].x)];
///cout << i << " ::: " << ans[ask_car[i]] << endl;
while(dsu.st.size() > cur_sz)
dsu.rollback();
/**for (int i = 1; i <= n; i ++)
cout << dsu.par[i] << " ";
cout << endl;
cout << "-----------" << endl;*/
}
}
for (int i = 1; i <= q; i ++)
if (ask[i].t == 2)
cout << ans[i] << endl;
}
int main()
{
speed();
solve();
return 0;
}
/**
3 4
1 2 5
2 3 2
3 1 4
2 3 8
4
2 1 5
1 4 1
2 2 5
1 1 1
*/
Compilation message
bridges.cpp: In function 'void solve()':
bridges.cpp:137:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
137 | for (int i = 1; i <= m; i ++)
| ^~~
bridges.cpp:140:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
140 | for (int i = 0; i < block; i ++)
| ^~~
bridges.cpp:184:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for (int i = 0; i < ask_car.size(); i ++)
| ~~^~~~~~~~~~~~~~~~
bridges.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | while(ptr < unchanged.size() && e[unchanged[ptr]].d >= ask[ask_car[i]].y)
| ~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:202:33: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
202 | while(dsu.st.size() > cur_sz)
| ~~~~~~~~~~~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2696 KB |
Output is correct |
3 |
Correct |
40 ms |
9304 KB |
Output is correct |
4 |
Correct |
5 ms |
2836 KB |
Output is correct |
5 |
Correct |
36 ms |
10312 KB |
Output is correct |
6 |
Correct |
27 ms |
9036 KB |
Output is correct |
7 |
Correct |
36 ms |
11592 KB |
Output is correct |
8 |
Correct |
47 ms |
9132 KB |
Output is correct |
9 |
Correct |
43 ms |
13392 KB |
Output is correct |
10 |
Correct |
38 ms |
9584 KB |
Output is correct |
11 |
Correct |
38 ms |
9232 KB |
Output is correct |
12 |
Correct |
44 ms |
9376 KB |
Output is correct |
13 |
Correct |
48 ms |
9488 KB |
Output is correct |
14 |
Correct |
42 ms |
9132 KB |
Output is correct |
15 |
Correct |
55 ms |
9172 KB |
Output is correct |
16 |
Correct |
46 ms |
12196 KB |
Output is correct |
17 |
Correct |
41 ms |
11596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1402 ms |
15944 KB |
Output is correct |
2 |
Correct |
1403 ms |
15584 KB |
Output is correct |
3 |
Correct |
1416 ms |
15864 KB |
Output is correct |
4 |
Correct |
1564 ms |
15332 KB |
Output is correct |
5 |
Correct |
1498 ms |
16180 KB |
Output is correct |
6 |
Correct |
1987 ms |
18180 KB |
Output is correct |
7 |
Correct |
2083 ms |
18352 KB |
Output is correct |
8 |
Correct |
2129 ms |
18288 KB |
Output is correct |
9 |
Correct |
38 ms |
4600 KB |
Output is correct |
10 |
Correct |
1113 ms |
17480 KB |
Output is correct |
11 |
Correct |
1061 ms |
18168 KB |
Output is correct |
12 |
Correct |
1321 ms |
9000 KB |
Output is correct |
13 |
Correct |
1296 ms |
19280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1048 ms |
15280 KB |
Output is correct |
2 |
Correct |
739 ms |
16700 KB |
Output is correct |
3 |
Correct |
1177 ms |
18224 KB |
Output is correct |
4 |
Correct |
1028 ms |
15240 KB |
Output is correct |
5 |
Correct |
34 ms |
4556 KB |
Output is correct |
6 |
Correct |
1114 ms |
15324 KB |
Output is correct |
7 |
Correct |
988 ms |
14072 KB |
Output is correct |
8 |
Correct |
843 ms |
13632 KB |
Output is correct |
9 |
Correct |
711 ms |
8000 KB |
Output is correct |
10 |
Correct |
703 ms |
7948 KB |
Output is correct |
11 |
Correct |
793 ms |
18992 KB |
Output is correct |
12 |
Correct |
678 ms |
19044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1848 ms |
8988 KB |
Output is correct |
2 |
Correct |
44 ms |
4556 KB |
Output is correct |
3 |
Correct |
182 ms |
5636 KB |
Output is correct |
4 |
Correct |
93 ms |
5844 KB |
Output is correct |
5 |
Correct |
996 ms |
7224 KB |
Output is correct |
6 |
Correct |
1768 ms |
8920 KB |
Output is correct |
7 |
Correct |
961 ms |
7300 KB |
Output is correct |
8 |
Correct |
930 ms |
7096 KB |
Output is correct |
9 |
Correct |
948 ms |
7168 KB |
Output is correct |
10 |
Correct |
896 ms |
7056 KB |
Output is correct |
11 |
Correct |
1346 ms |
8012 KB |
Output is correct |
12 |
Correct |
1394 ms |
8156 KB |
Output is correct |
13 |
Correct |
1373 ms |
7908 KB |
Output is correct |
14 |
Correct |
913 ms |
7420 KB |
Output is correct |
15 |
Correct |
971 ms |
7292 KB |
Output is correct |
16 |
Correct |
1791 ms |
8984 KB |
Output is correct |
17 |
Correct |
1844 ms |
8760 KB |
Output is correct |
18 |
Correct |
1829 ms |
9020 KB |
Output is correct |
19 |
Correct |
1841 ms |
9164 KB |
Output is correct |
20 |
Correct |
1590 ms |
8240 KB |
Output is correct |
21 |
Correct |
1523 ms |
8200 KB |
Output is correct |
22 |
Correct |
1741 ms |
8684 KB |
Output is correct |
23 |
Correct |
1056 ms |
7044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1402 ms |
15944 KB |
Output is correct |
2 |
Correct |
1403 ms |
15584 KB |
Output is correct |
3 |
Correct |
1416 ms |
15864 KB |
Output is correct |
4 |
Correct |
1564 ms |
15332 KB |
Output is correct |
5 |
Correct |
1498 ms |
16180 KB |
Output is correct |
6 |
Correct |
1987 ms |
18180 KB |
Output is correct |
7 |
Correct |
2083 ms |
18352 KB |
Output is correct |
8 |
Correct |
2129 ms |
18288 KB |
Output is correct |
9 |
Correct |
38 ms |
4600 KB |
Output is correct |
10 |
Correct |
1113 ms |
17480 KB |
Output is correct |
11 |
Correct |
1061 ms |
18168 KB |
Output is correct |
12 |
Correct |
1321 ms |
9000 KB |
Output is correct |
13 |
Correct |
1296 ms |
19280 KB |
Output is correct |
14 |
Correct |
1048 ms |
15280 KB |
Output is correct |
15 |
Correct |
739 ms |
16700 KB |
Output is correct |
16 |
Correct |
1177 ms |
18224 KB |
Output is correct |
17 |
Correct |
1028 ms |
15240 KB |
Output is correct |
18 |
Correct |
34 ms |
4556 KB |
Output is correct |
19 |
Correct |
1114 ms |
15324 KB |
Output is correct |
20 |
Correct |
988 ms |
14072 KB |
Output is correct |
21 |
Correct |
843 ms |
13632 KB |
Output is correct |
22 |
Correct |
711 ms |
8000 KB |
Output is correct |
23 |
Correct |
703 ms |
7948 KB |
Output is correct |
24 |
Correct |
793 ms |
18992 KB |
Output is correct |
25 |
Correct |
678 ms |
19044 KB |
Output is correct |
26 |
Correct |
1385 ms |
16160 KB |
Output is correct |
27 |
Correct |
1651 ms |
19024 KB |
Output is correct |
28 |
Correct |
1488 ms |
15724 KB |
Output is correct |
29 |
Correct |
1151 ms |
14200 KB |
Output is correct |
30 |
Correct |
1665 ms |
19196 KB |
Output is correct |
31 |
Correct |
1660 ms |
19096 KB |
Output is correct |
32 |
Correct |
1677 ms |
18932 KB |
Output is correct |
33 |
Correct |
1469 ms |
15636 KB |
Output is correct |
34 |
Correct |
1446 ms |
15620 KB |
Output is correct |
35 |
Correct |
1483 ms |
15740 KB |
Output is correct |
36 |
Correct |
1204 ms |
14196 KB |
Output is correct |
37 |
Correct |
1183 ms |
14200 KB |
Output is correct |
38 |
Correct |
1162 ms |
14092 KB |
Output is correct |
39 |
Correct |
1061 ms |
8940 KB |
Output is correct |
40 |
Correct |
1033 ms |
9064 KB |
Output is correct |
41 |
Correct |
1034 ms |
9032 KB |
Output is correct |
42 |
Correct |
982 ms |
18124 KB |
Output is correct |
43 |
Correct |
1000 ms |
17752 KB |
Output is correct |
44 |
Correct |
968 ms |
17752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2696 KB |
Output is correct |
3 |
Correct |
40 ms |
9304 KB |
Output is correct |
4 |
Correct |
5 ms |
2836 KB |
Output is correct |
5 |
Correct |
36 ms |
10312 KB |
Output is correct |
6 |
Correct |
27 ms |
9036 KB |
Output is correct |
7 |
Correct |
36 ms |
11592 KB |
Output is correct |
8 |
Correct |
47 ms |
9132 KB |
Output is correct |
9 |
Correct |
43 ms |
13392 KB |
Output is correct |
10 |
Correct |
38 ms |
9584 KB |
Output is correct |
11 |
Correct |
38 ms |
9232 KB |
Output is correct |
12 |
Correct |
44 ms |
9376 KB |
Output is correct |
13 |
Correct |
48 ms |
9488 KB |
Output is correct |
14 |
Correct |
42 ms |
9132 KB |
Output is correct |
15 |
Correct |
55 ms |
9172 KB |
Output is correct |
16 |
Correct |
46 ms |
12196 KB |
Output is correct |
17 |
Correct |
41 ms |
11596 KB |
Output is correct |
18 |
Correct |
1402 ms |
15944 KB |
Output is correct |
19 |
Correct |
1403 ms |
15584 KB |
Output is correct |
20 |
Correct |
1416 ms |
15864 KB |
Output is correct |
21 |
Correct |
1564 ms |
15332 KB |
Output is correct |
22 |
Correct |
1498 ms |
16180 KB |
Output is correct |
23 |
Correct |
1987 ms |
18180 KB |
Output is correct |
24 |
Correct |
2083 ms |
18352 KB |
Output is correct |
25 |
Correct |
2129 ms |
18288 KB |
Output is correct |
26 |
Correct |
38 ms |
4600 KB |
Output is correct |
27 |
Correct |
1113 ms |
17480 KB |
Output is correct |
28 |
Correct |
1061 ms |
18168 KB |
Output is correct |
29 |
Correct |
1321 ms |
9000 KB |
Output is correct |
30 |
Correct |
1296 ms |
19280 KB |
Output is correct |
31 |
Correct |
1048 ms |
15280 KB |
Output is correct |
32 |
Correct |
739 ms |
16700 KB |
Output is correct |
33 |
Correct |
1177 ms |
18224 KB |
Output is correct |
34 |
Correct |
1028 ms |
15240 KB |
Output is correct |
35 |
Correct |
34 ms |
4556 KB |
Output is correct |
36 |
Correct |
1114 ms |
15324 KB |
Output is correct |
37 |
Correct |
988 ms |
14072 KB |
Output is correct |
38 |
Correct |
843 ms |
13632 KB |
Output is correct |
39 |
Correct |
711 ms |
8000 KB |
Output is correct |
40 |
Correct |
703 ms |
7948 KB |
Output is correct |
41 |
Correct |
793 ms |
18992 KB |
Output is correct |
42 |
Correct |
678 ms |
19044 KB |
Output is correct |
43 |
Correct |
1848 ms |
8988 KB |
Output is correct |
44 |
Correct |
44 ms |
4556 KB |
Output is correct |
45 |
Correct |
182 ms |
5636 KB |
Output is correct |
46 |
Correct |
93 ms |
5844 KB |
Output is correct |
47 |
Correct |
996 ms |
7224 KB |
Output is correct |
48 |
Correct |
1768 ms |
8920 KB |
Output is correct |
49 |
Correct |
961 ms |
7300 KB |
Output is correct |
50 |
Correct |
930 ms |
7096 KB |
Output is correct |
51 |
Correct |
948 ms |
7168 KB |
Output is correct |
52 |
Correct |
896 ms |
7056 KB |
Output is correct |
53 |
Correct |
1346 ms |
8012 KB |
Output is correct |
54 |
Correct |
1394 ms |
8156 KB |
Output is correct |
55 |
Correct |
1373 ms |
7908 KB |
Output is correct |
56 |
Correct |
913 ms |
7420 KB |
Output is correct |
57 |
Correct |
971 ms |
7292 KB |
Output is correct |
58 |
Correct |
1791 ms |
8984 KB |
Output is correct |
59 |
Correct |
1844 ms |
8760 KB |
Output is correct |
60 |
Correct |
1829 ms |
9020 KB |
Output is correct |
61 |
Correct |
1841 ms |
9164 KB |
Output is correct |
62 |
Correct |
1590 ms |
8240 KB |
Output is correct |
63 |
Correct |
1523 ms |
8200 KB |
Output is correct |
64 |
Correct |
1741 ms |
8684 KB |
Output is correct |
65 |
Correct |
1056 ms |
7044 KB |
Output is correct |
66 |
Correct |
1385 ms |
16160 KB |
Output is correct |
67 |
Correct |
1651 ms |
19024 KB |
Output is correct |
68 |
Correct |
1488 ms |
15724 KB |
Output is correct |
69 |
Correct |
1151 ms |
14200 KB |
Output is correct |
70 |
Correct |
1665 ms |
19196 KB |
Output is correct |
71 |
Correct |
1660 ms |
19096 KB |
Output is correct |
72 |
Correct |
1677 ms |
18932 KB |
Output is correct |
73 |
Correct |
1469 ms |
15636 KB |
Output is correct |
74 |
Correct |
1446 ms |
15620 KB |
Output is correct |
75 |
Correct |
1483 ms |
15740 KB |
Output is correct |
76 |
Correct |
1204 ms |
14196 KB |
Output is correct |
77 |
Correct |
1183 ms |
14200 KB |
Output is correct |
78 |
Correct |
1162 ms |
14092 KB |
Output is correct |
79 |
Correct |
1061 ms |
8940 KB |
Output is correct |
80 |
Correct |
1033 ms |
9064 KB |
Output is correct |
81 |
Correct |
1034 ms |
9032 KB |
Output is correct |
82 |
Correct |
982 ms |
18124 KB |
Output is correct |
83 |
Correct |
1000 ms |
17752 KB |
Output is correct |
84 |
Correct |
968 ms |
17752 KB |
Output is correct |
85 |
Correct |
2193 ms |
17432 KB |
Output is correct |
86 |
Correct |
211 ms |
11768 KB |
Output is correct |
87 |
Correct |
128 ms |
14968 KB |
Output is correct |
88 |
Correct |
1318 ms |
19436 KB |
Output is correct |
89 |
Correct |
2200 ms |
17728 KB |
Output is correct |
90 |
Correct |
1291 ms |
19632 KB |
Output is correct |
91 |
Correct |
1513 ms |
15664 KB |
Output is correct |
92 |
Correct |
1487 ms |
15500 KB |
Output is correct |
93 |
Correct |
1930 ms |
19416 KB |
Output is correct |
94 |
Correct |
1865 ms |
17060 KB |
Output is correct |
95 |
Correct |
1784 ms |
16868 KB |
Output is correct |
96 |
Correct |
2025 ms |
19804 KB |
Output is correct |
97 |
Correct |
1143 ms |
9824 KB |
Output is correct |
98 |
Correct |
1155 ms |
19984 KB |
Output is correct |
99 |
Correct |
2274 ms |
17656 KB |
Output is correct |
100 |
Correct |
2256 ms |
17420 KB |
Output is correct |
101 |
Correct |
2325 ms |
17440 KB |
Output is correct |
102 |
Correct |
2276 ms |
17348 KB |
Output is correct |
103 |
Correct |
2199 ms |
20320 KB |
Output is correct |
104 |
Correct |
2237 ms |
20028 KB |
Output is correct |
105 |
Correct |
1780 ms |
20448 KB |
Output is correct |
106 |
Correct |
1556 ms |
20060 KB |
Output is correct |
107 |
Correct |
1730 ms |
9684 KB |
Output is correct |
108 |
Correct |
2243 ms |
18924 KB |
Output is correct |
109 |
Correct |
1510 ms |
19792 KB |
Output is correct |