#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int SQ = 1500;
struct Query { int t, x, y, p; };
int N, C, Q;
Query A[MAXN+10], B[MAXN+10], V[MAXN*2+10];
vector<int> ans;
struct UF
{
int par[MAXN+10], sz[MAXN+10];
vector<int> S;
void init()
{
int i, j;
S.clear();
for(i=1; i<=N; i++) par[i]=i, sz[i]=1;
}
int Find(int x) { return x==par[x] ? x : Find(par[x]); }
int Union(int x, int y)
{
x=Find(x); y=Find(y);
if(x==y) return 0;
if(sz[x]<sz[y]) swap(x, y);
sz[x]+=sz[y]; par[y]=x;
S.push_back(y);
return 1;
}
void restore()
{
int v=S.back(); S.pop_back();
sz[par[v]]-=sz[v];
par[v]=v;
}
}uf;
vector<int> simulateCollapse(int _N, vector<int> _T, vector<int> _X, vector<int> _Y, vector<int> _W, vector<int> _P)
{
int i, j, k, p, q;
N=_N; C=_T.size(); Q=_W.size(); ans.resize(Q, N);
for(i=0; i<C; i++) if(_X[i]>_Y[i]) swap(_X[i], _Y[i]);
for(i=0; i<C; i++) A[i+1]={_T[i], _X[i]+1, _Y[i]+1, i+1};
for(i=0; i<Q; i++) B[i+1]={-1, _P[i]+1, i, _W[i]+1};
for(i=1; i<=C; i++) V[i]=A[i];
for(i=1; i<=Q; i++) V[i+C]=B[i];
sort(V+1, V+C+Q+1, [&](const Query &p, const Query &q)
{
if(p.p!=q.p) return p.p<q.p;
else return p.t>q.t;
});
for(i=0; i<=(C+Q)/SQ; i++)
{
int l=max(1, i*SQ), r=min(C+Q, (i+1)*SQ-1);
set<pii> S;
vector<pii> E1, E2;
vector<int> query;
for(j=1; j<l; j++)
{
if(V[j].t==0) S.insert({V[j].x, V[j].y});
else if(V[j].t==1) S.erase({V[j].x, V[j].y});
}
for(j=l; j<=r; j++)
{
if(V[j].t==-1)
{
query.push_back(j);
}
else
{
if(S.count({V[j].x, V[j].y}))
{
S.erase({V[j].x, V[j].y});
E2.push_back({V[j].x, V[j].y});
}
}
}
for(auto it : S) E1.push_back(it);
sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x<V[q].x; });
uf.init(); j=0;
for(auto &it : query)
{
for(; j<E1.size() && E1[j].second<=V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
set<pii> S1; vector<pii> S2;
for(p=l; p<=it; p++)
{
if(V[p].t==-1) continue;
if(V[p].y>V[it].x) continue;
if(V[p].t==0) S1.insert({V[p].x, V[p].y});
else S1.erase({V[p].x, V[p].y});
S2.push_back({V[p].x, V[p].y});
}
sort(S2.begin(), S2.end());
int cnt=0;
for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
for(auto jt : E2) if(jt.second<=V[it].x && !binary_search(S2.begin(), S2.end(), jt)) cnt+=uf.Union(jt.first, jt.second);
ans[V[it].y]-=uf.S.size();
while(cnt--) uf.restore();
}
sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x>V[q].x; });
uf.init(); j=0;
for(auto &it : query)
{
for(; j<E1.size() && E1[j].first>V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
set<pii> S1; vector<pii> S2;
for(p=l; p<=it; p++)
{
if(V[p].t==-1) continue;
if(V[p].x<=V[it].x) continue;
if(V[p].t==0) S1.insert({V[p].x, V[p].y});
else S1.erase({V[p].x, V[p].y});
S2.push_back({V[p].x, V[p].y});
}
int cnt=0;
for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
for(auto jt : E2) if(jt.first>V[it].x && !binary_search(S2.begin(), S2.end(), jt)) cnt+=uf.Union(jt.first, jt.second);
ans[V[it].y]-=uf.S.size();
while(cnt--) uf.restore();
}
}
return ans;
}
Compilation message
collapse.cpp: In member function 'void UF::init()':
collapse.cpp:24:10: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
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:100:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j<E1.size() && E1[j].second<=V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
~^~~~~~~~~~
collapse.cpp:125:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j<E1.size() && E1[j].first>V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
~^~~~~~~~~~
collapse.cpp:48:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k, p, q;
^
collapse.cpp:48:18: warning: unused variable 'q' [-Wunused-variable]
int i, j, k, p, q;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
896 KB |
Output is correct |
| 2 |
Correct |
11 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
5884 KB |
Output is correct |
| 2 |
Correct |
156 ms |
5888 KB |
Output is correct |
| 3 |
Incorrect |
2477 ms |
11360 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
5880 KB |
Output is correct |
| 2 |
Correct |
158 ms |
5888 KB |
Output is correct |
| 3 |
Correct |
159 ms |
5880 KB |
Output is correct |
| 4 |
Correct |
163 ms |
5880 KB |
Output is correct |
| 5 |
Correct |
220 ms |
6008 KB |
Output is correct |
| 6 |
Correct |
562 ms |
6476 KB |
Output is correct |
| 7 |
Correct |
6549 ms |
14988 KB |
Output is correct |
| 8 |
Correct |
9159 ms |
17880 KB |
Output is correct |
| 9 |
Correct |
179 ms |
6648 KB |
Output is correct |
| 10 |
Correct |
275 ms |
6776 KB |
Output is correct |
| 11 |
Correct |
9923 ms |
18780 KB |
Output is correct |
| 12 |
Correct |
9996 ms |
18964 KB |
Output is correct |
| 13 |
Correct |
10094 ms |
19116 KB |
Output is correct |
| 14 |
Correct |
10369 ms |
18856 KB |
Output is correct |
| 15 |
Correct |
10126 ms |
18756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
896 KB |
Output is correct |
| 2 |
Correct |
11 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
