#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
struct dsu0 {
vector<int> par, siz;
int n;
int cc;
int largest;
void init(int n) {
assert(n>0);
this->n=n;
cc=n;
par.resize(n+10);siz.resize(n+10);
for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
largest=1;
}
int parent(int x) {
assert(x>=0 && x<n);
return par[x]==x?x:par[x]=parent(par[x]);
}
bool join(int x, int y) {
x=parent(x);y=parent(y);
if (x==y) return false;
cc--;
if (siz[x]<siz[y]) swap(x,y);
siz[x]+=siz[y];par[y]=x;
largest=max(largest,siz[x]);
return true;
}
};
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e5 + 5;
struct line {
int type, x, y;
line(int _t, int _x, int _y) : type(_t), x(_x), y(_y) {}
};
set<int> g[maxn];
set<pair<int,int>> edges;
void add_edge(int x, int y) {
if (x>y) swap(x,y);
g[x].insert(y);
g[y].insert(x);
edges.insert({x,y});
}
void rem_edge(int x, int y) {
if (x>y) swap(x,y);
g[x].erase(y);
g[y].erase(x);
edges.erase({x,y});
}
vector<int> solve(int N, vector<line> v, vector<vector<pair<int,int>>> ev, int Q) {
int n = v.size();
vector<int> ans(Q);
for (int i=0; i<n; i++) {
if (v[i].type==0) {
add_edge(v[i].x,v[i].y);
} else {
rem_edge(v[i].x,v[i].y);
}
for (auto qu: ev[i]) {
int id = qu.first;
int x = qu.second;
dsu0 dsu; dsu.init(N);
for (auto ed: edges) {
int u = ed.first;
int v = ed.second;
if (u<=x && x+1<=v) continue;
dsu.join(u,v);
}
ans[id] = dsu.cc;
}
}
return ans;
}
struct dsu_rollback {
int n;
vector<int> par, siz;
int cc;
vector<pair<int,int>> undo;
void init(int n) {
this->n=n;
par.resize(n);
siz.resize(n);
for (int i=0; i<n; i++) {
par[i]=i;
siz[i]=1;
}
cc = n;
}
int parent(int x) {
while (par[x] != x) x=par[x];
return x;
}
void join(int u, int v) {
u = parent(u);
v = parent(v);
if (u != v) {
if (siz[u]<siz[v]) swap(u,v);
par[v]=u;
siz[u]+=siz[v];
cc--;
}
undo.push_back({u,v});
}
void rollback() {
assert(undo.size());
int u = undo.back().first;
int v = undo.back().second;
if (u!=v) {
siz[u]-=siz[v];
par[v]=v;
cc++;
}
undo.pop_back();
}
};
const int SQ = 316; // sqrt(10^5) = 316.227
struct dat {
int x, y, id;
dat(int _x, int _y, int _id) : x(_x), y(_y), id(_id) {}
};
bool cmpY(dat A, dat B) {
if (A.y != B.y) return A.y < B.y;
return A.id < B.id;
}
bool cmpX(dat A, dat B) {
if (A.x != B.x) return A.x > B.x;
return A.id < B.id;
}
// All lines in v are addEdge(x,y)
// requests[time]: idx, loc
vector<int> solveTask3(int N, vector<line> v, vector<vector<pair<int,int>>> requests, int Q) {
//cerr<<"task3"<<endl;
int m = v.size();
for (auto &line: v) {
if (line.x>line.y) {
swap(line.x,line.y);
}
}
vector<int> reqTime(Q);
for (int i=0; i<m; i++) {
for (auto p: requests[i]) reqTime[p.first] = i;
}
vector<int> ans(Q, -N);
vector<int> alive;
// iterate over sqrt blocks of time
for (int i=0; i<m; i+=SQ) {
int start = i; int end = min(i+SQ-1, m-1);
// [start, end]
vector<dat> op;
// sort by increasing Y
{
op.clear();
// add all alive graph edits
for (int idx: alive) {
op.push_back({v[idx].x,v[idx].y,-1});
}
// add all relevant queries
for (int j=start; j<=end; j++) {
for (auto p: requests[j]) {
op.push_back({p.second,p.second,p.first});
}
}
sort(op.begin(), op.end(), cmpY);
dsu_rollback dsu;
dsu.init(N);
for (auto o: op) {
if (o.id < 0) {
dsu.join(o.x,o.y);
} else {
int time = reqTime[o.id];
int did = 0;
for (int j=start; j<=time; j++) {
if (v[j].y<=o.x) {
dsu.join(v[j].x,v[j].y);
did++;
}
}
ans[o.id] += dsu.cc;
while (did--) {
dsu.rollback();
}
}
}
}
// sort by decreasing X
{
op.clear();
// add all alive graph edits
for (int idx: alive) {
op.push_back({v[idx].x,v[idx].y,-1});
}
// add all relevant queries
for (int j=start; j<=end; j++) {
for (auto p: requests[j]) {
op.push_back({p.second+1,p.second+1,p.first});
}
}
sort(op.begin(), op.end(), cmpX);
dsu_rollback dsu;
dsu.init(N);
for (auto o: op) {
if (o.id < 0) {
dsu.join(o.x,o.y);
} else {
int time = reqTime[o.id];
int did = 0;
for (int j=start; j<=time; j++) {
if (o.y<=v[j].x) {
dsu.join(v[j].x,v[j].y);
did++;
}
}
ans[o.id] += dsu.cc;
while (did--) {
dsu.rollback();
}
}
}
}
// update alive
for (int j=start; j<=end; j++) {
alive.push_back(j);
}
}
return ans;
}
std::vector<int> simulateCollapse(
int N,
std::vector<int> T,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W,
std::vector<int> P
) {
int n = T.size();
vector<vector<pair<int,int>>> ev(n);
for (int i=0; i<(int)W.size(); i++) {
ev[W[i]].push_back({i,P[i]});
}
bool t0 = true;
vector<line> v;
for (int i=0; i<n; i++) {
v.push_back({T[i],X[i],Y[i]});
if (T[i]==1) t0=false;
}
if (t0) return solveTask3(N, v, ev, W.size());
return solve(N, v, ev, W.size());
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int N, C, Q;
cin>>N>>C>>Q;
vector<int> T, X, Y, W, P;
for (int i=0; i<C; i++) {
int t,x,y;
cin>>t>>x>>y;
T.push_back(t);
X.push_back(x);
Y.push_back(y);
}
for (int i=0; i<Q; i++) {
int w, p;
cin>>w>>p;
W.push_back(w);
P.push_back(p);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
for (int i: res) cout<<i<<" ";
cout<<endl;
return 0;
}
Compilation message
/tmp/ccsd1Snz.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cctJ8hjU.o:collapse.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
