#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
#define Nmax 100010
#define B 300
namespace uf{
ll p[Nmax],uni;
void init(){
rep(i,Nmax)p[i]=i;
uni=0;
}
ll par(ll x){
return p[x]=(x==p[x]?x:par(p[x]));
}
void unite(ll a,ll b){
a=par(a),b=par(b);
if(a!=b){
p[a]=b;
uni++;
}
}
};
typedef struct query{
ll w,p,id;
}query;
bool comp_w(const query&a,const query&b){
return a.w<b.w;
}
bool comp_p(const query&a,const query&b){
return a.p<b.p;
}
vector<query> qrys[Nmax];
bool vis[Nmax];
vector<ll> graph[Nmax];
ll cmp[Nmax];
void dfs(ll x,ll cmps){
if(vis[x])return;
vis[x]=1;
if(cmps>=0)cmp[x]=cmps;
for(auto y:graph[x])dfs(y,cmps);
}
typedef struct edge{
ll x,y;
}edge;
bool edge_comp_x(const edge&a,const edge&b){
return a.x>b.x;
}
bool edge_comp_y(const edge&a,const edge&b){
return a.y<b.y;
}
vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){
for(int i=0;i<Nmax;i++){
qrys[i].clear();
graph[i].clear();
}
for(int i=0;i<T.size();i++){
if(X[i]>Y[i])swap(X[i],Y[i]);
//subtask2限定
//if(X[i]<=P[0]&&P[0]+1<=Y[i])X[i]=Y[i]=0;
}
vi fans(W.size());
for(int i=0;i<W.size();i++){
qrys[W[i]].push_back((query){W[i],P[i],i});
fans[i]=0;
}
for(int L=0;L<T.size();L+=B){
int R=min(L+B,(int)T.size());
vector<edge> baseedge;
//{//base,s,baseedgeを用意
unordered_set<ll> base,s;
for(int i=0;i<L;i++){
ll has=(ll)X[i]*Nmax+Y[i];
if(base.count(has))base.erase(has);
else base.insert(has);
}
for(int i=L;i<R;i++){
ll has=(ll)X[i]*Nmax+Y[i];
if(base.count(has)){
base.erase(has);
s.insert(has);
}
}
for(auto e:base){
ll x=e/Nmax,y=e%Nmax;
baseedge.push_back((edge){x,y});
}
/*for(int i=0;i<N;i++){vis[i]=0;graph[i].clear();}
for(auto e:base){
ll x=e/Nmax,y=e%Nmax;
graph[x].push_back(y);
graph[y].push_back(x);
}
ll basecmp=0;
for(int i=0;i<N;i++)if(vis[i]==0){
dfs(i,basecmp++);
}*/
for(int i=0;i<N;i++){vis[i]=0;graph[i].clear();}
//}
vector<query> Q;
for(int i=L;i<R;i++){
for(query tmp:qrys[i]){
Q.push_back(tmp);
}
}
sort(all(Q),comp_p);
unordered_set<ll> swork[B];
for(int i=L;i<R;i++){
ll has=(ll)X[i]*Nmax+Y[i];
if(s.count(has))s.erase(has);
else s.insert(has);
swork[i-L]=s;
}
{//pの昇順に、左側の成分数を求める。base辺はyの昇順にソート
uf::init();
ll benum=0;
sort(all(baseedge),edge_comp_y);
for(query qry:Q){
for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
uf::unite(baseedge[benum].x,baseedge[benum].y);
}
vector<ll> conc;
for(auto e:swork[qry.w-L]){
ll x=e/Nmax,y=e%Nmax;
if(qry.p+1<=y)continue;
x=uf::par(x),y=uf::par(y);
graph[x].push_back(y);
graph[y].push_back(x);
conc.push_back(x);
conc.push_back(y);
}
ll scmp=0;
for(auto i:conc)if(vis[i]==0){
dfs(i,-1);
scmp++;
}
for(auto i:conc){vis[i]=0;graph[i].clear();}
fans[qry.id]+=(qry.p-uf::uni)-conc.size()+scmp;
}
}
reverse(all(Q));
{//pの降順に、右側の成分数を求める。base辺はxの降順にソート
uf::init();
ll benum=0;
sort(all(baseedge),edge_comp_x);
for(query qry:Q){
for(;benum<baseedge.size()&&baseedge[benum].x>=qry.p+1;benum++){
uf::unite(baseedge[benum].x,baseedge[benum].y);
}
vector<ll> conc;
for(auto e:swork[qry.w-L]){
ll x=e/Nmax,y=e%Nmax;
if(x<=qry.p)continue;
x=uf::par(x),y=uf::par(y);
graph[x].push_back(y);
graph[y].push_back(x);
conc.push_back(x);
conc.push_back(y);
}
ll scmp=0;
for(auto i:conc)if(vis[i]==0){
dfs(i,-1);
scmp++;
}
for(auto i:conc){vis[i]=0;graph[i].clear();}
fans[qry.id]+=(N-qry.p-uf::uni)-conc.size()+scmp;
}
}
}
return fans;
}
Compilation message
collapse.cpp:19:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
#pragma gcc optimize("O3")
collapse.cpp:20:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
#pragma gcc optimize("unroll-loops")
collapse.cpp:21:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
#pragma gcc target("avx2,see4")
collapse.cpp: In function 'vi simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<T.size();i++){
~^~~~~~~~~
collapse.cpp:87:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<W.size();i++){
~^~~~~~~~~
collapse.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int L=0;L<T.size();L+=B){
~^~~~~~~~~
collapse.cpp:147:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
~~~~~^~~~~~~~~~~~~~~~
collapse.cpp:175:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;benum<baseedge.size()&&baseedge[benum].x>=qry.p+1;benum++){
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
6264 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
6352 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
13928 KB |
Output is correct |
| 2 |
Correct |
58 ms |
12664 KB |
Output is correct |
| 3 |
Incorrect |
1436 ms |
14000 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
13924 KB |
Output is correct |
| 2 |
Incorrect |
73 ms |
12568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
6264 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
6352 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
