#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 = 2e5;
const int SQ = 330;
struct Query { int t, x, y, s; };
int N, C, Q, M;
int T[MAXN+10], X[MAXN+10], Y[MAXN+10], W[MAXN+10], P[MAXN+10], ans[MAXN+10];
Query U[MAXN+10];
int Par[MAXN+10], Rank[MAXN+10];
int Find(int x) { return x==Par[x] ? x : Find(Par[x]); }
vector<Query> query;
vector<int> simulateCollapse(int _N, vector<int> _T, vector<int> _X, vector<int> _Y, vector<int> _W, vector<int> _P)
{
int i, j, k;
N=_N; C=_T.size(); Q=_W.size(); M=C+Q;
for(i=1; i<=C; i++) T[i]=_T[i-1], X[i]=_X[i-1]+1, Y[i]=_Y[i-1]+1;
for(i=1; i<=C; i++) if(X[i]>Y[i]) swap(X[i], Y[i]);
for(i=1; i<=Q; i++) W[i]=_W[i-1]+1, P[i]=_P[i-1]+1;
for(i=1; i<=Q; i++) U[i]={W[i], P[i], i};
sort(U+1, U+Q+1, [&](const Query &p, const Query &q) { return p.t<q.t; });
for(i=1, j=1; i<=C; i++)
{
query.push_back({T[i], X[i], Y[i], query.size()});
for(; U[j].t<=i && j<=Q; j++) query.push_back({-1, U[j].x, U[j].y, query.size()});
}
//for(auto it : query) printf("QUERY %d %d %d %d\n", it.t, it.x, it.y, it.s);
set<pii> alive;
for(i=0; i<=M/SQ; i++)
{
int s=i*SQ, e=min(M, (i+1)*SQ);
int it, jt;
vector<pii> edge;
vector<Query> upd, ask;
for(auto it : alive) edge.push_back(it);
for(j=s; j<e; j++)
{
if(query[j].t==-1) ask.push_back(query[j]);
else upd.push_back(query[j]);
}
sort(edge.begin(), edge.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
sort(ask.begin(), ask.end(), [&](const Query &p, const Query &q) { return p.x<q.x; });
for(j=1; j<=N; j++) Par[j]=j, Rank[j]=1;
int cnt=0;
it=0, jt=0;
for(j=1; j<=N; j++)
{
for(; it<edge.size() && edge[it].second<=j; it++)
{
int u=edge[it].first, v=edge[it].second;
u=Find(u); v=Find(v);
if(u==v) continue;
if(Rank[u]<Rank[v]) swap(u, v);
Rank[u]+=Rank[v]; Par[v]=u;
cnt++;
}
//printf("!%d\n", cnt);
for(; jt<ask.size() && ask[jt].x<=j; jt++)
{
vector<int> S;
for(k=0; k<upd.size(); k++)
{
if(upd[k].s>=ask[jt].s) continue;
if(upd[k].y>j) continue;
int u=upd[k].x, v=upd[k].y;
u=Find(u); v=Find(v);
if(u==v) continue;
if(Rank[u]<Rank[v]) swap(u, v);
Rank[u]+=Rank[v]; Par[v]=u;
cnt++; S.push_back(v);
}
ans[ask[jt].y]+=cnt;
//printf("! %d !%d %d\n", ask[jt].x, j, cnt);
while(!S.empty())
{
int now=S.back();
Rank[Par[now]]-=Rank[now];
Par[now]=now;
cnt--; S.pop_back();
}
}
}
sort(edge.begin(), edge.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
sort(ask.begin(), ask.end(), [&](const Query &p, const Query &q) { return p.x>q.x; });
for(j=1; j<=N; j++) Par[j]=j, Rank[j]=1;
cnt=0;
it=0, jt=0;
for(j=N; j>=1; j--)
{
for(; it<edge.size() && edge[it].first>=j; it++)
{
int u=edge[it].first, v=edge[it].second;
u=Find(u); v=Find(v);
if(Rank[u]<Rank[v]) swap(u, v);
Rank[u]+=Rank[v]; Par[v]=u;
cnt++;
}
//printf("!%d\n", cnt);
for(; jt<ask.size() && ask[jt].x+1>=j; jt++)
{
vector<int> S;
for(k=0; k<upd.size(); k++)
{
if(upd[k].s>=ask[jt].s) continue;
if(upd[k].x<j) continue;
int u=upd[k].x, v=upd[k].y;
u=Find(u); v=Find(v);
if(u==v) continue;
if(Rank[u]<Rank[v]) swap(u, v);
Rank[u]+=Rank[v]; Par[v]=u;
cnt++; S.push_back(v);
}
ans[ask[jt].y]+=cnt;
//printf("!!%d %d\n", j, cnt);
while(!S.empty())
{
int now=S.back();
Rank[Par[now]]-=Rank[now];
Par[now]=now;
cnt--; S.pop_back();
}
}
}
for(j=0; j<upd.size(); j++) alive.insert({upd[j].x, upd[j].y});
}
for(i=1; i<=Q; i++) ans[i]=N-ans[i];
return vector<int>(ans+1, ans+Q+1);
}
Compilation message
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:36:54: warning: narrowing conversion of 'query.std::vector<Query>::size()' from 'std::vector<Query>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
query.push_back({T[i], X[i], Y[i], query.size()});
~~~~~~~~~~^~
collapse.cpp:37:86: warning: narrowing conversion of 'query.std::vector<Query>::size()' from 'std::vector<Query>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
for(; U[j].t<=i && j<=Q; j++) query.push_back({-1, U[j].x, U[j].y, query.size()});
~~~~~~~~~~^~
collapse.cpp:66:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; it<edge.size() && edge[it].second<=j; it++)
~~^~~~~~~~~~~~
collapse.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; jt<ask.size() && ask[jt].x<=j; jt++)
~~^~~~~~~~~~~
collapse.cpp:80:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k=0; k<upd.size(); k++)
~^~~~~~~~~~~
collapse.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; it<edge.size() && edge[it].first>=j; it++)
~~^~~~~~~~~~~~
collapse.cpp:124:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; jt<ask.size() && ask[jt].x+1>=j; jt++)
~~^~~~~~~~~~~
collapse.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k=0; k<upd.size(); k++)
~^~~~~~~~~~~
collapse.cpp:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<upd.size(); j++) alive.insert({upd[j].x, upd[j].y});
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
7056 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
7016 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
7144 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
7156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
