Submission #1082746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082746		nickolasarapidis	Split the Attractions (IOI19_split)	C++17	0 / 100	6 ms	7128 KiB

split

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

const int MAXN = 100000;

vector<bool> visited(MAXN, false);
vector<int> adj[MAXN];

vector<int> S(MAXN, 0);
vector<int> S_reset(MAXN, 0);

int v = 0;

void dfs(int x, int s, int id){
	if(visited[x]) return;
	visited[x] = true;
	S[x] = id;
	v++;

	for(auto u : adj[x]){
		if(v == s) return;
		dfs(u, s, id);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){

	vector<int> s(n, 0);

	for(int i = 0; i < n; i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}

	bool d = false;

	dfs(0, a, 1);

	if(v != a){
		return s;
	}

	for(int i = 0; i < n; i++){
		if(S[i] != 0){
			s[i] = S[i];
			S[i] = 0;
		}
	}

	v = 0;

	for(int i = 1; i < n; i++){
		if(visited[i] == false){
			dfs(i, b, 2);
			if(v != b){
				v = 0;
				S = S_reset;
			}
			else{
				d = true;
				v = 0;
				for(int i = 0; i < n; i++){
					if(S[i] == 2){
						s[i] = 2;
						S[i] = 0;
					}
				}

				break;
			}
		}
	}

	if(d == false){
		for(int i = 0; i < n; i++){
			s[i] = 0;
		}

		return s;
	}

	for(int i = 0; i < n; i++){
		if(s[i] == 0) s[i] = 3;
	}

	return s;
}

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