Submission #1023530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023530		sopaconk	Split the Attractions (IOI19_split)	C++17	0 / 100	1787 ms	1048576 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
using lli=long long int;
#define pb push_back
#define deb(x) cout<<#x<<": "<<x<<endl;



mt19937_64 rnd(807);


vector<int> find_split(int n, int a1, int b1, int c1, vector<int> p, vector<int> q) {
	int m=p.size();

		vector<pair<int,int>> ayuda;
		ayuda.pb({a1,1});
		ayuda.pb({b1,2});
		ayuda.pb({c1,3});
		sort(ayuda.begin(), ayuda.end());
		int a=ayuda[0].first;
		int b=ayuda[1].first;
		int c=ayuda[2].first;
	vector<vector<int>> adj (n);

	for(int i=0;i<m; ++i){
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	vector<vector<int>> dis (n, vector<int> (n,-1));
	for(int i=0; i<n; ++i){
		queue<pair<int,int>> q;
		dis[i][i]=0;
		q.push({i,0});
		while(!q.empty()){
			int x=q.front().first;
			int d=q.front().second;
			q.pop();
			for(int y: adj[x]){
				if(dis[i][y]==-1){
					dis[i][y]=d+1;
					q.push({y,d+1});
				}
			}
		}
	}
	vector<int> ans;
	for(int i=0; i<n; ++i){
//		deb(i);
		
		vector<int> aux2;
		
		int maxi=0;
	//	int ind=i;
		for(int j=0; j<n; ++j){
			if(dis[i][j]>=maxi){
				maxi=dis[i][j];
	//			ind=j;
			}
		}
		vector<int> pos;
		for(int j=0; j<n; ++j){
			if(dis[i][j]==maxi){
				pos.pb(j);
			}
		}
		int cnt=5;
		vector<bool> check (pos.size(), false);
		while(cnt>0){
			int bb=b;
		int aa=a;
		vector<int> aux(n,0);
		vector<bool> vis(n,0);
		
		vis[i]=true;
		aux[i]=2;
		cnt--;
		int ind=pos[rnd()%pos.size()];
		vis[ind]=true;
		aux[ind]=1;
//		deb(ind);
		bb--;
		aa--;
		priority_queue<pair<int,int>> pq1;
		priority_queue<pair<int,int>> pq2;
		for(int x:adj[i]){
//			deb(x);
			if(!vis[x]){
				pq1.push({dis[ind][x], x});
			}
		}
//		deb("_----");
		for(int x: adj[ind]){
//			deb(x);
			if(!vis[x]){
				pq2.push({dis[i][x], x});
			}
		}
	//	deb("------");
		while(bb>0 && !pq1.empty()){
			int x=pq1.top().second;
//			deb(x);
			pq1.pop();
			while(vis[x] && !pq1.empty()){
				x=pq1.top().second;
//				deb(x);
				pq1.pop();
			}
		
	//		deb("------------------");
			if(vis[x]){
				break;
			}
			aux[x]=2;
			vis[x]=true;
			for(int y:adj[x]){
				if(!vis[y]){
				pq1.push({dis[ind][y], y});
				}	
			}
			bb--;
			if(aa>0){
				if(pq2.empty()) break;
				x=pq2.top().second;
	//			deb(x);
				pq2.pop();
				while(vis[x] && !pq2.empty()){
					x=pq2.top().second;
	//				deb(x);
					pq2.pop();
				}
		//		deb("-----------");
				if(vis[x]) break;
				vis[x]=true;
				aux[x]=1;
				for(int y:adj[x]){
					if(!vis[y]){
					pq2.push({dis[i][y], y});
					}	
				}
				aa--;
			}
		}
		if(aa==0 && bb==0){
			aux2=aux;
			break;
		}
		}
		if(aux2.size()!=0){
			ans=aux2;
			break;
		}
	}
	if(ans.size()==0){
		vector<int> aux (n,0);
		return aux;
	}
	for(int i=0; i<n; ++i){
		ans[i]=ayuda[(ans[i]+2)%3].second;
	}
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:23:7: warning: unused variable 'c' [-Wunused-variable]
   23 |   int c=ayuda[2].first;
      |       ^

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