#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 160;
const int SQRT = 320;
//#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;
int T[MAXN], X[MAXN], Y[MAXN]; //Edges
int E[MAXN]; //edge ID.
int W[MAXN], P[MAXN]; //Queries
int ans[MAXN];
struct union_find {
int par[MAXN];
stack<pair<int*, int>> chng; //god fucking damn it. used vector not stack. Then used a "forall" loop on it. But you need to go backward NOT forward iterating through this container!!!
bool active;
int ncomp;
void reset() {
for (int i = 0; i < N; i++) {
par[i] = i;
}
ncomp = N;
assert(chng.empty());
active = false;
}
void change (int &x, int y) {
if (active) {
chng.push(make_pair(&x, x));
}
x = y;
}
int find (int x) {
if (x == par[x]) {
return x;
}
change(par[x], find(par[x]));
return par[x];
}
void merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
change(par[x], y);
change(ncomp, ncomp - 1);
}
void rollback() {
while (!chng.empty()) {
*(chng.top().fi) = chng.top().se;
chng.pop();
}
}
};
int death[MAXN]; //death time of edge.
vector<pii> queries[MAXN]; //queries[day] = vector(position, id)
union_find uf;
int estl[MAXN], estr[MAXN], tmp[MAXN];
bool cmpr (int a, int b) {
return Y[a] < Y[b];
}
bool cmpl (int a, int b) {
return X[a] > X[b];
}
void solve() {
//X, Y = roads constructed
//w, P = questions.
/*
//they aren't vectors but global arrays.
assert(X.size() == C);
assert(Y.size() == C);
assert(W.size() == Q);
assert(P.size() == Q);
*/
for (int i = 0; i < Q; i++) {
queries[W[i]].push_back({P[i], i});
}
for (int sday = 0; sday < C; sday += SQRT) {
int eday = min(sday + SQRT, C);
//what is the stuff before sday? certainly need to add this in.
vector<array<int, 3>> vqu;
for (int i = sday; i < eday; i++) {
for (pii p : queries[i]) {
vqu.push_back({p.fi, i, p.se});
}
}
//ok let's now go to this now.
int posr = 0; //position of estr
//prefix
debug("-------start prefix----------\n");
sort(all(vqu));
uf.reset();
//preliminary add edge if: it is born before sday (edgeid < sday) and if it dies >= eday (death[edgeid] >= eday)
for (auto q : vqu) {
int pos = q[0];
for (; posr < sday && Y[estr[posr]] <= q[0]; posr++) {
int edgeid = estr[posr];
debug("Consider edge (%d, %d). death[%d] = %d. eday = %d\n", X[estr[posr]], Y[estr[posr]], edgeid, death[edgeid], eday);
//assert(death[edgeid] >= eday);
if (edgeid < sday && death[edgeid] >= eday) {
uf.merge(X[edgeid], Y[edgeid]);
debug("Rsection merge %d %d\n", X[edgeid], Y[edgeid]);
}
}
//need this
for (int i = sday; i < eday; i++) {
uf.find(X[i]);
uf.find(Y[i]);
}
uf.active = true;
debug("--active--\n");
//then merge the rest of them!
for (int i = sday; i < eday; i++) {
//is this a valid merge?
debug("Start with ncomp = %d. i = %d\n", uf.ncomp, i);
if (Y[i] <= pos) {
//debug("find(1) == find(56)? %d. find(60) == find(72)? %d.\n", (uf.find(1) == uf.find(56)), (uf.find(60) == uf.find(72))); //this is for the specific test data in "cbad.in" - it gets 36 not 35 in original buggy code for the first query (35 is correct answer)
//only add edge if: born <= q[1] (edgeid <= q[1]) -- this is actually 100% going to happen here -- and not dead yet (death[edgeid] > q[1])
int edgeid = E[i];
debug("EID %d. Need it to be alive at day %d.\n", edgeid, q[1]);
if (edgeid <= q[1] && death[edgeid] > q[1]) {
uf.merge(X[i], Y[i]);
debug("Lsection merge %d %d\n", X[i], Y[i]);
}
}
}
ans[q[2]] += uf.ncomp;
debug("answer[%d] += %d\n", q[2], uf.ncomp);
uf.rollback();
uf.active = false;
debug("--inactive--\n");
}
debug("-------start suffix----------\n");
//suffix
uf.reset();
reverse(all(vqu));
int posl = 0;
for (auto q : vqu) {
int pos = q[0];
//note: strictly greater than q[0]
for (; posl < sday && X[estl[posl]] > q[0]; posl++) {
int edgeid = estl[posl];
if (edgeid < sday && death[edgeid] >= eday) {
uf.merge(X[edgeid], Y[edgeid]);
debug("merge %d %d\n", X[edgeid], Y[edgeid]);
}
}
//need this
for (int i = sday; i < eday; i++) {
uf.find(X[i]);
uf.find(Y[i]);
}
debug("--active--\n");
uf.active = true;
for (int i = sday; i <= q[1]; i++) {
if (X[i] > pos) {
//only add edge if: born <= q[1] (edgeid <= q[1]) -- this is actually 100% going to happen here -- and not dead yet (death[edgeid] > q[1])
int edgeid = E[i];
if (edgeid <= q[1] && death[edgeid] > q[1]) {
uf.merge(X[i], Y[i]);
debug("merge %d %d\n", X[i], Y[i]);
}
}
}
ans[q[2]] += uf.ncomp - N;
debug("answer[%d] += %d; answer[%d] -= N\n", q[2], uf.ncomp, q[2]);
uf.rollback();
debug("--inactive--\n");
uf.active = false;
}
//then add the new edges
vector<int> nedge;
for (int i = sday; i < eday; i++) {
nedge.push_back(i);
}
sort(all(nedge), cmpl);
copy(tmp, merge(estl, estl + sday, all(nedge), tmp, cmpl), estl);
sort(all(nedge), cmpr);
copy(tmp, merge(estr, estr + sday, all(nedge), tmp, cmpr), estr);
}
}
vector<int> simulateCollapse (int n, vector<int> ttt, vector<int> xxx, vector<int> yyy, vector<int> www, vector<int> ppp) {
//globalize the variables
N = n;
C = xxx.size();
Q = www.size();
for (int i = 0; i < C; i++) {
T[i] = ttt[i];
X[i] = xxx[i];
Y[i] = yyy[i];
}
for (int i = 0; i < Q; i++) {
W[i] = www[i];
P[i] = ppp[i];
}
map<pii, vector<int>> mpind;
for (int i = 0; i < C; i++) {
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
pii p(X[i], Y[i]);
if (T[i] == 1) {
//remove it
int ind = mpind.at(p).back();
death[ind] = i;
debug("death (%d, %d) is %d. ind = %d --> death[%d] = %d\n", X[ind], Y[ind], i, ind, ind, i);
E[i] = ind;
mpind.at(p).pop_back();
} else {
death[i] = C;
E[i] = i;
mpind[p].push_back(i);
}
}
for (int i = 0; i < 6; i++) {
debug("death[%d] = %d\n", i, death[i]);
}
solve();
return vector<int> (ans, ans + Q);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
3320 KB |
Output is correct |
| 2 |
Correct |
9 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
10 ms |
3320 KB |
Output is correct |
| 4 |
Correct |
11 ms |
3344 KB |
Output is correct |
| 5 |
Incorrect |
22 ms |
3480 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
8516 KB |
Output is correct |
| 2 |
Correct |
56 ms |
8516 KB |
Output is correct |
| 3 |
Incorrect |
473 ms |
14720 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
14720 KB |
Output is correct |
| 2 |
Correct |
65 ms |
14720 KB |
Output is correct |
| 3 |
Correct |
91 ms |
14720 KB |
Output is correct |
| 4 |
Correct |
140 ms |
14720 KB |
Output is correct |
| 5 |
Correct |
644 ms |
14720 KB |
Output is correct |
| 6 |
Correct |
661 ms |
14720 KB |
Output is correct |
| 7 |
Correct |
1718 ms |
20656 KB |
Output is correct |
| 8 |
Correct |
2591 ms |
24964 KB |
Output is correct |
| 9 |
Correct |
79 ms |
24964 KB |
Output is correct |
| 10 |
Correct |
633 ms |
24964 KB |
Output is correct |
| 11 |
Correct |
2830 ms |
25236 KB |
Output is correct |
| 12 |
Correct |
3112 ms |
25308 KB |
Output is correct |
| 13 |
Correct |
3115 ms |
25388 KB |
Output is correct |
| 14 |
Correct |
2905 ms |
25388 KB |
Output is correct |
| 15 |
Correct |
3034 ms |
25452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
3320 KB |
Output is correct |
| 2 |
Correct |
9 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
10 ms |
3320 KB |
Output is correct |
| 4 |
Correct |
11 ms |
3344 KB |
Output is correct |
| 5 |
Incorrect |
22 ms |
3480 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
