oj.uz

Submission #207448

# Submission time Handle Problem Language Result Execution time Memory
207448 2020-03-07T14:49:05 Z Segtree Collapse (JOI18_collapse) C++14
35 / 100
 15000 ms 72904 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].emplace_back(y);
					graph[y].emplace_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].emplace_back(y);
					graph[y].emplace_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 16 ms 6264 KB Output is correct
2 Correct 12 ms 6352 KB Output is correct
3 Correct 15 ms 6332 KB Output is correct
4 Correct 18 ms 6336 KB Output is correct
5 Correct 27 ms 6648 KB Output is correct
6 Correct 95 ms 8696 KB Output is correct
7 Correct 12 ms 6256 KB Output is correct
8 Correct 16 ms 6352 KB Output is correct
9 Correct 41 ms 6904 KB Output is correct
10 Correct 138 ms 8440 KB Output is correct
11 Correct 208 ms 9336 KB Output is correct
12 Correct 168 ms 10616 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13928 KB Output is correct
2 Correct 62 ms 12652 KB Output is correct
3 Correct 1470 ms 13896 KB Output is correct
4 Correct 194 ms 13996 KB Output is correct
5 Correct 2323 ms 15096 KB Output is correct
6 Correct 585 ms 14252 KB Output is correct
7 Correct 7281 ms 21400 KB Output is correct
8 Correct 2914 ms 15288 KB Output is correct
9 Correct 67 ms 14048 KB Output is correct
10 Correct 131 ms 13092 KB Output is correct
11 Correct 1565 ms 14556 KB Output is correct
12 Correct 3345 ms 16248 KB Output is correct
13 Correct 6138 ms 20336 KB Output is correct
14 Correct 10843 ms 25724 KB Output is correct
15 Correct 8800 ms 25432 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13928 KB Output is correct
2 Correct 83 ms 12568 KB Output is correct
3 Correct 136 ms 13612 KB Output is correct
4 Correct 195 ms 13988 KB Output is correct
5 Correct 893 ms 14960 KB Output is correct
6 Correct 663 ms 14020 KB Output is correct
7 Correct 4924 ms 24072 KB Output is correct
8 Correct 10457 ms 45660 KB Output is correct
9 Correct 79 ms 14056 KB Output is correct
10 Correct 2766 ms 14280 KB Output is correct
11 Correct 13347 ms 72904 KB Output is correct
12 Correct 14820 ms 48020 KB Output is correct
13 Correct 14076 ms 69172 KB Output is correct
14 Execution timed out 15014 ms 49376 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6264 KB Output is correct
2 Correct 12 ms 6352 KB Output is correct
3 Correct 15 ms 6332 KB Output is correct
4 Correct 18 ms 6336 KB Output is correct
5 Correct 27 ms 6648 KB Output is correct
6 Correct 95 ms 8696 KB Output is correct
7 Correct 12 ms 6256 KB Output is correct
8 Correct 16 ms 6352 KB Output is correct
9 Correct 41 ms 6904 KB Output is correct
10 Correct 138 ms 8440 KB Output is correct
11 Correct 208 ms 9336 KB Output is correct
12 Correct 168 ms 10616 KB Output is correct
13 Correct 49 ms 13928 KB Output is correct
14 Correct 62 ms 12652 KB Output is correct
15 Correct 1470 ms 13896 KB Output is correct
16 Correct 194 ms 13996 KB Output is correct
17 Correct 2323 ms 15096 KB Output is correct
18 Correct 585 ms 14252 KB Output is correct
19 Correct 7281 ms 21400 KB Output is correct
20 Correct 2914 ms 15288 KB Output is correct
21 Correct 67 ms 14048 KB Output is correct
22 Correct 131 ms 13092 KB Output is correct
23 Correct 1565 ms 14556 KB Output is correct
24 Correct 3345 ms 16248 KB Output is correct
25 Correct 6138 ms 20336 KB Output is correct
26 Correct 10843 ms 25724 KB Output is correct
27 Correct 8800 ms 25432 KB Output is correct
28 Correct 48 ms 13928 KB Output is correct
29 Correct 83 ms 12568 KB Output is correct
30 Correct 136 ms 13612 KB Output is correct
31 Correct 195 ms 13988 KB Output is correct
32 Correct 893 ms 14960 KB Output is correct
33 Correct 663 ms 14020 KB Output is correct
34 Correct 4924 ms 24072 KB Output is correct
35 Correct 10457 ms 45660 KB Output is correct
36 Correct 79 ms 14056 KB Output is correct
37 Correct 2766 ms 14280 KB Output is correct
38 Correct 13347 ms 72904 KB Output is correct
39 Correct 14820 ms 48020 KB Output is correct
40 Correct 14076 ms 69172 KB Output is correct
41 Execution timed out 15014 ms 49376 KB Time limit exceeded
42 Halted 0 ms 0 KB -