//Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
const int BLOCK = 400;
struct Edge
{
int u, v, w;
};
struct Query
{
int type, u, v, id;
};
struct DisjointSetWithRollback
{
struct DisjointSetSave
{
int u, rankU, sizeConnectedU, v, rankV, sizeConnectedV;
DisjointSetSave(int _u = 0, int _rankU = 0, int _sizeConnectedU = 0, int _v = 0, int _rankV = 0, int _sizeConnectedV = 0) : u(_u), rankU(_rankU), sizeConnectedU(_sizeConnectedU), v(_v), rankV(_rankV), sizeConnectedV(_sizeConnectedV) {}
};
int numNode;
int parent[MAX_N], rank[MAX_N], sizeConnected[MAX_N];
stack<DisjointSetSave> s;
void init(int numNode)
{
this->numNode = numNode;
for (int node = 1; node <= numNode; node++)
{
parent[node] = node;
rank[node] = 0;
sizeConnected[node] = 1;
}
while (s.size())
{
s.pop();
}
}
int findRoot(int node) { return (node == parent[node] ? node : findRoot(parent[node])); }
bool join(int u, int v)
{
u = findRoot(u);
v = findRoot(v);
if (u == v)
{
return false;
}
if (rank[u] < rank[v])
{
swap(u, v);
}
s.push(DisjointSetSave(u, rank[u], sizeConnected[u], v, rank[v], sizeConnected[v]));
parent[v] = u;
sizeConnected[u] += sizeConnected[v];
if (rank[u] == rank[v])
{
rank[u]++;
}
return true;
}
void rollback()
{
if (s.empty())
{
return;
}
DisjointSetSave dsuSave = s.top();
s.pop();
parent[dsuSave.u] = dsuSave.u;
rank[dsuSave.u] = dsuSave.rankU;
sizeConnected[dsuSave.u] = dsuSave.sizeConnectedU;
parent[dsuSave.v] = dsuSave.v;
rank[dsuSave.v] = dsuSave.rankV;
sizeConnected[dsuSave.v] = dsuSave.sizeConnectedV;
}
int getSizeConnected(int node)
{
return sizeConnected[findRoot(node)];
}
} dsuRollback;
int numTest, numNode, numEdge, numQuery;
Edge edges[MAX_N];
int edgesId[MAX_N];
Query query[MAX_N], tmpQuery[BLOCK];
vector<pair<int, int>> change[MAX_N];
bool haveChange[MAX_N];
vector<int> edgesChange;
int answer[MAX_N];
void solve(int left, int right)
{
edgesChange.clear();
int cntQuery = 0;
for (int i = left; i <= right; i++)
{
if (query[i].type == 2)
{
tmpQuery[++cntQuery] = query[i];
}
else
{
if (!haveChange[query[i].u])
{
haveChange[query[i].u] = true;
edgesChange.push_back(query[i].u);
change[query[i].u].push_back(make_pair(left - 1, edges[query[i].u].w));
}
change[query[i].u].push_back(make_pair(i, query[i].v));
}
}
int cntEdge = 0;
for (int i = 1; i <= numEdge; i++)
{
if (!haveChange[edgesId[i]])
{
edgesId[++cntEdge] = edgesId[i];
}
}
sort(tmpQuery + 1, tmpQuery + cntQuery + 1, [&](const Query &a, const Query &b)
{ return a.v > b.v; });
dsuRollback.init(numNode);
int j = 1;
for (int i = 1; i <= cntQuery; i++)
{
while (j <= cntEdge && edges[edgesId[j]].w >= tmpQuery[i].v)
{
dsuRollback.join(edges[edgesId[j]].u, edges[edgesId[j]].v);
j++;
}
int cnt = 0;
for (auto &id : edgesChange)
{
auto it = lower_bound(change[id].begin(), change[id].end(), make_pair(tmpQuery[i].id, 0));
it--;
if (it->second >= tmpQuery[i].v)
{
cnt += dsuRollback.join(edges[id].u, edges[id].v);
}
}
answer[tmpQuery[i].id] = dsuRollback.getSizeConnected(tmpQuery[i].u);
while (cnt--)
{
dsuRollback.rollback();
}
}
for (auto &x : edgesChange)
{
edges[x].w = change[x].back().second;
haveChange[x] = false;
change[x].clear();
}
sort(edgesChange.begin(), edgesChange.end(), [&](const int &x, const int &y)
{ return edges[x].w > edges[y].w; });
int pos = numEdge;
while (edgesChange.size())
{
if (cntEdge == 0)
{
edgesId[pos--] = edgesChange.back();
edgesChange.pop_back();
continue;
}
if (edges[edgesChange.back()].w <= edges[edgesId[cntEdge]].w)
{
edgesId[pos--] = edgesChange.back();
edgesChange.pop_back();
}
else
{
edgesId[pos--] = edgesId[cntEdge];
cntEdge--;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef Flower_On_Stone
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
{
cin >> numNode >> numEdge;
for (int i = 1; i <= numEdge; i++)
{
cin >> edges[i].u >> edges[i].v >> edges[i].w;
edgesId[i] = i;
}
sort(edgesId + 1, edgesId + numEdge + 1, [&](const int &x, const int &y)
{ return edges[x].w > edges[y].w; });
cin >> numQuery;
for (int i = 1; i <= numQuery; i++)
{
cin >> query[i].type >> query[i].u >> query[i].v;
query[i].id = i;
}
for (int i = 1; i <= numQuery; i += BLOCK)
{
solve(i, min(numQuery, i + BLOCK - 1));
}
for (int i = 1; i <= numQuery; i++)
{
if (query[i].type == 2)
{
cout << answer[i] << '\n';
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
20 ms |
2948 KB |
Output is correct |
4 |
Correct |
6 ms |
2808 KB |
Output is correct |
5 |
Correct |
18 ms |
2908 KB |
Output is correct |
6 |
Correct |
13 ms |
2892 KB |
Output is correct |
7 |
Correct |
18 ms |
2948 KB |
Output is correct |
8 |
Correct |
18 ms |
2844 KB |
Output is correct |
9 |
Correct |
19 ms |
2912 KB |
Output is correct |
10 |
Correct |
20 ms |
2892 KB |
Output is correct |
11 |
Correct |
18 ms |
2880 KB |
Output is correct |
12 |
Correct |
20 ms |
2888 KB |
Output is correct |
13 |
Correct |
22 ms |
2912 KB |
Output is correct |
14 |
Correct |
21 ms |
2900 KB |
Output is correct |
15 |
Correct |
19 ms |
2896 KB |
Output is correct |
16 |
Correct |
21 ms |
2892 KB |
Output is correct |
17 |
Correct |
19 ms |
2916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1314 ms |
8492 KB |
Output is correct |
2 |
Correct |
1267 ms |
8480 KB |
Output is correct |
3 |
Correct |
1309 ms |
8460 KB |
Output is correct |
4 |
Correct |
1306 ms |
8340 KB |
Output is correct |
5 |
Correct |
1324 ms |
8476 KB |
Output is correct |
6 |
Correct |
1640 ms |
8480 KB |
Output is correct |
7 |
Correct |
1576 ms |
8548 KB |
Output is correct |
8 |
Correct |
1654 ms |
8604 KB |
Output is correct |
9 |
Correct |
44 ms |
4804 KB |
Output is correct |
10 |
Correct |
1221 ms |
8556 KB |
Output is correct |
11 |
Correct |
1162 ms |
8460 KB |
Output is correct |
12 |
Correct |
1095 ms |
8184 KB |
Output is correct |
13 |
Correct |
1164 ms |
8560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
937 ms |
7288 KB |
Output is correct |
2 |
Correct |
559 ms |
5528 KB |
Output is correct |
3 |
Correct |
1028 ms |
7368 KB |
Output is correct |
4 |
Correct |
918 ms |
7280 KB |
Output is correct |
5 |
Correct |
48 ms |
4764 KB |
Output is correct |
6 |
Correct |
976 ms |
7372 KB |
Output is correct |
7 |
Correct |
869 ms |
7296 KB |
Output is correct |
8 |
Correct |
838 ms |
7556 KB |
Output is correct |
9 |
Correct |
685 ms |
6892 KB |
Output is correct |
10 |
Correct |
651 ms |
6876 KB |
Output is correct |
11 |
Correct |
731 ms |
7356 KB |
Output is correct |
12 |
Correct |
659 ms |
7492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1572 ms |
8488 KB |
Output is correct |
2 |
Correct |
47 ms |
4740 KB |
Output is correct |
3 |
Correct |
130 ms |
4452 KB |
Output is correct |
4 |
Correct |
123 ms |
4556 KB |
Output is correct |
5 |
Correct |
1462 ms |
8560 KB |
Output is correct |
6 |
Correct |
1506 ms |
8412 KB |
Output is correct |
7 |
Correct |
1358 ms |
8492 KB |
Output is correct |
8 |
Correct |
927 ms |
7560 KB |
Output is correct |
9 |
Correct |
948 ms |
7352 KB |
Output is correct |
10 |
Correct |
988 ms |
7632 KB |
Output is correct |
11 |
Correct |
1318 ms |
7844 KB |
Output is correct |
12 |
Correct |
1254 ms |
8116 KB |
Output is correct |
13 |
Correct |
1281 ms |
8168 KB |
Output is correct |
14 |
Correct |
1359 ms |
8604 KB |
Output is correct |
15 |
Correct |
1334 ms |
8476 KB |
Output is correct |
16 |
Correct |
1653 ms |
8468 KB |
Output is correct |
17 |
Correct |
1617 ms |
8420 KB |
Output is correct |
18 |
Correct |
1676 ms |
8436 KB |
Output is correct |
19 |
Correct |
1628 ms |
8300 KB |
Output is correct |
20 |
Correct |
1469 ms |
8288 KB |
Output is correct |
21 |
Correct |
1449 ms |
8372 KB |
Output is correct |
22 |
Correct |
1634 ms |
8464 KB |
Output is correct |
23 |
Correct |
1325 ms |
8152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1314 ms |
8492 KB |
Output is correct |
2 |
Correct |
1267 ms |
8480 KB |
Output is correct |
3 |
Correct |
1309 ms |
8460 KB |
Output is correct |
4 |
Correct |
1306 ms |
8340 KB |
Output is correct |
5 |
Correct |
1324 ms |
8476 KB |
Output is correct |
6 |
Correct |
1640 ms |
8480 KB |
Output is correct |
7 |
Correct |
1576 ms |
8548 KB |
Output is correct |
8 |
Correct |
1654 ms |
8604 KB |
Output is correct |
9 |
Correct |
44 ms |
4804 KB |
Output is correct |
10 |
Correct |
1221 ms |
8556 KB |
Output is correct |
11 |
Correct |
1162 ms |
8460 KB |
Output is correct |
12 |
Correct |
1095 ms |
8184 KB |
Output is correct |
13 |
Correct |
1164 ms |
8560 KB |
Output is correct |
14 |
Correct |
937 ms |
7288 KB |
Output is correct |
15 |
Correct |
559 ms |
5528 KB |
Output is correct |
16 |
Correct |
1028 ms |
7368 KB |
Output is correct |
17 |
Correct |
918 ms |
7280 KB |
Output is correct |
18 |
Correct |
48 ms |
4764 KB |
Output is correct |
19 |
Correct |
976 ms |
7372 KB |
Output is correct |
20 |
Correct |
869 ms |
7296 KB |
Output is correct |
21 |
Correct |
838 ms |
7556 KB |
Output is correct |
22 |
Correct |
685 ms |
6892 KB |
Output is correct |
23 |
Correct |
651 ms |
6876 KB |
Output is correct |
24 |
Correct |
731 ms |
7356 KB |
Output is correct |
25 |
Correct |
659 ms |
7492 KB |
Output is correct |
26 |
Correct |
1287 ms |
8316 KB |
Output is correct |
27 |
Correct |
1583 ms |
8388 KB |
Output is correct |
28 |
Correct |
1453 ms |
8440 KB |
Output is correct |
29 |
Correct |
1191 ms |
8388 KB |
Output is correct |
30 |
Correct |
1528 ms |
8592 KB |
Output is correct |
31 |
Correct |
1574 ms |
8508 KB |
Output is correct |
32 |
Correct |
1555 ms |
8412 KB |
Output is correct |
33 |
Correct |
1412 ms |
8376 KB |
Output is correct |
34 |
Correct |
1454 ms |
8376 KB |
Output is correct |
35 |
Correct |
1473 ms |
8512 KB |
Output is correct |
36 |
Correct |
1199 ms |
8444 KB |
Output is correct |
37 |
Correct |
1207 ms |
8444 KB |
Output is correct |
38 |
Correct |
1212 ms |
8356 KB |
Output is correct |
39 |
Correct |
1044 ms |
7828 KB |
Output is correct |
40 |
Correct |
1037 ms |
7944 KB |
Output is correct |
41 |
Correct |
1041 ms |
7816 KB |
Output is correct |
42 |
Correct |
989 ms |
8576 KB |
Output is correct |
43 |
Correct |
1027 ms |
8572 KB |
Output is correct |
44 |
Correct |
1039 ms |
8676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
20 ms |
2948 KB |
Output is correct |
4 |
Correct |
6 ms |
2808 KB |
Output is correct |
5 |
Correct |
18 ms |
2908 KB |
Output is correct |
6 |
Correct |
13 ms |
2892 KB |
Output is correct |
7 |
Correct |
18 ms |
2948 KB |
Output is correct |
8 |
Correct |
18 ms |
2844 KB |
Output is correct |
9 |
Correct |
19 ms |
2912 KB |
Output is correct |
10 |
Correct |
20 ms |
2892 KB |
Output is correct |
11 |
Correct |
18 ms |
2880 KB |
Output is correct |
12 |
Correct |
20 ms |
2888 KB |
Output is correct |
13 |
Correct |
22 ms |
2912 KB |
Output is correct |
14 |
Correct |
21 ms |
2900 KB |
Output is correct |
15 |
Correct |
19 ms |
2896 KB |
Output is correct |
16 |
Correct |
21 ms |
2892 KB |
Output is correct |
17 |
Correct |
19 ms |
2916 KB |
Output is correct |
18 |
Correct |
1314 ms |
8492 KB |
Output is correct |
19 |
Correct |
1267 ms |
8480 KB |
Output is correct |
20 |
Correct |
1309 ms |
8460 KB |
Output is correct |
21 |
Correct |
1306 ms |
8340 KB |
Output is correct |
22 |
Correct |
1324 ms |
8476 KB |
Output is correct |
23 |
Correct |
1640 ms |
8480 KB |
Output is correct |
24 |
Correct |
1576 ms |
8548 KB |
Output is correct |
25 |
Correct |
1654 ms |
8604 KB |
Output is correct |
26 |
Correct |
44 ms |
4804 KB |
Output is correct |
27 |
Correct |
1221 ms |
8556 KB |
Output is correct |
28 |
Correct |
1162 ms |
8460 KB |
Output is correct |
29 |
Correct |
1095 ms |
8184 KB |
Output is correct |
30 |
Correct |
1164 ms |
8560 KB |
Output is correct |
31 |
Correct |
937 ms |
7288 KB |
Output is correct |
32 |
Correct |
559 ms |
5528 KB |
Output is correct |
33 |
Correct |
1028 ms |
7368 KB |
Output is correct |
34 |
Correct |
918 ms |
7280 KB |
Output is correct |
35 |
Correct |
48 ms |
4764 KB |
Output is correct |
36 |
Correct |
976 ms |
7372 KB |
Output is correct |
37 |
Correct |
869 ms |
7296 KB |
Output is correct |
38 |
Correct |
838 ms |
7556 KB |
Output is correct |
39 |
Correct |
685 ms |
6892 KB |
Output is correct |
40 |
Correct |
651 ms |
6876 KB |
Output is correct |
41 |
Correct |
731 ms |
7356 KB |
Output is correct |
42 |
Correct |
659 ms |
7492 KB |
Output is correct |
43 |
Correct |
1572 ms |
8488 KB |
Output is correct |
44 |
Correct |
47 ms |
4740 KB |
Output is correct |
45 |
Correct |
130 ms |
4452 KB |
Output is correct |
46 |
Correct |
123 ms |
4556 KB |
Output is correct |
47 |
Correct |
1462 ms |
8560 KB |
Output is correct |
48 |
Correct |
1506 ms |
8412 KB |
Output is correct |
49 |
Correct |
1358 ms |
8492 KB |
Output is correct |
50 |
Correct |
927 ms |
7560 KB |
Output is correct |
51 |
Correct |
948 ms |
7352 KB |
Output is correct |
52 |
Correct |
988 ms |
7632 KB |
Output is correct |
53 |
Correct |
1318 ms |
7844 KB |
Output is correct |
54 |
Correct |
1254 ms |
8116 KB |
Output is correct |
55 |
Correct |
1281 ms |
8168 KB |
Output is correct |
56 |
Correct |
1359 ms |
8604 KB |
Output is correct |
57 |
Correct |
1334 ms |
8476 KB |
Output is correct |
58 |
Correct |
1653 ms |
8468 KB |
Output is correct |
59 |
Correct |
1617 ms |
8420 KB |
Output is correct |
60 |
Correct |
1676 ms |
8436 KB |
Output is correct |
61 |
Correct |
1628 ms |
8300 KB |
Output is correct |
62 |
Correct |
1469 ms |
8288 KB |
Output is correct |
63 |
Correct |
1449 ms |
8372 KB |
Output is correct |
64 |
Correct |
1634 ms |
8464 KB |
Output is correct |
65 |
Correct |
1325 ms |
8152 KB |
Output is correct |
66 |
Correct |
1287 ms |
8316 KB |
Output is correct |
67 |
Correct |
1583 ms |
8388 KB |
Output is correct |
68 |
Correct |
1453 ms |
8440 KB |
Output is correct |
69 |
Correct |
1191 ms |
8388 KB |
Output is correct |
70 |
Correct |
1528 ms |
8592 KB |
Output is correct |
71 |
Correct |
1574 ms |
8508 KB |
Output is correct |
72 |
Correct |
1555 ms |
8412 KB |
Output is correct |
73 |
Correct |
1412 ms |
8376 KB |
Output is correct |
74 |
Correct |
1454 ms |
8376 KB |
Output is correct |
75 |
Correct |
1473 ms |
8512 KB |
Output is correct |
76 |
Correct |
1199 ms |
8444 KB |
Output is correct |
77 |
Correct |
1207 ms |
8444 KB |
Output is correct |
78 |
Correct |
1212 ms |
8356 KB |
Output is correct |
79 |
Correct |
1044 ms |
7828 KB |
Output is correct |
80 |
Correct |
1037 ms |
7944 KB |
Output is correct |
81 |
Correct |
1041 ms |
7816 KB |
Output is correct |
82 |
Correct |
989 ms |
8576 KB |
Output is correct |
83 |
Correct |
1027 ms |
8572 KB |
Output is correct |
84 |
Correct |
1039 ms |
8676 KB |
Output is correct |
85 |
Correct |
1942 ms |
9436 KB |
Output is correct |
86 |
Correct |
155 ms |
4800 KB |
Output is correct |
87 |
Correct |
132 ms |
4724 KB |
Output is correct |
88 |
Correct |
1684 ms |
9628 KB |
Output is correct |
89 |
Correct |
1925 ms |
9508 KB |
Output is correct |
90 |
Correct |
1708 ms |
9456 KB |
Output is correct |
91 |
Correct |
1562 ms |
8348 KB |
Output is correct |
92 |
Correct |
1560 ms |
8528 KB |
Output is correct |
93 |
Correct |
1756 ms |
8516 KB |
Output is correct |
94 |
Correct |
1695 ms |
8896 KB |
Output is correct |
95 |
Correct |
1689 ms |
9100 KB |
Output is correct |
96 |
Correct |
1752 ms |
8992 KB |
Output is correct |
97 |
Correct |
1501 ms |
8832 KB |
Output is correct |
98 |
Correct |
1602 ms |
9420 KB |
Output is correct |
99 |
Correct |
1973 ms |
9432 KB |
Output is correct |
100 |
Correct |
1992 ms |
9828 KB |
Output is correct |
101 |
Correct |
2062 ms |
9632 KB |
Output is correct |
102 |
Correct |
2029 ms |
9560 KB |
Output is correct |
103 |
Correct |
1888 ms |
9076 KB |
Output is correct |
104 |
Correct |
1896 ms |
9256 KB |
Output is correct |
105 |
Correct |
1671 ms |
9360 KB |
Output is correct |
106 |
Correct |
1436 ms |
9172 KB |
Output is correct |
107 |
Correct |
1585 ms |
8720 KB |
Output is correct |
108 |
Correct |
1937 ms |
9312 KB |
Output is correct |
109 |
Correct |
1649 ms |
8884 KB |
Output is correct |