oj.uz

Submission #207436

# Submission time Handle Problem Language Result Execution time Memory
207436 2020-03-07T14:19:26 Z Segtree Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 35692 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 200

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);
		
		{//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> swork=s;
				for(int i=L;i<=qry.w;i++){
					ll has=(ll)X[i]*Nmax+Y[i];
					if(swork.count(has))swork.erase(has);
					else swork.insert(has);
				}
				unordered_set<ll> conc;
				for(auto e:swork){
					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> swork=s;
				for(int i=L;i<=qry.w;i++){
					ll has=(ll)X[i]*Nmax+Y[i];
					if(swork.count(has))swork.erase(has);
					else swork.insert(has);
				}
				unordered_set<ll> conc;
				for(auto e:swork){
					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: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:138:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
          ~~~~~^~~~~~~~~~~~~~~~
collapse.cpp:172: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 47 ms 6264 KB Output is correct
2 Correct 14 ms 6356 KB Output is correct
3 Correct 30 ms 6332 KB Output is correct
4 Correct 44 ms 6336 KB Output is correct
5 Correct 96 ms 6136 KB Output is correct
6 Correct 165 ms 6908 KB Output is correct
7 Correct 14 ms 6268 KB Output is correct
8 Correct 21 ms 6352 KB Output is correct
9 Correct 111 ms 6392 KB Output is correct
10 Correct 197 ms 6648 KB Output is correct
11 Correct 245 ms 7576 KB Output is correct
12 Correct 216 ms 8112 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 13928 KB Output is correct
2 Correct 144 ms 12656 KB Output is correct
3 Correct 3453 ms 13324 KB Output is correct
4 Correct 694 ms 14116 KB Output is correct
5 Correct 4167 ms 13468 KB Output is correct
6 Correct 2513 ms 12564 KB Output is correct
7 Correct 11563 ms 20960 KB Output is correct
8 Correct 5047 ms 13820 KB Output is correct
9 Correct 98 ms 14056 KB Output is correct
10 Correct 285 ms 13096 KB Output is correct
11 Correct 3232 ms 12988 KB Output is correct
12 Correct 5238 ms 15060 KB Output is correct
13 Correct 9547 ms 18168 KB Output is correct
14 Execution timed out 15084 ms 23212 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13924 KB Output is correct
2 Correct 177 ms 12664 KB Output is correct
3 Correct 352 ms 13612 KB Output is correct
4 Correct 682 ms 13988 KB Output is correct
5 Correct 2533 ms 13676 KB Output is correct
6 Correct 2577 ms 12432 KB Output is correct
7 Correct 8137 ms 21256 KB Output is correct
8 Execution timed out 15092 ms 35692 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6264 KB Output is correct
2 Correct 14 ms 6356 KB Output is correct
3 Correct 30 ms 6332 KB Output is correct
4 Correct 44 ms 6336 KB Output is correct
5 Correct 96 ms 6136 KB Output is correct
6 Correct 165 ms 6908 KB Output is correct
7 Correct 14 ms 6268 KB Output is correct
8 Correct 21 ms 6352 KB Output is correct
9 Correct 111 ms 6392 KB Output is correct
10 Correct 197 ms 6648 KB Output is correct
11 Correct 245 ms 7576 KB Output is correct
12 Correct 216 ms 8112 KB Output is correct
13 Correct 79 ms 13928 KB Output is correct
14 Correct 144 ms 12656 KB Output is correct
15 Correct 3453 ms 13324 KB Output is correct
16 Correct 694 ms 14116 KB Output is correct
17 Correct 4167 ms 13468 KB Output is correct
18 Correct 2513 ms 12564 KB Output is correct
19 Correct 11563 ms 20960 KB Output is correct
20 Correct 5047 ms 13820 KB Output is correct
21 Correct 98 ms 14056 KB Output is correct
22 Correct 285 ms 13096 KB Output is correct
23 Correct 3232 ms 12988 KB Output is correct
24 Correct 5238 ms 15060 KB Output is correct
25 Correct 9547 ms 18168 KB Output is correct
26 Execution timed out 15084 ms 23212 KB Time limit exceeded
27 Halted 0 ms 0 KB -