Submission #169930

#	Time	Username	Problem	Language	Result	Execution time	Memory
169930		socho	Split the Attractions (IOI19_split)	C++14	0 / 100	975 ms	1048580 KiB

split

#include "bits/stdc++.h"
#include "split.h"
using namespace std;

int N;
const int MXN = 100005;
int stsize[MXN];
vector<int> adj[MXN];
int parent[MXN];
bool blocked[MXN];

int dfs_st(int node, int last) {
	int sz = 1;
	parent[node] = last;
	for (int i=0; i<adj[node].size(); i++) {
		int ot = adj[node][i];
		if (ot == last) continue;
		sz += dfs_st(ot, node);
	}
	return stsize[node] = sz;
}

int dfs_ce(int node, int last) {
	// cout << " > " << node << ' ' << stsize[node] << endl;
	for (int i=0; i<adj[node].size(); i++) {
		int ot = adj[node][i];
		if (ot == last) continue;
		if (stsize[ot] * 2 > N) return dfs_ce(ot, node);
	}
	return node;
}

int get_centroid() {
	dfs_st(0, -1);
	return dfs_ce(0, -1);
}

int limit = 0;
int taken = 0;
vector<int> picked;

void getst(int node) {
	if (taken >= limit) return;
	picked.push_back(node);
	blocked[node] = true;
	taken++;
	for (int i=0; i<adj[node].size(); i++) {
		if (adj[node][i] == parent[i]) continue;
		if (blocked[adj[node][i]]) continue;
		getst(adj[node][i]);
	}
}

vector<int> took;

void travel(int node, int last) {
	if (taken >= limit) return;
	took.push_back(node);
	blocked[node] = true;
	taken++;
	for (int i=0; i<adj[node].size(); i++) {
		int ot = adj[node][i];
		if (ot == last) continue;
		if (blocked[ot]) continue;
		travel(ot, node);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	
	N = n;
	for (int i=0; i<p.size(); i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	
	int cen = get_centroid();
	dfs_st(cen, -1);
	
	int vs[3] = {a, b, c};
	sort(vs, vs+3);
	int smallest = vs[0];
	
	int lowlabel, midlabel, highlabel;
	if (smallest == a) {
		lowlabel = 1;
		if (b > c) {
			midlabel = 3;
			highlabel = 2;
		}
		else {
			midlabel = 2;
			highlabel = 3;
		}
	}
	else if (smallest == b) {
		lowlabel = 2;
		if (a > c) {
			midlabel = 3;
			highlabel = 1;
		}
		else {
			midlabel = 1;
			highlabel = 3;
		}
	}
	else {
		lowlabel = 3;
		if (a > b) {
			midlabel = 2;
			highlabel = 1;
		}
		else {
			midlabel = 1;
			highlabel = 2;
		}
	}
	
	// cout << "cent: " << cen << endl;
	// cout << lowlabel << ' ' << midlabel << ' ' << highlabel << endl;
	
	int where = cen;
	
	for (int i=0; i<n; i++) {
		if (stsize[i] >= smallest) {
			if (stsize[i] <= stsize[where]) {
				where = i;
			}
		}
	}
	
	// cout << "cancel: " << where << endl;
	
	int take = n - stsize[where];
	
	if (vs[1] > take) {
		vector<int> res;
		for (int i=0; i<n; i++) res.push_back(0);
		return res;
	}
	
	vector<int> res(n, 0);
	
	limit = smallest;
	taken = 0;
	memset(blocked, 0, sizeof blocked);
	getst(where);
	
	// cout << "smallest: " << picked.size() << ' ' << limit << endl;
	for (int i=0; i<picked.size(); i++) {
		// cout << " > " << picked[i] << endl;
		res[picked[i]] = lowlabel;
	}
	
	limit = vs[1];
	taken = 0;
	travel(parent[where], where);
	
	for (int i=0; i<took.size(); i++) {
		res[took[i]] = midlabel;
	}
	
	for (int i=0; i<n; i++) {
		if (res[i] == 0) res[i] = highlabel;
	}
	
	return res;
}

Compilation message (stderr)

split.cpp: In function 'int dfs_st(int, int)':
split.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'int dfs_ce(int, int)':
split.cpp:25:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void getst(int)':
split.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void travel(int, int)':
split.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<p.size(); i++) {
                ~^~~~~~~~~
split.cpp:150:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<picked.size(); i++) {
                ~^~~~~~~~~~~~~~
split.cpp:159:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<took.size(); i++) {
                ~^~~~~~~~~~~~

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