oj.uz

Submission #207458

# Submission time Handle Problem Language Result Execution time Memory
207458 2020-03-07T14:59:32 Z Segtree Collapse (JOI18_collapse) C++14
100 / 100
 12608 ms 74136 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
#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;
}
 
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);
				}
				vector<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.push_back(x);
					conc.push_back(y);
				}
				sort(all(conc));
				conc.erase(unique(all(conc)),conc.end());
				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);
				}
				vector<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.push_back(x);
					conc.push_back(y);
				}
				sort(all(conc));
				conc.erase(unique(all(conc)),conc.end());
				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:19:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
collapse.cpp:20:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
collapse.cpp:21: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:146:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
          ~~~~~^~~~~~~~~~~~~~~~
collapse.cpp:176: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 15 ms 6264 KB Output is correct
2 Correct 11 ms 6352 KB Output is correct
3 Correct 16 ms 6332 KB Output is correct
4 Correct 18 ms 6336 KB Output is correct
5 Correct 27 ms 6524 KB Output is correct
6 Correct 107 ms 8844 KB Output is correct
7 Correct 11 ms 6264 KB Output is correct
8 Correct 13 ms 6352 KB Output is correct
9 Correct 33 ms 6780 KB Output is correct
10 Correct 116 ms 8440 KB Output is correct
11 Correct 160 ms 9336 KB Output is correct
12 Correct 146 ms 10744 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13924 KB Output is correct
2 Correct 55 ms 12660 KB Output is correct
3 Correct 1462 ms 14152 KB Output is correct
4 Correct 155 ms 13996 KB Output is correct
5 Correct 2192 ms 15096 KB Output is correct
6 Correct 670 ms 14252 KB Output is correct
7 Correct 7495 ms 21240 KB Output is correct
8 Correct 2488 ms 15480 KB Output is correct
9 Correct 71 ms 14052 KB Output is correct
10 Correct 99 ms 13092 KB Output is correct
11 Correct 688 ms 14564 KB Output is correct
12 Correct 2773 ms 15992 KB Output is correct
13 Correct 5692 ms 20124 KB Output is correct
14 Correct 9352 ms 25648 KB Output is correct
15 Correct 8053 ms 25004 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14052 KB Output is correct
2 Correct 74 ms 12568 KB Output is correct
3 Correct 121 ms 13736 KB Output is correct
4 Correct 174 ms 13988 KB Output is correct
5 Correct 1057 ms 14960 KB Output is correct
6 Correct 861 ms 14244 KB Output is correct
7 Correct 5275 ms 24024 KB Output is correct
8 Correct 10810 ms 44600 KB Output is correct
9 Correct 72 ms 14052 KB Output is correct
10 Correct 1618 ms 14264 KB Output is correct
11 Correct 11471 ms 72420 KB Output is correct
12 Correct 12608 ms 47816 KB Output is correct
13 Correct 12253 ms 66192 KB Output is correct
14 Correct 12019 ms 47536 KB Output is correct
15 Correct 11949 ms 74136 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6264 KB Output is correct
2 Correct 11 ms 6352 KB Output is correct
3 Correct 16 ms 6332 KB Output is correct
4 Correct 18 ms 6336 KB Output is correct
5 Correct 27 ms 6524 KB Output is correct
6 Correct 107 ms 8844 KB Output is correct
7 Correct 11 ms 6264 KB Output is correct
8 Correct 13 ms 6352 KB Output is correct
9 Correct 33 ms 6780 KB Output is correct
10 Correct 116 ms 8440 KB Output is correct
11 Correct 160 ms 9336 KB Output is correct
12 Correct 146 ms 10744 KB Output is correct
13 Correct 47 ms 13924 KB Output is correct
14 Correct 55 ms 12660 KB Output is correct
15 Correct 1462 ms 14152 KB Output is correct
16 Correct 155 ms 13996 KB Output is correct
17 Correct 2192 ms 15096 KB Output is correct
18 Correct 670 ms 14252 KB Output is correct
19 Correct 7495 ms 21240 KB Output is correct
20 Correct 2488 ms 15480 KB Output is correct
21 Correct 71 ms 14052 KB Output is correct
22 Correct 99 ms 13092 KB Output is correct
23 Correct 688 ms 14564 KB Output is correct
24 Correct 2773 ms 15992 KB Output is correct
25 Correct 5692 ms 20124 KB Output is correct
26 Correct 9352 ms 25648 KB Output is correct
27 Correct 8053 ms 25004 KB Output is correct
28 Correct 45 ms 14052 KB Output is correct
29 Correct 74 ms 12568 KB Output is correct
30 Correct 121 ms 13736 KB Output is correct
31 Correct 174 ms 13988 KB Output is correct
32 Correct 1057 ms 14960 KB Output is correct
33 Correct 861 ms 14244 KB Output is correct
34 Correct 5275 ms 24024 KB Output is correct
35 Correct 10810 ms 44600 KB Output is correct
36 Correct 72 ms 14052 KB Output is correct
37 Correct 1618 ms 14264 KB Output is correct
38 Correct 11471 ms 72420 KB Output is correct
39 Correct 12608 ms 47816 KB Output is correct
40 Correct 12253 ms 66192 KB Output is correct
41 Correct 12019 ms 47536 KB Output is correct
42 Correct 11949 ms 74136 KB Output is correct
43 Correct 2096 ms 16884 KB Output is correct
44 Correct 8401 ms 28004 KB Output is correct
45 Correct 2724 ms 17784 KB Output is correct
46 Correct 10864 ms 47104 KB Output is correct
47 Correct 76 ms 14824 KB Output is correct
48 Correct 95 ms 13968 KB Output is correct
49 Correct 1303 ms 15448 KB Output is correct
50 Correct 1968 ms 15952 KB Output is correct
51 Correct 3170 ms 19032 KB Output is correct
52 Correct 5801 ms 22120 KB Output is correct
53 Correct 5547 ms 40704 KB Output is correct
54 Correct 6995 ms 24344 KB Output is correct
55 Correct 6801 ms 39904 KB Output is correct
56 Correct 8487 ms 49164 KB Output is correct
57 Correct 11144 ms 64384 KB Output is correct
58 Correct 10862 ms 36700 KB Output is correct
59 Correct 11455 ms 62368 KB Output is correct
60 Correct 12160 ms 50216 KB Output is correct