oj.uz

Submission #207434

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

#define Nmax 100010
#define B 600

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: In function 'vi simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++){
              ~^~~~~~~~~
collapse.cpp:83:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:87:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int L=0;L<T.size();L+=B){
              ~^~~~~~~~~
collapse.cpp:135:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
          ~~~~~^~~~~~~~~~~~~~~~
collapse.cpp:169: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 107 ms 6264 KB Output is correct
2 Correct 14 ms 6352 KB Output is correct
3 Correct 30 ms 6332 KB Output is correct
4 Correct 41 ms 6336 KB Output is correct
5 Correct 222 ms 6268 KB Output is correct
6 Correct 407 ms 7160 KB Output is correct
7 Correct 14 ms 6264 KB Output is correct
8 Correct 25 ms 6356 KB Output is correct
9 Correct 237 ms 6392 KB Output is correct
10 Correct 492 ms 6904 KB Output is correct
11 Correct 621 ms 8100 KB Output is correct
12 Correct 576 ms 10664 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 13928 KB Output is correct
2 Correct 136 ms 12660 KB Output is correct
3 Correct 5092 ms 13432 KB Output is correct
4 Correct 666 ms 14120 KB Output is correct
5 Correct 6930 ms 13432 KB Output is correct
6 Correct 7861 ms 12900 KB Output is correct
7 Correct 11144 ms 20948 KB Output is correct
8 Correct 8470 ms 13688 KB Output is correct
9 Correct 97 ms 14056 KB Output is correct
10 Correct 266 ms 13092 KB Output is correct
11 Correct 9110 ms 14892 KB Output is correct
12 Correct 8682 ms 14932 KB Output is correct
13 Correct 14139 ms 18056 KB Output is correct
14 Execution timed out 15090 ms 23200 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 13924 KB Output is correct
2 Correct 167 ms 12564 KB Output is correct
3 Correct 352 ms 13612 KB Output is correct
4 Correct 705 ms 13992 KB Output is correct
5 Correct 7582 ms 13552 KB Output is correct
6 Correct 7720 ms 13120 KB Output is correct
7 Correct 10278 ms 24384 KB Output is correct
8 Correct 14126 ms 63760 KB Output is correct
9 Correct 104 ms 14052 KB Output is correct
10 Correct 12179 ms 13688 KB Output is correct
11 Execution timed out 15103 ms 103664 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 6264 KB Output is correct
2 Correct 14 ms 6352 KB Output is correct
3 Correct 30 ms 6332 KB Output is correct
4 Correct 41 ms 6336 KB Output is correct
5 Correct 222 ms 6268 KB Output is correct
6 Correct 407 ms 7160 KB Output is correct
7 Correct 14 ms 6264 KB Output is correct
8 Correct 25 ms 6356 KB Output is correct
9 Correct 237 ms 6392 KB Output is correct
10 Correct 492 ms 6904 KB Output is correct
11 Correct 621 ms 8100 KB Output is correct
12 Correct 576 ms 10664 KB Output is correct
13 Correct 74 ms 13928 KB Output is correct
14 Correct 136 ms 12660 KB Output is correct
15 Correct 5092 ms 13432 KB Output is correct
16 Correct 666 ms 14120 KB Output is correct
17 Correct 6930 ms 13432 KB Output is correct
18 Correct 7861 ms 12900 KB Output is correct
19 Correct 11144 ms 20948 KB Output is correct
20 Correct 8470 ms 13688 KB Output is correct
21 Correct 97 ms 14056 KB Output is correct
22 Correct 266 ms 13092 KB Output is correct
23 Correct 9110 ms 14892 KB Output is correct
24 Correct 8682 ms 14932 KB Output is correct
25 Correct 14139 ms 18056 KB Output is correct
26 Execution timed out 15090 ms 23200 KB Time limit exceeded
27 Halted 0 ms 0 KB -