#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;
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;
}
int main(int argc, char *argv[]) {
int N, C, Q;
scanf("%d%d%d", &N, &C, &Q);
std::vector<int> T(C), X(C), Y(C);
for(int i = 0; i < C; i++) {
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
}
std::vector<int> W(Q), P(Q);
for(int i = 0; i < Q; i++) {
scanf("%d%d", &W[i], &P[i]);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
for(auto i : res) {
printf("%d\n", i);
}
cerr << rollbacks << ' ' << forceinsert << ' ' <<always << '\n';
}
Compilation message
collapse.cpp:4:2: warning: #warning W e PREFIXUL [-Wcpp]
4 | #warning W e PREFIXUL
| ^~~~~~~
collapse.cpp: In member function 'void Driver::Bucket::apply()':
collapse.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while(ptr < included.size() && edge[included[ptr]].second <= time)
| ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp:92:75: error: too few arguments to function 'void Driver::DSU::unite(int, int, bool)'
92 | DSU::unite(edge[included[ptr]].first, edge[included[ptr]].second), ptr++;
| ^
collapse.cpp:39:10: note: declared here
39 | void unite(int a, int b, bool compr) {
| ^~~~~
collapse.cpp:98:57: error: too few arguments to function 'void Driver::DSU::unite(int, int, bool)'
98 | DSU::unite(edge[edg].first, edge[edg].second);
| ^
collapse.cpp:39:10: note: declared here
39 | void unite(int a, int b, bool compr) {
| ^~~~~
collapse.cpp: In function 'void Driver::Init::prepare()':
collapse.cpp:118: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]
118 | for(int i = 0; i < edge.size(); i++) {
| ~~^~~~~~~~~~~~~
collapse.cpp:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Driver::Bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | if(ptr == decomp.size())
| ~~~~^~~~~~~~~~~~~~~~
collapse.cpp: In function 'void Driver::Init::flip()':
collapse.cpp:171: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]
171 | for(int i = 0; i < edge.size(); i++)
| ~~^~~~~~~~~~~~~
collapse.cpp: In function 'int main(int, char**)':
collapse.cpp:218:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
218 | scanf("%d%d%d", &N, &C, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:221:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
221 | scanf("%d%d%d", &T[i], &X[i], &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:225:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
225 | scanf("%d%d", &W[i], &P[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
