Submission #596883

#	Time	Username	Problem	Language	Result	Execution time	Memory
596883		kshitij_sodani	Split the Attractions (IOI19_split)	C++14	100 / 100	231 ms	26284 KiB

split

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'

#include "split.h"

int par5[100001];
int par2[100001];
vector<int> adj[100001];
vector<int> adj2[100001];
vector<int> adj3[100001];

int find(int no){
	if(par5[no]==no){
		return no;
	}
	par5[no]=find(par5[no]);
	return par5[no];
}
int nn;
int s[100001];
void dfs(int no,int par=-1){
	s[no]=1;
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
			s[no]+=s[j];
		}
	}
}
int dfs2(int no,int par=-1){
	for(auto j:adj[no]){
		if(j!=par){
			if(s[j]>(nn/2)){
				return dfs2(j,no);
			}
		}
	}
	return no;
}
void dfs3(int no,int par=-1,int xx=-1){
	par2[no]=xx;
	s[no]=1;
	for(auto j:adj[no]){
		if(j!=par){
			if(par==-1){
				dfs3(j,no,j);
			}
			else{
				dfs3(j,no,xx);
			}
			s[no]+=s[j];
		}
	}
}
int vis[100001];
int su=0;
int ac=0;
vector<int> cur;
void dfs4(int no){
	vis[no]=1;
	if(su<ac){
		su+=s[no];
		cur.pb(no);
	}
	for(auto j:adj2[no]){
		if(vis[j]==0){
			dfs4(j);
		}
	}
}
void dfs5(int no){
	vis[no]=1;
	if(cur.size()<ac){
		cur.pb(no);
	}
	for(auto j:adj3[no]){
		if(vis[j]==0){
			dfs5(j);
		}
	}
}
vector<int> find_split(int n, int aa, int bb, int cc, vector<int> p, vector<int> q) {
	nn=n;

	vector<pair<int,int>> ss;
	ss.pb({aa,1});
	ss.pb({bb,2});
	ss.pb({cc,3});

	sort(ss.begin(),ss.end());
	ac=ss[0].a;
	aa=ss[0].a;
	bb=ss[1].a;
	cc=ss[2].a;

	for(int i=0;i<n;i++){
		par5[i]=i;
	}
	vector<pair<int,int>> tt;
	for(int i=0;i<p.size();i++){
		int x=find(p[i]);
		int y=find(q[i]);
		if(x!=y){
			par5[x]=y;
			adj[p[i]].pb(q[i]);
			adj[q[i]].pb(p[i]);
		}
		else{
			tt.pb({p[i],q[i]});
		}
	}
	dfs(0);
	int cen=dfs2(0);
	dfs3(cen);
	
	for(auto j:tt){
		int x=par2[j.a];
		int y=par2[j.b];
		if(x==-1 or y==-1 or x==y){
			continue;
		}
		adj2[x].pb(y);
		adj2[y].pb(x);
	}
//	cout<<cen<<"::"<<endl;
	for(auto j:adj[cen]){
		if(vis[j]==0){
			cur.clear();
			su=0;
			dfs4(j);
			set<int> xx;
			for(auto i:cur){
				xx.insert(i);
			}
			if(su>=aa and su<=(n/2)){
				/*for(auto i:xx){
					cout<<i<<":";
				}
				cout<<endl;*/
				for(int i=0;i<n;i++){
					vis[i]=0;
				}
				for(int i=0;i<p.size();i++){
					if(xx.find(par2[p[i]])!=xx.end()){
						if(xx.find(par2[q[i]])!=xx.end()){
							adj3[p[i]].pb(q[i]);
							adj3[q[i]].pb(p[i]);
						}
					}
				}
				ac=aa;
				cur.clear();
				dfs5(j);
				vector<int> ha=cur;
				

				for(int i=0;i<n;i++){
					adj3[i].clear();
				}
				
				for(int i=0;i<p.size();i++){
					if(xx.find(par2[p[i]])==xx.end()){
						if(xx.find(par2[q[i]])==xx.end()){
							adj3[p[i]].pb(q[i]);
							adj3[q[i]].pb(p[i]);
						}
					}
				}
				ac=bb;
				cur.clear();
				for(int i=0;i<n;i++){
					vis[i]=0;
				}
				dfs5(cen);
				vector<int> hb=cur;
				
				vector<int> ans;
				for(int i=0;i<n;i++){
					ans.pb(3);
				}
				for(auto j:ha){
					ans[j]=1;
				}
				for(auto j:hb){
					ans[j]=2;
				}
				map<int,int> mm;
				mm[1]=ss[0].b;
				mm[2]=ss[1].b;
				mm[3]=ss[2].b;
				for(int i=0;i<n;i++){
					ans[i]=mm[ans[i]];
				}
				return ans;
			}
			else if(su>=aa){
				for(int i=0;i<n;i++){
					vis[i]=0;
				}
				for(int i=0;i<p.size();i++){
					if(xx.find(par2[p[i]])!=xx.end()){
						if(xx.find(par2[q[i]])!=xx.end()){
							adj3[p[i]].pb(q[i]);
							adj3[q[i]].pb(p[i]);
						}
					}
				}
				ac=bb;
				cur.clear();
				dfs5(j);
				vector<int> ha=cur;

				for(int i=0;i<n;i++){
					adj3[i].clear();
				}
				
				for(int i=0;i<p.size();i++){
					if(xx.find(par2[p[i]])==xx.end()){
						if(xx.find(par2[q[i]])==xx.end()){
							adj3[p[i]].pb(q[i]);
							adj3[q[i]].pb(p[i]);
						}
					}
				}
				ac=aa;
				cur.clear();
				for(int i=0;i<n;i++){
					vis[i]=0;
				}
				dfs5(cen);
				vector<int> hb=cur;
				vector<int> ans;
				for(int i=0;i<n;i++){
					ans.pb(3);
				}

				for(auto j:ha){
					ans[j]=2;
				}
				for(auto j:hb){
					ans[j]=1;
				}
				map<int,int> mm;
				mm[1]=ss[0].b;
				mm[2]=ss[1].b;
				mm[3]=ss[2].b;
				for(int i=0;i<n;i++){
					ans[i]=mm[ans[i]];
				}
				return ans;

			}
			else{
				continue;
			}
		}
	}

	vector<int> res;
	for(int i=0;i<n;i++){
		res.pb(0);
	}
	return res;

}

Compilation message (stderr)

split.cpp: In function 'void dfs5(int)':
split.cpp:78:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |  if(cur.size()<ac){
      |     ~~~~~~~~~~^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:148:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for(int i=0;i<p.size();i++){
      |                 ~^~~~~~~~~
split.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for(int i=0;i<p.size();i++){
      |                 ~^~~~~~~~~
split.cpp:205:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |     for(int i=0;i<p.size();i++){
      |                 ~^~~~~~~~~
split.cpp:222:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |     for(int i=0;i<p.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36