#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(requests.size());
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();
}
}
}
}
}
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());
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
6016 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 4 |
Runtime error |
11 ms |
10368 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
17004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
17004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
6016 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 4 |
Runtime error |
11 ms |
10368 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
