oj.uz

Submission #207443

# Submission time Handle Problem Language Result Execution time Memory
207443 2020-03-07T14:44:37 Z Segtree Collapse (JOI18_collapse) C++14
35 / 100
 15000 ms 72584 KB 
#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

#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);
				}
				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: In function 'vi simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++){
              ~^~~~~~~~~
collapse.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:88:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int L=0;L<T.size();L+=B){
              ~^~~~~~~~~
collapse.cpp:144: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 17 ms 6264 KB Output is correct
2 Correct 12 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 6648 KB Output is correct
6 Correct 103 ms 8952 KB Output is correct
7 Correct 12 ms 6268 KB Output is correct
8 Correct 15 ms 6352 KB Output is correct
9 Correct 41 ms 6904 KB Output is correct
10 Correct 145 ms 8440 KB Output is correct
11 Correct 216 ms 9464 KB Output is correct
12 Correct 175 ms 10744 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13928 KB Output is correct
2 Correct 60 ms 12656 KB Output is correct
3 Correct 1466 ms 13908 KB Output is correct
4 Correct 174 ms 14120 KB Output is correct
5 Correct 2267 ms 15096 KB Output is correct
6 Correct 552 ms 14124 KB Output is correct
7 Correct 7259 ms 21172 KB Output is correct
8 Correct 2928 ms 15352 KB Output is correct
9 Correct 69 ms 14052 KB Output is correct
10 Correct 131 ms 13096 KB Output is correct
11 Correct 1508 ms 14416 KB Output is correct
12 Correct 3391 ms 16256 KB Output is correct
13 Correct 6080 ms 20064 KB Output is correct
14 Correct 10821 ms 25316 KB Output is correct
15 Correct 8937 ms 25080 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13920 KB Output is correct
2 Correct 90 ms 12568 KB Output is correct
3 Correct 147 ms 13588 KB Output is correct
4 Correct 205 ms 13976 KB Output is correct
5 Correct 931 ms 14860 KB Output is correct
6 Correct 703 ms 14256 KB Output is correct
7 Correct 5320 ms 23936 KB Output is correct
8 Correct 11166 ms 44984 KB Output is correct
9 Correct 85 ms 14056 KB Output is correct
10 Correct 2796 ms 14264 KB Output is correct
11 Correct 13320 ms 72584 KB Output is correct
12 Execution timed out 15070 ms 49840 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6264 KB Output is correct
2 Correct 12 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 6648 KB Output is correct
6 Correct 103 ms 8952 KB Output is correct
7 Correct 12 ms 6268 KB Output is correct
8 Correct 15 ms 6352 KB Output is correct
9 Correct 41 ms 6904 KB Output is correct
10 Correct 145 ms 8440 KB Output is correct
11 Correct 216 ms 9464 KB Output is correct
12 Correct 175 ms 10744 KB Output is correct
13 Correct 47 ms 13928 KB Output is correct
14 Correct 60 ms 12656 KB Output is correct
15 Correct 1466 ms 13908 KB Output is correct
16 Correct 174 ms 14120 KB Output is correct
17 Correct 2267 ms 15096 KB Output is correct
18 Correct 552 ms 14124 KB Output is correct
19 Correct 7259 ms 21172 KB Output is correct
20 Correct 2928 ms 15352 KB Output is correct
21 Correct 69 ms 14052 KB Output is correct
22 Correct 131 ms 13096 KB Output is correct
23 Correct 1508 ms 14416 KB Output is correct
24 Correct 3391 ms 16256 KB Output is correct
25 Correct 6080 ms 20064 KB Output is correct
26 Correct 10821 ms 25316 KB Output is correct
27 Correct 8937 ms 25080 KB Output is correct
28 Correct 56 ms 13920 KB Output is correct
29 Correct 90 ms 12568 KB Output is correct
30 Correct 147 ms 13588 KB Output is correct
31 Correct 205 ms 13976 KB Output is correct
32 Correct 931 ms 14860 KB Output is correct
33 Correct 703 ms 14256 KB Output is correct
34 Correct 5320 ms 23936 KB Output is correct
35 Correct 11166 ms 44984 KB Output is correct
36 Correct 85 ms 14056 KB Output is correct
37 Correct 2796 ms 14264 KB Output is correct
38 Correct 13320 ms 72584 KB Output is correct
39 Execution timed out 15070 ms 49840 KB Time limit exceeded
40 Halted 0 ms 0 KB -