Submission #1226708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226708		repsak	Split the Attractions (IOI19_split)	C++20	11 / 100	49 ms	10564 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> visited;

void DFS(int u, int team, int& counter, int max){
	if(visited[u] || counter >= max) return;
	visited[u] = team; counter++;

	for(int v : adj[u]){
		DFS(v, team, counter, max);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	adj.resize(n);
	visited.resize(n);
	
	for(int i = 0; i < p.size(); i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}

	int findAmount = min(b, c);
	int findTeam = b < c ? 2 : 3;
	int counter = 0;
	DFS(0, findTeam, counter, findAmount);
	
	bool hasFoundA = false;
	int otherTeam = b < c ? 3 : 2;
	for(int i = 0; i < n; i++){
		if(visited[i] == 0 && !hasFoundA){
			hasFoundA = true;
			visited[i] = 1;
		}
		
		if(visited[i] == 0){
			visited[i] = otherTeam;
		}
	}

	return visited;
}

// #include "grader.cpp"

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