제출 #825442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825442		caganyanmaz	Split the Attractions (IOI19_split)	C++17	0 / 100	95 ms	31888 KiB

split

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

//#define DEBUGGING

using namespace std;

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 1e5;

array<array<int, 2>, 3> arr;
vector<array<int, 2>> g[MXN];
vector<int> res;
set<int> used;
int subsize[MXN];
bitset<MXN> visited;
int n;

struct Node
{
	int head, tail, size, nxt;
	Node(int i) : head(i), tail(i), size(1), nxt(-1) {}
	Node() : Node(-1) {}
};

Node node[MXN];

void merge(int a, int b)
{
	if (node[a].size < node[b].size) swap(a,b);
	node[a].size += node[b].size;
	node[node[a].tail].nxt = b;
	node[a].tail = node[b].tail;
	for (; b != -1; b = node[b].nxt)
		node[b].head = a;
}

void dfs1(int node)
{
	subsize[node] = 1;
	for (auto [c, index] : g[node])
	{
		if (!subsize[c])
		{
			dfs1(c);
			subsize[node] += subsize[c];
		}
	}

}

int find_centroid(int i)
{
	for (auto [c,index]:  g[i])
		if (subsize[c] < subsize[i] && subsize[c] >= (n/2))
			return find_centroid(c);
	return i;
}

void dfs2(int i)
{
	for (auto [c, index] : g[i])
	{
		if (subsize[c] < subsize[i])
		{
			used.insert(index);
			assert(node[c].head != node[i].head);
			merge(node[c].head, node[i].head);
			dfs2(c);
		}
	}
}
void dfs3(int i)
{
	visited[i] = true;
	for (auto [c, index] : g[i])
	{
		if (!visited[c])
		{
			debug(i, c);
			used.insert(index);
			assert(node[c].head != node[i].head);
			merge(node[c].head, node[i].head);
			dfs3(c);
		}
	}
}


int centroid;
int counter;
bool dfs4(int i, int val)
{
	res[i] = arr[val][1];
	counter++;
	if (counter == arr[val][0])
		return true;
	for (auto [c, index] : g[i])
	{
		if (node[c].head == node[i].head && !res[c])
		{
			bool out = dfs4(c, val);
			if (out)
				return true;
		}
	}
	return false;
}

bool dfs5(int i, int val)
{
	res[i] = arr[val][1];
	counter++;
	if (counter == arr[val][0])
		return true;
	for (auto [c, index] : g[i])
	{
		if (!res[c])
		{
			bool out = dfs5(c, val);
			if (out)
				return true;
		}
	}
	return false;
}


vector<int> finish(int subtree)
{
	int val = 0;
	if (node[subtree].size >= arr[1][0])
		val = 1;
	assert(dfs4(subtree, val));
	counter = 0;
	assert(dfs5(centroid, val^1));
	for (int i = 0; i < n; i++)
		if (!res[i])
			res[i] = arr[2][1];
	return res;
		
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q)
{

	n = _n;
	res = vector<int>(n, 0);
	for (int i = 0; i < n; i++)
		node[i] = Node(i);
	arr[0] = {a, 1};
	arr[1] = {b, 2};
	arr[2] = {c, 3};
	sort(arr.begin(), arr.end());
	for (int i = 0; i < p.size(); i++)
	{
		g[p[i]].pb({q[i], i});
		g[q[i]].pb({p[i], i});
	}
	dfs1(0);
	centroid = find_centroid(0);
	visited[centroid] = true;
	debug(centroid);
	for (auto [c, index] : g[centroid])
	{
		used.insert(index);
		if (subsize[c] < subsize[centroid])
			dfs2(c);
	}
	for (auto [c, index] : g[centroid])
		if (subsize[c] > subsize[centroid])
			dfs3(c);
	for (auto [c, index] : g[centroid])
		if ((subsize[c] < subsize[centroid] && subsize[c] >= arr[0][0]) || (subsize[c] > subsize[centroid] && subsize[c] - subsize[centroid] >= arr[0][0]))
			return finish(node[c].head);
	for (int i = 0; i < p.size(); i++)
	{
		if (used.find(i) != used.end() || p[i] == centroid || q[i] == centroid)
			continue;
		used.insert(i);
		if (node[p[i]].head == node[q[i]].head)
			continue;
		merge(node[p[i]].head, node[q[i]].head);
		if (node[node[p[i]].head].size >= arr[0][0])
			return finish(node[p[i]].head);
	}
	return res;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:161:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
split.cpp:182:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~

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