#include<bits/stdc++.h>
#define block 300
#define maxn 100005
using namespace std;
typedef long long ll;
typedef pair < int, int > II;
int n, m;
int nq;
struct edge{
int u, v, c;
edge(int _u = 0, int _v = 0, int _c = 0) : u(_u), v(_v), c(_c) {};
};
vector < edge > e;
struct query{
int type, a, b;
query(int _type, int _a, int _b) : type(_type), a(_a), b(_b) {};
};
vector < query > q[400];
int id[maxn], ok[maxn];
II d[maxn];
int ntem;
pair < II*, II > tem[maxn * 100];
int root(int u) {
if (u == d[u].first)
return u;
tem[ntem++] = {d + u, d[u]};
return d[u].first = root(d[u].first);
}
void join(int u, int v) {
u = root(u); v = root(v);
if (u != v) {
tem[ntem++] = {d + u, d[u]};
tem[ntem++] = {d + v, d[v]};
d[u].first = v;
d[v].second += d[u].second;
d[u].second = 0;
}
}
void undo() {
for (int i = ntem - 1; i >= 0; --i)
(*tem[i].first) = tem[i].second;
ntem = 0;
}
int k;
int main(){
#define TASK "ABC"
// freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
e.push_back({edge(u, v, c)});
id[i] = i;
}
cin >> nq;
for (int i = 0; i < nq; ++i) {
int type, a, b;
cin >> type >> a >> b;
if (type == 1)
a--;
q[i / block].push_back(query(type, a, b));
}
for (k = 0; k <= (nq - 1) / block; ++k) {
for (int i = 1; i <= n; ++i)
d[i] = {i, 1};
ntem = 0;
sort(id, id + m, [](int i, int j){
return e[i].c > e[j].c;
});
vector < int > ret;
for (int i = 0; i < q[k].size(); ++i)
if (q[k][i].type == 2)
ret.push_back(i);
sort(ret.begin(), ret.end(), [](int i, int j){
return q[k][i].b > q[k][j].b;
});
vector < int > ans(q[k].size());
int index = 0;
for (auto x : ret) {
for (int i = 0; i < q[k].size(); ++i)
if (q[k][i].type == 1)
ok[q[k][i].a] = 1;
while (index < e.size() && e[id[index]].c >= q[k][x].b) {
if (!ok[id[index]])
join(e[id[index]].u, e[id[index]].v);
index++;
}
ntem = 0;
for (int i = 0; i < q[k].size(); ++i)
if (q[k][i].type == 1)
ok[q[k][i].a] = 0;
for (int i = 0; i < x; ++i)
if (q[k][i].type == 1)
ok[q[k][i].a] = 1;
for (int i = q[k].size() - 1; i >= 0; --i)
if (q[k][i].type == 1 && ((i < x && q[k][i].b >= q[k][x].b && ok[q[k][i].a]) || (i >= x && e[q[k][i].a].c >= q[k][x].b && !ok[q[k][i].a]))) {
ok[q[k][i].a] = 0;
join(e[q[k][i].a].u, e[q[k][i].a].v);
}
for (int i = 0; i < q[k].size(); ++i)
if (q[k][i].type == 1)
ok[q[k][i].a] = 0;
ans[x] = d[root(q[k][x].a)].second;
undo();
}
for (int i = 0; i < q[k].size(); ++i)
if (q[k][i].type == 2)
cout << ans[i] << '\n';
else
e[q[k][i].a].c = q[k][i].b;
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[k].size(); ++i)
~~^~~~~~~~~~~~~
bridges.cpp:109:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[k].size(); ++i)
~~^~~~~~~~~~~~~
bridges.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (index < e.size() && e[id[index]].c >= q[k][x].b) {
~~~~~~^~~~~~~~~~
bridges.cpp:121:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[k].size(); ++i)
~~^~~~~~~~~~~~~
bridges.cpp:135:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[k].size(); ++i)
~~^~~~~~~~~~~~~
bridges.cpp:144:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[k].size(); ++i)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
41 ms |
640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2227 ms |
4424 KB |
Output is correct |
| 2 |
Correct |
2120 ms |
4080 KB |
Output is correct |
| 3 |
Correct |
2175 ms |
4168 KB |
Output is correct |
| 4 |
Correct |
2300 ms |
4340 KB |
Output is correct |
| 5 |
Correct |
2314 ms |
4180 KB |
Output is correct |
| 6 |
Correct |
2734 ms |
6520 KB |
Output is correct |
| 7 |
Correct |
2805 ms |
6528 KB |
Output is correct |
| 8 |
Correct |
2697 ms |
6628 KB |
Output is correct |
| 9 |
Correct |
191 ms |
2680 KB |
Output is correct |
| 10 |
Correct |
1656 ms |
5360 KB |
Output is correct |
| 11 |
Correct |
1527 ms |
4976 KB |
Output is correct |
| 12 |
Correct |
2110 ms |
6720 KB |
Output is correct |
| 13 |
Correct |
2005 ms |
6128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1912 ms |
3812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3074 ms |
5484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2227 ms |
4424 KB |
Output is correct |
| 2 |
Correct |
2120 ms |
4080 KB |
Output is correct |
| 3 |
Correct |
2175 ms |
4168 KB |
Output is correct |
| 4 |
Correct |
2300 ms |
4340 KB |
Output is correct |
| 5 |
Correct |
2314 ms |
4180 KB |
Output is correct |
| 6 |
Correct |
2734 ms |
6520 KB |
Output is correct |
| 7 |
Correct |
2805 ms |
6528 KB |
Output is correct |
| 8 |
Correct |
2697 ms |
6628 KB |
Output is correct |
| 9 |
Correct |
191 ms |
2680 KB |
Output is correct |
| 10 |
Correct |
1656 ms |
5360 KB |
Output is correct |
| 11 |
Correct |
1527 ms |
4976 KB |
Output is correct |
| 12 |
Correct |
2110 ms |
6720 KB |
Output is correct |
| 13 |
Correct |
2005 ms |
6128 KB |
Output is correct |
| 14 |
Incorrect |
1912 ms |
3812 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
41 ms |
640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
