Submission #589456

#	Time	Username	Problem	Language	Result	Execution time	Memory
589456		Soumya1	Split the Attractions (IOI19_split)	C++17	40 / 100	73 ms	16768 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
	#include <debug_local.h>
#endif
using namespace std;
const int mxN = 1e5 + 5;
vector<int> ad[mxN];
bool vis[mxN];
int need;
vector<int> s1;
void dfs(int u) {
	vis[u] = true;
	if (s1.size() == need) return;
	s1.push_back(u);
	for (int v : ad[u]) {
		if (vis[v]) continue;
		dfs(v);
	}
}
int sz[mxN], in[mxN], out[mxN], timer;
void dfs1(int u, int p) {
	in[u] = ++timer;
  sz[u] = 1;
  for (int v : ad[u]) {
    if (v == p) continue;
    dfs1(v, u);
    sz[u] += sz[v];
  }
  out[u] = timer;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for (int i = 0; i < p.size(); i++) {
		ad[p[i]].push_back(q[i]);
		ad[q[i]].push_back(p[i]);
	}
	if (p.size() == n - 1) {
		vector<pair<int, int>> choice = {{a, 1}, {b, 2}, {c, 3}};
		sort(choice.begin(), choice.end());
		int A = choice[0].first;
		int B = choice[1].first;
		vector<int> ans(n, choice[2].second);
		dfs1(0, -1);
		for (int i = 0; i < n - 1; i++) {
			if (in[p[i]] <= in[q[i]] && out[q[i]] <= out[p[i]]) swap(p[i], q[i]);
			if (sz[p[i]] >= A && n - sz[p[i]] >= B) {
				need = A;
				for (int j = 0; j < n; j++) vis[j] = !(in[j] >= in[p[i]] && out[j] <= out[p[i]]);
				dfs(p[i]);
				for (int j : s1) ans[j] = choice[0].second;
				memset(vis, 0, sizeof vis);
				s1.clear();
				need = B;
				for (int j = 0; j < n; j++) vis[j] = (in[j] >= in[p[i]] && out[j] <= out[p[i]]);
				dfs(q[i]);
				for (int j : s1) ans[j] = choice[1].second;
				return ans;
			}
			if (sz[p[i]] >= B && n - sz[p[i]] >= A) {
				need = B;
				for (int j = 0; j < n; j++) vis[j] = !(in[j] >= in[p[i]] && out[j] <= out[p[i]]);
				dfs(p[i]);
				for (int j : s1) ans[j] = choice[1].second;
				memset(vis, 0, sizeof vis);
				s1.clear();
				need = A;
				for (int j = 0; j < n; j++) vis[j] = (in[j] >= in[p[i]] && out[j] <= out[p[i]]);
				dfs(q[i]);
				for (int j : s1) ans[j] = choice[0].second;
				return ans;
			}
		}
		ans.assign(n, 0);
		return ans;
	}
	if (a == 1) {
		vector<int> ans(n, 3);
		need = b;
		dfs(1);
		for (int i : s1) ans[i] = 2;
		for (int i = 0; i < n; i++) {
			if (ans[i] == 3) {
				ans[i] = 1;
				break;
			}
		}
		return ans;
	}
	int start = 0;
	vector<int> deg(n);
	for (int i : p) deg[i]++;
	for (int i : q) deg[i]++;
	for (int i = 0; i < n; i++) {
		if (deg[i] == 1) start = i;
	}
	vector<int> ans(n);
	int cur = 0;
	while (!ans[start]) {
		cur++;
		if (cur <= a) ans[start] = 1;
		else if (cur <= a + b) ans[start] = 2;
		else ans[start] = 3;
		for (int to : ad[start]) {
			if (!ans[to]) start = to;
		}
	}
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int)':
split.cpp:14:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   14 |  if (s1.size() == need) return;
      |      ~~~~~~~~~~^~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
split.cpp:37:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |  if (p.size() == n - 1) {
      |      ~~~~~~~~~^~~~~~~~

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