Submission #1292658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292658		ortsac	Split the Attractions (IOI19_split)	C++20	7 / 100	33 ms	15760 KiB

split

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

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

vector<bool> seen;
vector<int> ans;
vector<vector<int>> adj;
const int INF = 0x3f3f3f3f;

int dfs(int node, int qtd, int qual) {
	seen[node] = 1;
	ans[node] = qual;
	qtd--;
	if (qtd == 0) {
		for (auto u : adj[node]) if (!seen[u]) return u;
		return -1;
	}
	for (auto u : adj[node]) {
		if (seen[u]) continue;
		return dfs(u, qtd, qual);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<pii> ord = {{a, 1}, {b, 2}, {c, 3}};
	sort(ord.begin(), ord.end());
	seen.clear();
	adj.clear();
	seen.resize(n);
	ans.resize(n);
	adj.resize(n);
	for (int i = 0; i < ((int) p.size()); i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	pii comeco = {INF, INF};
	for (int i = 0; i < n; i++) {
		comeco = min(comeco, {((int)adj[i].size()), i});
	}
	int nxt = dfs(comeco.se, ord[0].fr, ord[0].se);
	nxt = dfs(nxt, ord[1].fr, ord[1].se);
	dfs(nxt, ord[2].fr, ord[2].se);
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'int dfs(int, int, int)':
split.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^

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