Submission #823125

#	Time	Username	Problem	Language	Result	Execution time	Memory
823125		vjudge1	Split the Attractions (IOI19_split)	C++17	18 / 100	65 ms	15676 KiB

split

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

using namespace std;

const int N = 1e5 + 10;

vector<int> g[N];

vector<bool> vis;
vector<int> ord;
void bamboo(int s) {
	vis[s] = 1;
	ord.push_back(s);
	for(int to : g[s]) {
		if(vis[to]) continue;
		bamboo(to);
	}
}

void dfs(int s, int lim) {
	if((int)ord.size() == lim) return;
	vis[s] = 1;
	ord.push_back(s);
	for(int to : g[s]) {
		if(vis[to]) continue;
		dfs(to, lim);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = (int)p.size();
	for(int i = 0; i < m; i++) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	bool isFirst = 1;
	for(int i = 0; i < n; i++)
		isFirst &= ((int)g[i].size() <= 2);
	if(isFirst) {
		vector<int> res(n);
		int root = 0;
		while(root < n - 1 && (int)g[root].size() == 2)
			root++;
		vis.assign(n, false);
		bamboo(root);
		for(int i = 0; i < a; i++) 
			res[ord[i]] = 1;
		for(int i = a; i < a + b; i++)
			res[ord[i]] = 2;
		for(int i = a + b; i < a + b + c; i++)
			res[ord[i]] = 3;
		return res;
	}
	if(a == 1) {
		vis.assign(n, false);
		dfs(0, b);
		vector<int> res(n);
		for(int c : ord) res[c] = 2;
		bool flag = 1;
		for(int i = 0; i < n; i++) {
			if(res[i]) continue;
			if(flag) {
				res[i] = 1;
				flag = 0;
			} else res[i] = 3;
		}
		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:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^

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