Submission #1292660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292660		ortsac	Split the Attractions (IOI19_split)	C++20	7 / 100	34 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

const int MAXN = 1e5  + 10;
const int INF = 0x3f3f3f3f;

bool seen[MAXN];
int ans[MAXN];
vector<int> adj[MAXN];

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());
	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);
	// retornar
	vector<int> resposta(n);
	for (int i = 0; i < n; i++) resposta[i] = ans[i];
	return resposta;
}

Compilation message (stderr)

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

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