Submission #823141

#	Time	Username	Problem	Language	Result	Execution time	Memory
823141		vjudge1	Split the Attractions (IOI19_split)	C++17	18 / 100	434 ms	1048576 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);
	}
}
int sz[N];
void precalc(int s, int p) {
	sz[s] = 1;
	for(int to : g[s]) {
		if(to == p) continue;
		precalc(to, s);
		sz[s] += sz[to];
	}
}

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;
	}
	if(m == n - 1) {
		precalc(0, 0);
		int u, v;
		vector<pair<int, int>> cl;
		cl.push_back({a, 1});
		cl.push_back({b, 2});
		cl.push_back({c, 3});
		sort(cl.begin(), cl.end());
		for(int i = 0; i < m; i++) {
			if(sz[p[i]] < sz[q[i]]) swap(p[i], q[i]);
			if(sz[q[i]] >= cl[0].first && n - sz[q[i]] >= cl[1].first) {
				u = q[i];
				v = p[i];
			}
		}
		vector<int> res(n, cl[2].second);
		vis.assign(n, false);
		vis[v] = 1;
		dfs(u, cl[0].first);
		for(int c : ord) res[c] = cl[0].second;
		ord.clear();
		vis.assign(n, false);
		vis[u] = 1;
		dfs(v, cl[1].first);
		for(int c : ord) res[c] = cl[1].second;
		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:106:1: warning: control reaches end of non-void function [-Wreturn-type]
  106 | }
      | ^
split.cpp:102:6: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |   dfs(v, cl[1].first);
      |   ~~~^~~~~~~~~~~~~~~~
split.cpp:101:8: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |   vis[u] = 1;
      |        ^

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