#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
using namespace std;
class DisjointSetUnion {
private:
vector<int> parent;
vector<int> compSize;
int n;
int connectedComponents;
public:
int getConnectedComponents() const {
return connectedComponents;
}
int getNeighbors (int x) {
return compSize[find_head(x)];
}
public:
void resz (int sz){
n = sz;
connectedComponents = sz;
parent.resize(sz), compSize.resize(sz);
for (int i = 0; i < n; i++) {
parent[i] = i, compSize[i] = 1;
}
}
int find_head(int x) const {
int cur = x;
while (cur != parent[cur]) {
cur = parent[cur];
}
return cur;
}
void join(int x, int y) {
x = find_head(x);
y = find_head(y);
if (x == y) {
return;
}
if (compSize[x] > compSize[y]) {
swap(x, y);
//ensures that compSize[x1] <= compSize[y1]
}
parent[x] = y;
compSize[y] += compSize[x];
connectedComponents--;
}
bool comp(int x, int y) {
return (find_head(x) == find_head(y));
}
};
class Query {
public:
int w;
int x;
int type;
int q;
//w is hte weight thing
Query (int w, int x, int type, int q) {
this->w = w, this->x = x, this->type = type, this-> q = q;
}
bool operator < (const Query myQuery) const {
if (myQuery.w != w) return (myQuery.w < w);
if (myQuery.x != x) return (myQuery.x < x);
if (myQuery.type != type) return (myQuery.type < type);
return false;
}
};
bool comp_index (Query a, Query b) {
return (a.q < b.q);
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<pair<pair<int,int>,int>> edges;
for (int i = 0; i < M; i++) {
int x, y, z; cin >> x >> y >> z; x--, y--;
edges.push_back({{x, y}, z});
}
int Q;
cin >> Q;
vector<vector<Query>> blocks;
blocks.emplace_back();
for (int i = 0; i < Q; i++) {
if (blocks.back().size() > sqrt(Q)) {
blocks.emplace_back();
}
int t, w, x; cin >> t >> x >> w; x--;
blocks.back().emplace_back(Query(w, x, t, i));
}
map<int,int> default_edges;
for (int i = 0; i < M; i++) {
default_edges[i] = edges[i].second;
}
vector<pair<int,int>> myVec;
for (auto& v: blocks) {
sort(v.begin(), v.end()); //sort the blocks by weight
reverse(v.begin(), v.end());
DisjointSetUnion dsu;
dsu.resz(N);
set<int> uncertain;
set<pair<int,int>> unknown[M];
for (Query q: v) {
if (q.type == 1) {
uncertain.insert(q.x);
//cout << "INSERT " << edges[q.x].first.first << " " << edges[q.x].first.second << '\n';
unknown[q.x].insert({q.q, q.w});
}
}
for (auto& p: default_edges) {
unknown[p.first].insert({-1, p.second});
}
map<int,vector<int>> e;
for (int i = 0; i < M; i++) {
if (!uncertain.count(i)) {
e[edges[i].second].push_back(i);
}
}
int prev = -1;
reverse(v.begin(), v.end());
for (Query q: v) {
for (auto it = e.begin(); it != e.end(); it++) {
if ((*it).first < q.w) {
continue;
}
for (int i: (*it).second) {
prev = (*it).first;
//cout << "JOIN " << edges[i].first.first << " " << edges[i].first.second << '\n';
dsu.join(edges[i].first.first, edges[i].first.second);
}
}
if (q.type == 1) {
continue;
}
DisjointSetUnion prev_dsu = dsu;
for (int x: uncertain) {
auto it = unknown[x].lower_bound({q.q + 1, -1});
it--;
int lastVal = (*it).second;
if (lastVal >= q.w) {
//cout << "TEMP JOIN " << edges[x].first.first << " " << edges[x].first.second << '\n';
dsu.join(edges[x].first.first, edges[x].first.second);
}
}
//cout << dsu.getNeighbors(q.x) << '\n';
myVec.push_back({q.q, dsu.getNeighbors(q.x)});
dsu = prev_dsu;
}
sort(v.begin(), v.end(), comp_index);
for (Query q: v) {
if (q.type == 1) {
default_edges[q.x] = q.w;
}
}
//cout << "-----\n";
}
sort(myVec.begin(), myVec.end());
for (auto& p: myVec) {
cout <<p.second << '\n';
}
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:136:13: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
136 | int prev = -1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
