Submission #772866

#	Time	Username	Problem	Language	Result	Execution time	Memory
772866		Abrar_Al_Samit	Split the Attractions (IOI19_split)	C++17	7 / 100	715 ms	1048576 KiB

split

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

const int nax = 1e5 + 3;

//subtask 1

vector<int>g[nax];
int m, n;

vector<int>stk;

void dfs(int v, int p) {
	stk.push_back(v);

	for(int u : g[v]) if(u!=p && u!=stk[0]) {
		dfs(u, v);
	}
}
vector<int> find_split(int N, int a, int b, int c, 
	vector<int> p, vector<int> q) {
	n = N;

	m = p.size();
	for(int i=0; i<m; ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}

	int st = 0;
	for(int i=0; i<n; ++i) if(g[i].size()==1) {
		st = i;
		break;
	}
	dfs(st, st);

	vector<int>res(n, 0);
	for(int i=0; i<n; ++i) {
		if(i<a) res[stk[i]] = 1;
		else if(i<a+b) res[stk[i]] = 2;
		else res[stk[i]] = 3;
	}
	return res;
}

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