| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 678124 | Cross_Ratio | Bridges (APIO19_bridges) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> root;
vector<array<int, 4>> V;
UnionFind(int N) {
root.resize(N);
fill(root.begin(),root.end(),-1);
}
int Find(int n) {
if(root[n]<0) return n;
return Find(root[n]);
}
int Merge(int x, int y) {
x = Find(x), y = Find(y);
if(x==y) return 0;
if(root[x]>root[y]) swap(x, y);
V.push_back({x, root[x], y, root[y]});
root[x] += root[y];
root[y] = x;
return 1;
}
void rollback() {
if(V.size()==0) return;
auto it = V.back();
root[it[0]] = it[1], root[it[2]] = it[3];
V.pop_back();
}
};
int A[100005];
int B[100005];
int C[100005];
int D[100005];
array<int, 3> Query[100005];
int ans[100005];
int sB = 2650;
bool chan[100005];
int N, M;
vector<int> idx;
int id(int n) {
return lower_bound(idx.begin(),idx.end(),n)-idx.begin();
}
void calc(int s, int e) {
int i, j;
for(i=s;i<e;i++) {
if(Query[i][0]==1) {
chan[Query[i][1]] = true;
}
}
idx.clear();
for(i=0;i<M;i++) {
if(!chan[i]) {
idx.push_back(C[i]);
}
}
for(i=s;i<e;i++) {
if(Query[i][0]==2) idx.push_back(Query[i][2]);
}
sort(idx.begin(),idx.end());
idx.erase(unique(idx.begin(),idx.end()),idx.end());
vector<vector<int>> V1, V2;
V1.resize(idx.size());
V2.resize(idx.size());
vector<int> E;
for(i=0;i<M;i++) {
if(!chan[i]) {
V1[id(C[i])].push_back(i);
}
else E.push_back(i);
}
vector<array<int, 3>> F;
for(i=s;i<e;i++) {
if(Query[i][0]==2) V2[id(Query[i][2])].push_back(i);
else F.push_back({i, Query[i][1], Query[i][2]});
}
UnionFind UF(N);
for(i=idx.size()-1;i>=0;i--) {
for(int k : V1[i]) {
UF.Merge(A[k], B[k]);
pv = e+1, st = -1;
}
for(int k : V2[i]) {
if(pv > k) {
for(int v : E) {
D[v] = C[v];
}
for(j=0;j<F.size();j++) {
if(F[j][0] < k) D[F[j][1]] = F[j][2];
else {
break;
}
}
st = j;
}
else {
for(j = st; j < F.size();j++) {
if(F[j][0]<k) D[F[j][1]] = F[j][2];
else {
break;
}
}
st = j;
}
pv = k;
int sum = 0;
for(int v : E) {
if(Query[k][2] <= D[v]) {
sum += UF.Merge(A[v], B[v]);
}
}
ans[k] = -UF.root[UF.Find(Query[k][1])];
while(sum--) {
UF.rollback();
}
}
}
for(i=0;i<M;i++) chan[i] = false;
for(i=s;i<e;i++) {
if(Query[i][0]==1) C[Query[i][1]] = Query[i][2];
}
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
int i, j;
for(i=0;i<M;i++) {
cin >> A[i] >> B[i] >> C[i];
A[i]--, B[i]--;
}
int Q;
cin >> Q;
for(i=0;i<Q;i++) {
cin >> Query[i][0] >> Query[i][1] >> Query[i][2];
Query[i][1]--;
}
int pt = 0;
for(i=0;i<Q;i++) {
if(i%sB==sB-1||i==Q-1) {
calc(pt, i+1);
pt = i+1;
}
}
for(i=0;i<Q;i++) {
if(Query[i][0]==2) cout << ans[i] << '\n';
}
}