oj.uz

Submission #207153

# Submission time Handle Problem Language Result Execution time Memory
207153 2020-03-06T15:09:29 Z Segtree Collapse (JOI18_collapse) C++14
30 / 100
 5074 ms 23428 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5624 KB Output is correct
2 Incorrect 11 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8924 KB Output is correct
2 Correct 40 ms 9372 KB Output is correct
3 Correct 1215 ms 15272 KB Output is correct
4 Correct 40 ms 10488 KB Output is correct
5 Correct 1263 ms 16944 KB Output is correct
6 Correct 58 ms 11360 KB Output is correct
7 Correct 2179 ms 20476 KB Output is correct
8 Correct 1818 ms 17900 KB Output is correct
9 Correct 55 ms 10216 KB Output is correct
10 Correct 45 ms 10616 KB Output is correct
11 Correct 61 ms 11768 KB Output is correct
12 Correct 2193 ms 20396 KB Output is correct
13 Correct 2844 ms 21652 KB Output is correct
14 Correct 5074 ms 23364 KB Output is correct
15 Correct 3755 ms 23428 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8936 KB Output is correct
2 Incorrect 39 ms 9060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5624 KB Output is correct
2 Incorrect 11 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -