| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 547394 | cadmiumsky | Collapse (JOI18_collapse) | 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 "collapse.h"
#include <bits/stdc++.h>
#warning W e PREFIXUL
using namespace std;
int B;
const int nmax = 1e5 + 5, qmax = 1e5 + 5, cmax = 1e5 + 5;
using pii = pair<int,int>;
int n, q, c;
int rollbacks = 0, forceinsert = 0, always = 0;
// decomp dupa POZITIE
namespace Driver {
namespace DSU {
int area[nmax], dsu[nmax];
vector<pair<int,int> > bk;
int cc;
void init(int n) {
for(int i = 0; i < n; i++)
dsu[i] = i, area[i] = 1;
bk.clear();
cc = n;
return;
}
int father(int x) {
return (dsu[x] == x? x : father(dsu[x]));
}
int comprfather(int x) {
return (dsu[x] == x? x : dsu[x] = father(dsu[x]));
}
int gettime() {return bk.size();}
void unite(int a, int b, bool compr) {
if(!compr)
a = father(a),
b = father(b);
else
a = comprfather(a),
b = comprfather(b);
if(a == b)
return;
if(area[a] < area[b])
swap(a, b);
dsu[b] = a;
area[a] += area[b];
dsu[b] = a;
bk.push_back({b, a});
cc--;
}
int rollback() {
if(bk.size() == 0)
return -1;
int a, b;
tie(b, a) = bk.back();
dsu[b] = b;
area[a] -= area[b];
cc++;
bk.pop_back();
//rollbacks++;
return bk.size();
}
int query() { return cc; }
}
unordered_map<int, unordered_map<int,int> > atredge;
unordered_map<int, unordered_map<int,int> > open;
vector< pair<int,int> > edge;
vector< vector< pair<int,int> > > span;
vector< pair<int, int> > qs;
vector<int> rez;
struct Bucket {
vector<int> included;
vector<tuple<int,int,int> > partial;
int L, R;
vector<int> queries;
Bucket(int l, int r) {tie(L, R) = {l, r};}
void apply() {
while(DSU::rollback() > 0);
sort(queries.begin(), queries.end(), [&](auto x, auto y) {return qs[x].second < qs[y].second;});
sort(included.begin(), included.end(), [&](auto x, auto y) {return edge[x].second < edge[y].second;});
int ptr = 0;
for(auto idx : queries) {
int poz, time;
tie(poz, time) = qs[idx];
while(ptr < included.size() && edge[included[ptr]].second <= time)
DSU::unite(edge[included[ptr]].first, edge[included[ptr]].second), ptr++;
int temporary = DSU::gettime();
for(auto X : partial) {
int edg, l, r;
tie(edg, l, r) = X;
if(l <= poz && poz <= r && edge[edg].second <= time)
DSU::unite(edge[edg].first, edge[edg].second);
//always++;
}
rez[idx] += DSU::query() - (n - qs[idx].second - 1);
if(DSU::gettime() > temporary)
while(DSU::rollback() > temporary);
}
//forceinsert += included.size();
}
};
vector<Bucket> decomp;
namespace Init {
void prepare() {
int l = 0, r = min(c - 1, B - 1);
while(l < c) {
decomp.push_back(Bucket(l, r));
l += B;
r = min(c - 1, r + B);
}
decomp.push_back(Bucket(2 * c + 1, 2 * c + 2));
for(int i = 0; i < edge.size(); i++) {
int ptr = 0;
for(auto X : span[i]) {
tie(l, r) = X;
while(decomp[ptr].R < l)
ptr++;
if(ptr == decomp.size())
break;
decomp[ptr].partial.push_back({i, l, r});
if(r <= decomp[ptr].R)
continue;
ptr++;
while(l <= decomp[ptr].L && decomp[ptr].R <= r)
decomp[ptr++].included.push_back(i);
if(!(decomp[ptr].R < l || decomp[ptr].L > r))
decomp[ptr].partial.push_back({i, l, r});
}
}
for(int i = 0; i < q; i++)
decomp[qs[i].first / B].queries.push_back(i);
return;
}
void read(vector<int> t, vector<int>& lf, vector<int>& rh, vector<int> w, vector<int> p) {
rez.resize(q, 0);
for(int i = 0, ptr; i < c; i++) {
int x, y;
tie(x, y) = {lf[i], rh[i]};
if(x > y)
swap(lf[i], rh[i]), swap(x, y);
if(atredge.find(x) == atredge.end() || atredge[x].find(y) == atredge[x].end())
atredge[x][y] = edge.size(), span.push_back(vector<pii>()), edge.push_back({x, y});
ptr = atredge[x][y];
open[x][y];
if(open[x][y] == 0)
span[ptr].push_back({i, -1});
open[x][y] += -2 * t[i] + 1;
if(open[x][y] == 0)
span[ptr].back().second = i - 1;
}
int x, y, val;
for(auto X : open) {
x = X.first;
for(auto Y : X.second) {
tie(y, val) = Y;
if(val > 0)
span[atredge[x][y]].back().second = c - 1;
}
}
for(int i = 0; i < q; i++)
qs.push_back({w[i], p[i]});
return;
}
void flip() {
for(int i = 0; i < edge.size(); i++)
edge[i].first = n - edge[i].first - 1,
edge[i].second = n - edge[i].second - 1;
for(int i = 0; i < q; i++)
qs[i].second = n - qs[i].second - 2;
}
}
namespace Decomp {
void start() {
for(auto& x : decomp)
x.apply();
}
}
void erase() {
DSU::init(n);
decomp.clear();
span.clear();
qs.clear();
edge.clear();
atredge.clear();
open.clear();
}
}
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
) {
n = N;
c = T.size();
q = W.size();
B = 220;
Driver::DSU::init(n);
Driver::Init::read(T, X, Y, W, P);
Driver::Init::prepare();
Driver::Decomp::start();
Driver::DSU::init(n);
Driver::Init::flip();
Driver::Decomp::start();
return Driver::rez;
}