Submission #1082750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082750		nickolasarapidis	Split the Attractions (IOI19_split)	C++17	0 / 100	4 ms	6748 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]);
	}

	for(int k = 0; k < n; k++){
		bool d = false;

		dfs(k, 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;
				S[i] = 0;
			}

			continue;
		}

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

		return s;
	}

	return s;
}

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