oj.uz

Submission #207439

# Submission time Handle Problem Language Result Execution time Memory
207439 2020-03-07T14:36:38 Z Segtree Collapse (JOI18_collapse) C++14
5 / 100
 10545 ms 45232 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#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;
}

/*unordered_map<ll,ll> mas[Nmax];
ll edgehash[Nmax];
class uset{
	public:
	bool th[Nmax];
	vector<ll> c;
	void init(){
		while(c.size()>0){
			th[c.back()]=0;
			c.pop_back();
		}
	}
	void add(int x){
		if(th[x]==0)c.push_back(x);
	}
};*/

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]);
		//if(mas[X[i]].count(Y[i]))edgehash[i]=mas[X[i]][Y[i]];
		//else edgehash[i]=i,mas[X[i]][Y[i]]=i;
	}
	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=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=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);
				}
				unordered_set<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.insert(x);
					conc.insert(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);
				}
				unordered_set<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.insert(x);
					conc.insert(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:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
collapse.cpp:19:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
collapse.cpp:20: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:98:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++){
              ~^~~~~~~~~
collapse.cpp:104:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int L=0;L<T.size();L+=B){
              ~^~~~~~~~~
collapse.cpp:165:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
          ~~~~~^~~~~~~~~~~~~~~~
collapse.cpp:193: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6136 KB Output is correct
2 Correct 11 ms 6352 KB Output is correct
3 Correct 14 ms 6332 KB Output is correct
4 Correct 17 ms 6336 KB Output is correct
5 Correct 28 ms 6520 KB Output is correct
6 Correct 99 ms 8700 KB Output is correct
7 Correct 12 ms 6264 KB Output is correct
8 Correct 14 ms 6348 KB Output is correct
9 Correct 41 ms 6904 KB Output is correct
10 Correct 135 ms 8492 KB Output is correct
11 Correct 205 ms 9352 KB Output is correct
12 Correct 169 ms 10616 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13928 KB Output is correct
2 Correct 59 ms 12656 KB Output is correct
3 Correct 1418 ms 13916 KB Output is correct
4 Correct 171 ms 13996 KB Output is correct
5 Correct 2248 ms 15096 KB Output is correct
6 Correct 535 ms 14124 KB Output is correct
7 Correct 7169 ms 21360 KB Output is correct
8 Correct 2903 ms 15528 KB Output is correct
9 Correct 69 ms 14052 KB Output is correct
10 Correct 129 ms 13096 KB Output is correct
11 Incorrect 1736 ms 15188 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13928 KB Output is correct
2 Correct 87 ms 12568 KB Output is correct
3 Correct 139 ms 13740 KB Output is correct
4 Correct 196 ms 13996 KB Output is correct
5 Correct 868 ms 15088 KB Output is correct
6 Correct 672 ms 14120 KB Output is correct
7 Correct 4941 ms 24160 KB Output is correct
8 Correct 10545 ms 45232 KB Output is correct
9 Correct 83 ms 14052 KB Output is correct
10 Incorrect 2740 ms 14388 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6136 KB Output is correct
2 Correct 11 ms 6352 KB Output is correct
3 Correct 14 ms 6332 KB Output is correct
4 Correct 17 ms 6336 KB Output is correct
5 Correct 28 ms 6520 KB Output is correct
6 Correct 99 ms 8700 KB Output is correct
7 Correct 12 ms 6264 KB Output is correct
8 Correct 14 ms 6348 KB Output is correct
9 Correct 41 ms 6904 KB Output is correct
10 Correct 135 ms 8492 KB Output is correct
11 Correct 205 ms 9352 KB Output is correct
12 Correct 169 ms 10616 KB Output is correct
13 Correct 47 ms 13928 KB Output is correct
14 Correct 59 ms 12656 KB Output is correct
15 Correct 1418 ms 13916 KB Output is correct
16 Correct 171 ms 13996 KB Output is correct
17 Correct 2248 ms 15096 KB Output is correct
18 Correct 535 ms 14124 KB Output is correct
19 Correct 7169 ms 21360 KB Output is correct
20 Correct 2903 ms 15528 KB Output is correct
21 Correct 69 ms 14052 KB Output is correct
22 Correct 129 ms 13096 KB Output is correct
23 Incorrect 1736 ms 15188 KB Output isn't correct
24 Halted 0 ms 0 KB -