제출 #207458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207458		Segtree	Collapse (JOI18_collapse)	C++14	100 / 100	12608 ms	74136 KiB

collapse

#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);
				}
				sort(all(conc));
				conc.erase(unique(all(conc)),conc.end());
				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);
				}
				sort(all(conc));
				conc.erase(unique(all(conc)),conc.end());
				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;
}

컴파일 시 표준 에러 (stderr) 메시지

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:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++){
              ~^~~~~~~~~
collapse.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int L=0;L<T.size();L+=B){
              ~^~~~~~~~~
collapse.cpp:146:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
          ~~~~~^~~~~~~~~~~~~~~~
collapse.cpp:176:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].x>=qry.p+1;benum++){
          ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35