Submission #298372

#	Time	Username	Problem	Language	Result	Execution time	Memory
298372		Rayaabualjamal	Split the Attractions (IOI19_split)	C++14	18 / 100	293 ms	14024 KiB

split

#include "split.h"
#include <cassert>
 
#include <iostream> 
#include <set> 
#include <iterator>
#include <cmath>
#include <algorithm>
#include <vector> 
#include <map> 
#include <cstdio>
#define rep(i,a,b) for(int i = a; i<b; i++)
#define per(i,a,b) for(int i = a; i>=b; i--)
#define pb push_back
#define se second
#define mp make_pair
#define fi first
using namespace std;
vector <int> ans;
vector < vector <int> > ve;
vector < pair <int, int> > ce;
int dfs(int v){
	if(ans[v] == 4|| ans[v]==ce[1].se)return 0;
	int cnt = 1;
	ans[v]=4;
	for(int l:ve[v]){
		if(ans[l]!=4&&ans[l]!=ce[1].se){
			cnt+=dfs(l);
		}
	}
	return cnt;
}
void bfs2(int v){
	int h = ce[0].first;
	int d = ce[0].se;
	set<int> s;
	s.insert(v);
	ans[v] = d;
	h--;
	while(!s.empty()&&h){
		int best = *s.begin();
		s.erase(s.begin());
		for(int k:ve[best]){
			if(h&&ans[k]==4){
				ans[k]=d;
				h--;
				s.insert(k);
			}
		}
	}
}
void fix(){
	rep(i,0,ans.size()){
		if(ans[i]==4){
			ans[i]=ce[2].se;
		}
	}
}
bool bfs(int v){
	int h = ce[1].first;
	int d = ce[1].se;
	set< pair <int, int> > s;
	s.insert(mp(ve[v].size(),v));
	//cout << v << ":" << endl;
	while(!s.empty()&&h){
		int best = (*s.begin()).se;
		//cout << best << endl;
		s.erase(s.begin());
		if(ans[best]==d)continue;
		ans[best]=d;
		h--;
		if(h==0)break;
		for(int k:ve[best]){
			if(ans[k]!=d){
				s.insert(mp(ve[k].size(),k));
			}
		}
	}
	//cout << endl;
	rep(i,0,ans.size()){
		if(ans[i]!=d){
			int count  = dfs(i);
			//cout << v << " " << count << " " << i << endl;
			if(count >=ce[0].first){
				bfs2(i);
				fix();
				//cout << "here" << endl;
				return true;
			}
		}
	}
	return false;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	ce.pb(make_pair(a, 1));
	ce.pb(make_pair(b, 2));
	ce.pb(make_pair(c, 3));
	sort(ce.begin(), ce.end());
	ve.resize(n+1);
	rep(i,0,p.size()){
		ve[p[i]].pb(q[i]);
		ve[q[i]].pb(p[i]);
	}
	bool f = 0;
	rep(i,0,n){
		//cout << i << endl;
		ans.assign(n,ce[2].se);
		if(bfs(i)){
			f = 1;
			break;
		}
	}
	if(f)return ans;
	ans.assign(n,0);
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void fix()':
split.cpp:12:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rep(i,a,b) for(int i = a; i<b; i++)
......
   53 |  rep(i,0,ans.size()){
      |      ~~~~~~~~~~~~~~                 
split.cpp:53:2: note: in expansion of macro 'rep'
   53 |  rep(i,0,ans.size()){
      |  ^~~
split.cpp: In function 'bool bfs(int)':
split.cpp:12:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rep(i,a,b) for(int i = a; i<b; i++)
......
   80 |  rep(i,0,ans.size()){
      |      ~~~~~~~~~~~~~~                 
split.cpp:80:2: note: in expansion of macro 'rep'
   80 |  rep(i,0,ans.size()){
      |  ^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:12:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rep(i,a,b) for(int i = a; i<b; i++)
......
  100 |  rep(i,0,p.size()){
      |      ~~~~~~~~~~~~                   
split.cpp:100:2: note: in expansion of macro 'rep'
  100 |  rep(i,0,p.size()){
      |  ^~~

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