#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N, C, Q;
struct union_find {
int par[100010]; //don't forget to init
int ncomp;
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
bool merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
par[x] = y;
ncomp--;
return true;
}
void reset (int sz) {
for (int i = 0; i < sz; i++) {
par[i] = i;
}
ncomp = sz;
}
};
namespace subtask1 {
const int MAXN = 5010;
map<pii, int> mpind;
bitset<MAXN> active[MAXN];
union_find uf;
vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
for (int i = 0; i < C; i++) {
if (i) {
active[i] = active[i - 1];
}
int indxy;
if (mpind.count(pii(X[i], Y[i]))) {
indxy = mpind[pii(X[i], Y[i])];
} else {
indxy = mpind[pii(X[i], Y[i])] = i;
}
if (T[i] == 0) {
active[i][indxy] = true;
} else {
active[i][indxy] = false;
}
}
vector<int> ans;
for (int i = 0; i < Q; i++) {
uf.reset(N);
//day W[i]
for (int j = 0; j < C; j++) {
if (active[W[i]][j]) {
if (!(X[j] <= P[i] && P[i] + 1 <= Y[j])) {
uf.merge(X[j], Y[j]);
debug("avail %d %d\n", X[j], Y[j]);
}
}
}
debug("warm\n");
ans.push_back(uf.ncomp);
}
return ans;
}
}
//should have gotten this...too bad not enough time.
namespace subtask2 {
const int MAXN = 1 << 17;
struct union_findr {
int par[MAXN], sz[MAXN]; //don't forget to init
int ncmp;
pair<int*, int> stk[MAXN * 34];
int stksz;
void init (int n) {
ncmp = n;
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
stksz = 0;
}
int find (int x) {
return x == par[x] ? x : find(par[x]);
}
void change (int &x, int y) {
stk[stksz++] = make_pair(&x, x);
x = y;
}
void merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (sz[x] > sz[y]) {
swap(x, y);
}
change(sz[y], sz[y] + sz[x]);
change(par[x], y);
change(ncmp, ncmp - 1);
}
void rollback (int s) {
while (stksz > s) {
auto p = stk[--stksz];
*(p.fi) = p.se;
}
}
};
union_findr ufl, ufr;
vector<pii> tree[2 * MAXN];
void update (int a, int b, pii v, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return;
}
if (a <= lt && rt <= b) {
tree[cur].push_back(v);
return;
}
int mid = (lt + rt) / 2;
update(a, b, v, 2 * cur, lt, mid);
update(a, b, v, 2 * cur + 1, mid, rt);
}
int P;
int ncompt[MAXN]; //number of components at this time
int seglt[MAXN], segrt[MAXN], segmid[MAXN];
void calcseg (int cur = 1, int lt = 0, int rt = MAXN) {
seglt[cur] = lt;
segrt[cur] = rt;
int mid = (lt + rt) >> 1;
segmid[cur] = mid;
if (rt - lt > 1) {
calcseg((cur << 1), lt, mid);
calcseg((cur << 1) | 1, mid, rt);
}
}
void dfs (int cur = 1) {
int lt = seglt[cur], rt = segrt[cur];
if (lt >= C) {
return;
}
int statel = ufl.stk.size(), stater = ufr.stk.size();
//add edges
for (pii e : tree[cur]) {
if (e.se <= P) {
ufl.merge(e.fi, e.se);
} else if (e.fi > P) {
ufr.merge(e.fi, e.se);
}
}
if (rt - lt == 1) {
ncompt[lt] = ufl.ncmp + ufr.ncmp - N; //minus N -- we both initted to N.
} else {
dfs(cur << 1);
dfs((cur << 1) | 1);
}
ufl.rollback(statel);
ufr.rollback(stater);
}
vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, int ppppp) {
ufl.init(N);
ufr.init(N);
P = ppppp;
map<pii, int> mp;
for (int i = 0; i < C; i++) {
pii e(X[i], Y[i]);
if (mp.count(e)) {
update(mp.at(e), i, e);
mp.erase(e);
} else {
mp[e] = i;
}
}
for (auto it : mp) {
update(it.se, C, it.fi);
}
//ok let's go!
calcseg();
dfs();
vector<int> ans;
for (int day : W) {
ans.push_back(ncompt[day]);
}
return ans;
}
}
namespace subtask3 {
//6s, 512MB
struct query {
int day, pos; //which day? which position?
int id; //what is the index?
};
bool operator < (query q1, query q2) {
return q1.day < q2.day;
}
const int MAXN = 1e5 + 320;
const int SQRT = 320;
union_find uf[SQRT];
int qid[SQRT];
vector<pii> edges;
vector<query> qu;
int ans[MAXN];
vector<int> go (vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
for (int i = 0; i < Q; i++) {
qu.push_back((query) {W[i], P[i], i});
}
sort(all(qu));
for (int i = 0; i < Q; i += SQRT) {
//i to i + Q.
int nq = 0;
for (int j = i; j < Q && j < i + SQRT; j++) {
//let's add this query in
uf[j - i].reset(N);
nq++;
}
//construction plan in this day
int cday = 0;
for (int j = i; j < Q && j < i + SQRT; j++) {
int day = qu[j].day;
for (; cday <= day; cday++) {
//let's add this day in to ALL of 'em
for (int k = 0; k < nq; k++) {
if (!(X[cday] <= qu[j].pos && qu[j].pos + 1 <= Y[cday])) {
uf[k].merge(X[cday], Y[cday]);
}
}
}
//ok let's now query this one!
ans[qu[j].id] = uf[j - i].ncomp;
}
}
return vector<int> (ans, ans + Q);
}
}
vector<int> simulateCollapse (int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
N = n;
C = X.size();
Q = W.size();
for (int i = 0; i < C; i++) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
}
if (N <= 5000 && Q <= 5000) {
return subtask1::go(T, X, Y, W, P);
} else if (count(all(T), 0) == T.size()) {
return subtask3::go(X, Y, W, P);
} else if ((set<int> (all(P))).size() == 1) {
return subtask2::go(T, X, Y, W, P[0]);
}
}
Compilation message
collapse.cpp: In function 'void subtask2::dfs(int)':
collapse.cpp:182:24: error: request for member 'size' in 'subtask2::ufl.subtask2::union_findr::stk', which is of non-class type 'std::pair<int*, int> [4456448]'
int statel = ufl.stk.size(), stater = ufr.stk.size();
^~~~
collapse.cpp:201:16: error: 'stater' was not declared in this scope
ufr.rollback(stater);
^~~~~~
collapse.cpp:201:16: note: suggested alternative: 'statel'
ufr.rollback(stater);
^~~~~~
statel
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:305:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
} else if (count(all(T), 0) == T.size()) {
~~~~~~~~~~~~~~~~~^~~~~~~~~~~
collapse.cpp:310:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
