Submission #207153

#	Time	Username	Problem	Language	Result	Execution time	Memory
207153		Segtree	Collapse (JOI18_collapse)	C++14	30 / 100	5074 ms	23428 KiB

collapse

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
#include"collapse.h"
using namespace std;
typedef long long ll;
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
//namespace solver2{
	#define B 300
	typedef struct qry{
		ll p,id;
	}qry;
	vector<qry> Query[100010];
	typedef struct edge{
		ll t,x,y;
		ll hash(){return x*100010+y;}
	}edge;
	edge Edge[100010];
	
	vi FANS;
	int component[100010];
	vector<ll> g[100010];
	bool vis[100010];
	void dfs(ll x,ll co){
		if(vis[x])return;
		vis[x]=1;
		if(co>=0)component[x]=co;
		for(auto y:g[x])dfs(y,co);
	}
	
	vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){
		rep(i,100010){
			g[i].clear();
			Query[i].clear();
		}
		int C=T.size(),Q=W.size();
		for(int i=0;i<C;i++){
			if(X[i]>Y[i])swap(X[i],Y[i]);
			if(X[i]<=P[0]&&P[0]+1<=Y[i])X[i]=Y[i]=0;
			Edge[i]=(edge){T[i],X[i],Y[i]};
		}
		for(int i=0;i<Q;i++){
			Query[W[i]].push_back((qry){P[i],i});
		}
		FANS.resize(W.size());
		for(int L=0;L<C;L+=B){
			int R=min(L+B,C);
			unordered_set<ll> BASE,S;
			//BASE:クエリのバケット内でも常に存在する辺のハッシュの集合
			//S:クエリのバケットのはじめに存在する、BASEに含まれない辺の集合
			//  後にそれぞれのクエリを処理する時に変化させる
			for(int i=0;i<L;i++){
				ll has=Edge[i].hash();
				if(BASE.count(has))BASE.erase(has);
				else BASE.insert(has);
			}
			//BASEを求める
			for(int i=L;i<R;i++){
				ll has=Edge[i].hash();
				if(BASE.count(has)){
					BASE.erase(has);
					S.insert(has);
				}
			}
			//SをBASEを使って求める
			for(int i=0;i<N;i++){g[i].clear();vis[i]=0;}
			for(auto e:BASE){ll x=e/100010,y=e%100010;g[x].push_back(y);g[y].push_back(x);}
			ll cc=0;
			//cc:BASEのグラフの連結成分数
			for(int i=0;i<N;i++){
				if(vis[i])continue;
				dfs(i,cc); cc++;
			}
			//BASEのグラフの連結成分を調べる
			unordered_set<ll> conc;
			//conc:クエリバケット内の辺の両端が属することのある連結成分の番号の集合
			//     このサイズは高々B個で、dfsで各クエリでの連結成分数を求めるのに使う
			//     それ以外のcc-conc個の成分は各クエリでも変わらず存在するので、加算すればok
			for(int i=L;i<R;i++){
				conc.insert(component[Edge[i].x]);
				conc.insert(component[Edge[i].y]);
			}
			for(int i=L;i<R;i++){
				ll has=Edge[i].hash();
				if(S.count(has))S.erase(has);
				else S.insert(has);
				//この工事の後では、Sにハッシュ値を持つ辺の集合が存在する
				for(auto t:conc){
					vis[t]=0;
					g[t].clear();
				}
				for(auto e:S){
					ll x=e/100010,y=e%100010;
					x=component[x],y=component[y];
					if(x!=y){
						g[x].push_back(y);
						g[y].push_back(x);
					}
				}
				ll cnt=0;
				for(auto t:conc){
					if(vis[t])continue;
					dfs(t,-1);
					cnt++;
				}
				//concの頂点とSの辺のグラフの連結成分数cntを調べる
				//cerr<<__LINE__<<cc<<" "<<conc.size()<<" "<<cnt<<endl;
				for(qry q:Query[i]){
					FANS[q.id]=cc-conc.size()+cnt;
				}
				//i番目の工事が終わったあとの連結成分数を答える
			}
		}
		return FANS;
	}
//};
/*int main(){
	ll N,C,Q;
	cin>>N>>C>>Q;
	vi T(C),X(C),Y(C),W(Q),P(Q);
	rep(i,C){
		cin>>T[i]>>X[i]>>Y[i];
	}
	rep(i,Q){
		cin>>W[i]>>P[i];
	}
	vi ANS1=solver1::simulateCollapse(N,T,X,Y,W,P);
	for(auto t:ANS1)cout<<t<<endl;
}*/

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