#include "collapse.h"
#include <bits/stdc++.h>
#warning W e PREFIXUL
using namespace std;
// Pentru fiecare bucata de radical, avem in total N^2/B muchii incluse direct (idfk)
// Muchii care ating partial (se includ sau pe prefix suffix etc) pot fi doar O(B)
// pentru fiecare query, procesam muchiile de primul tip (compl e spusa), iar dupa punem fortat (si dupa scoatem)
// toate muchiile de al doilea tip. Astfel, la fiecare query avem compl O(Q * B).
// Wow, chiar a fost greu sa scrie si ei un editorial atat de uman (nu ca as fi eu zeu, dar mna)
int B;
const int nmax = 1e5 + 5, qmax = 1e5 + 5, cmax = 1e5 + 5;
using pii = pair<int,int>;
int n, q, c;
// 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] = father(dsu[dsu[x]])));
}
int gettime() {return bk.size();}
void unite(int a, int b) {
a = father(a);
b = father(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();
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() {
//cout << "======\n";
//cout << L << ' ' << R << '\n';
//for(auto x : included)
//cout << edge[x].first << ' ' <<edge[x].second << '\n';
for(auto X : partial) {
int edg, l, r;
tie(edg, l, r) = X;
//cout << edge[edg].first << ' ' <<edge[edg].second << '\t' << l << ' ' << r << '\n';
}
//for(auto x : queries)
//cout << "?" << qs[x].first << ' ' << qs[x].second << '\n';
//return;
if(DSU::gettime() > n)
DSU::init(n);
else
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);
}
//cout << qs[idx].first << ' ' << qs[idx].second << ":\n";
//for(auto X : DSU::bk)
//cout << X.first << ' ' << X.second << '\n';
//cout <<"! " << DSU::query() << ' ' << (n - qs[idx].second - 1) << '\n';
rez[idx] += DSU::query() - (n - qs[idx].second - 1);
if(DSU::gettime() > temporary)
while(DSU::rollback() > temporary);
}
}
};
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(c + 1, c + 2));
//cerr << "CINE\n";
for(int i = 0; i < edge.size(); i++) {
int ptr = 0;
//cout << '\n'<<edge[i].first << ' ' << edge[i].second << '\n';
for(auto X : span[i]) {
tie(l, r) = X;
//cout << l << ' '<< r << "--> ";
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++)
//cerr << qs[i].first << ' ' << B << ' ' << qs[i].first / B << '\n',
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);
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];
//cout << t[i] << ' ' << 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;
//cout << open[x][y] << '\n';
}
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;
}
}
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 = sqrt(c / 2);
Driver::DSU::init(n);
Driver::Init::read(T, X, Y, W, P);
Driver::Init::prepare();
Driver::Decomp::start();
Driver::erase();
for(int i = 0; i < c; i++) {
X[i] = N - X[i] - 1;
Y[i] = N - Y[i] - 1;
}
for(int i = 0; i < q; i++)
P[i] = N - P[i] - 2;
Driver::Init::read(T, X, Y, W, P);
Driver::Init::prepare();
Driver::Decomp::start();
return Driver::rez;
}
Compilation message
collapse.cpp:3:2: warning: #warning W e PREFIXUL [-Wcpp]
3 | #warning W e PREFIXUL
| ^~~~~~~
collapse.cpp: In member function 'void Driver::Bucket::apply()':
collapse.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | while(ptr < included.size() && edge[included[ptr]].second <= time)
| ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp: In function 'void Driver::Init::prepare()':
collapse.cpp:126:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(int i = 0; i < edge.size(); i++) {
| ~~^~~~~~~~~~~~~
collapse.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Driver::Bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | if(ptr == decomp.size())
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
584 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
427 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
509 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
584 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
