Submission #718147

#	Time	Username	Problem	Language	Result	Execution time	Memory
718147		mseebacher	Split the Attractions (IOI19_split)	C++17	11 / 100	76 ms	12584 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;


#define MAX_N (int) 1e5+5
vector<int> ad[MAX_N];
vector<int> res;
vector<bool> vis(MAX_N);
int cnt;
void dfs(int x,char side){
	if(vis[x] || cnt == 0) return;
	vis[x] = 1;
	if(side == 'b'){
		res[x] = 2;
	}else{
		res[x] = 3;
	}
	cnt--;
	for(auto s: ad[x]){
		dfs(s,side);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for(int i = 0;i<(int)p.size();i++){
		ad[p[i]].push_back(q[i]);
		ad[q[i]].push_back(p[i]);
	}
	res.assign(n,0);
	if(p.size() < n-1 || b >= n-1 || c>=n-1) return res;
	cnt = min(b,c);
	if(b < c){
		res.assign(n,3);
		dfs(0,'b');
		for(int i = 0;i<n;i++){
			if(res[i] == 3){
				res[i] = 1;
				break;
			}
		}
	}else{
		res.assign(n,2);
		dfs(0,'c');
		for(int i = 0;i<n;i++){
			if(res[i] == 2){
				res[i] = 1;
				break;
			}
		}
	}
	if(cnt != 0) res.assign(n,0);
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:32:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |  if(p.size() < n-1 || b >= n-1 || c>=n-1) return res;
      |     ~~~~~~~~~^~~~~

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