#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});
}
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.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 |
15 ms |
896 KB |
Output is correct |
2 |
Correct |
12 ms |
640 KB |
Output is correct |
3 |
Correct |
14 ms |
616 KB |
Output is correct |
4 |
Correct |
14 ms |
640 KB |
Output is correct |
5 |
Correct |
182 ms |
952 KB |
Output is correct |
6 |
Correct |
336 ms |
1216 KB |
Output is correct |
7 |
Correct |
15 ms |
640 KB |
Output is correct |
8 |
Correct |
17 ms |
640 KB |
Output is correct |
9 |
Correct |
220 ms |
1064 KB |
Output is correct |
10 |
Correct |
286 ms |
1016 KB |
Output is correct |
11 |
Correct |
327 ms |
1400 KB |
Output is correct |
12 |
Correct |
338 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
5880 KB |
Output is correct |
2 |
Correct |
127 ms |
6008 KB |
Output is correct |
3 |
Correct |
2729 ms |
11368 KB |
Output is correct |
4 |
Correct |
135 ms |
5880 KB |
Output is correct |
5 |
Correct |
3677 ms |
11384 KB |
Output is correct |
6 |
Correct |
474 ms |
6408 KB |
Output is correct |
7 |
Correct |
7068 ms |
17600 KB |
Output is correct |
8 |
Correct |
3521 ms |
11592 KB |
Output is correct |
9 |
Correct |
144 ms |
6648 KB |
Output is correct |
10 |
Correct |
166 ms |
6776 KB |
Output is correct |
11 |
Correct |
256 ms |
6776 KB |
Output is correct |
12 |
Correct |
4515 ms |
12400 KB |
Output is correct |
13 |
Correct |
5772 ms |
14468 KB |
Output is correct |
14 |
Correct |
7673 ms |
18392 KB |
Output is correct |
15 |
Correct |
7125 ms |
18524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
5880 KB |
Output is correct |
2 |
Correct |
122 ms |
5880 KB |
Output is correct |
3 |
Correct |
134 ms |
5880 KB |
Output is correct |
4 |
Correct |
148 ms |
5880 KB |
Output is correct |
5 |
Correct |
182 ms |
5880 KB |
Output is correct |
6 |
Correct |
619 ms |
6476 KB |
Output is correct |
7 |
Correct |
7193 ms |
14712 KB |
Output is correct |
8 |
Correct |
9994 ms |
17524 KB |
Output is correct |
9 |
Correct |
140 ms |
6648 KB |
Output is correct |
10 |
Correct |
280 ms |
6780 KB |
Output is correct |
11 |
Correct |
10700 ms |
18856 KB |
Output is correct |
12 |
Correct |
10829 ms |
18720 KB |
Output is correct |
13 |
Correct |
10877 ms |
18648 KB |
Output is correct |
14 |
Correct |
10743 ms |
18724 KB |
Output is correct |
15 |
Correct |
10487 ms |
18692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
896 KB |
Output is correct |
2 |
Correct |
12 ms |
640 KB |
Output is correct |
3 |
Correct |
14 ms |
616 KB |
Output is correct |
4 |
Correct |
14 ms |
640 KB |
Output is correct |
5 |
Correct |
182 ms |
952 KB |
Output is correct |
6 |
Correct |
336 ms |
1216 KB |
Output is correct |
7 |
Correct |
15 ms |
640 KB |
Output is correct |
8 |
Correct |
17 ms |
640 KB |
Output is correct |
9 |
Correct |
220 ms |
1064 KB |
Output is correct |
10 |
Correct |
286 ms |
1016 KB |
Output is correct |
11 |
Correct |
327 ms |
1400 KB |
Output is correct |
12 |
Correct |
338 ms |
1272 KB |
Output is correct |
13 |
Correct |
115 ms |
5880 KB |
Output is correct |
14 |
Correct |
127 ms |
6008 KB |
Output is correct |
15 |
Correct |
2729 ms |
11368 KB |
Output is correct |
16 |
Correct |
135 ms |
5880 KB |
Output is correct |
17 |
Correct |
3677 ms |
11384 KB |
Output is correct |
18 |
Correct |
474 ms |
6408 KB |
Output is correct |
19 |
Correct |
7068 ms |
17600 KB |
Output is correct |
20 |
Correct |
3521 ms |
11592 KB |
Output is correct |
21 |
Correct |
144 ms |
6648 KB |
Output is correct |
22 |
Correct |
166 ms |
6776 KB |
Output is correct |
23 |
Correct |
256 ms |
6776 KB |
Output is correct |
24 |
Correct |
4515 ms |
12400 KB |
Output is correct |
25 |
Correct |
5772 ms |
14468 KB |
Output is correct |
26 |
Correct |
7673 ms |
18392 KB |
Output is correct |
27 |
Correct |
7125 ms |
18524 KB |
Output is correct |
28 |
Correct |
114 ms |
5880 KB |
Output is correct |
29 |
Correct |
122 ms |
5880 KB |
Output is correct |
30 |
Correct |
134 ms |
5880 KB |
Output is correct |
31 |
Correct |
148 ms |
5880 KB |
Output is correct |
32 |
Correct |
182 ms |
5880 KB |
Output is correct |
33 |
Correct |
619 ms |
6476 KB |
Output is correct |
34 |
Correct |
7193 ms |
14712 KB |
Output is correct |
35 |
Correct |
9994 ms |
17524 KB |
Output is correct |
36 |
Correct |
140 ms |
6648 KB |
Output is correct |
37 |
Correct |
280 ms |
6780 KB |
Output is correct |
38 |
Correct |
10700 ms |
18856 KB |
Output is correct |
39 |
Correct |
10829 ms |
18720 KB |
Output is correct |
40 |
Correct |
10877 ms |
18648 KB |
Output is correct |
41 |
Correct |
10743 ms |
18724 KB |
Output is correct |
42 |
Correct |
10487 ms |
18692 KB |
Output is correct |
43 |
Correct |
5251 ms |
11384 KB |
Output is correct |
44 |
Correct |
9433 ms |
17436 KB |
Output is correct |
45 |
Correct |
5530 ms |
11584 KB |
Output is correct |
46 |
Correct |
9881 ms |
17588 KB |
Output is correct |
47 |
Correct |
145 ms |
6648 KB |
Output is correct |
48 |
Correct |
147 ms |
6648 KB |
Output is correct |
49 |
Correct |
288 ms |
6776 KB |
Output is correct |
50 |
Correct |
1379 ms |
8004 KB |
Output is correct |
51 |
Correct |
6294 ms |
12292 KB |
Output is correct |
52 |
Correct |
7955 ms |
13380 KB |
Output is correct |
53 |
Correct |
8312 ms |
13644 KB |
Output is correct |
54 |
Correct |
8742 ms |
15008 KB |
Output is correct |
55 |
Correct |
8948 ms |
14712 KB |
Output is correct |
56 |
Correct |
10071 ms |
16028 KB |
Output is correct |
57 |
Correct |
10470 ms |
17412 KB |
Output is correct |
58 |
Correct |
10205 ms |
17896 KB |
Output is correct |
59 |
Correct |
10324 ms |
18752 KB |
Output is correct |
60 |
Correct |
10826 ms |
18684 KB |
Output is correct |