oj.uz

답안 #146284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146284 2019-08-23T09:47:53 Z jwvg0425 Split the Attractions (IOI19_split) C++17
18 / 100
 178 ms 22904 KB 
#include "split.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<int> edge[100005];
vector<int> treeEdge[100005];
bool visited[100005];
int cent;
int val[100005];
int csize[100005];
int treeNum[100005];
int parent[100005];
int treeSize[100005];
int compSize[100005];
bool usingTree[100005];
int usingSize;

void dfs(int root)
{
	visited[root] = true;

	for (auto& e : edge[root])
	{
		if (visited[e])
			continue;

		treeEdge[root].push_back(e);
		treeEdge[e].push_back(root);

		dfs(e);
	}
}

int findCent(int root, int n)
{
	csize[root] = 1;

	bool isCent = true;

	for (auto& e : treeEdge[root])
	{
		if (e == parent[root])
			continue;

		parent[e] = root;
		int c = findCent(e, n);

		if (c != -1)
			return c;

		csize[root] += csize[e];

		isCent = isCent && (csize[e] <= (n + 1) / 2);
	}

	if (isCent && n - csize[root] <= (n + 1) / 2)
		return root;

	return -1;
}

void treeDfs(int root, int k)
{
	// cent 방향 안 가면서 크기 계산, 트리 번호도 붙여준다
	treeNum[root] = k;

	for (auto& e : treeEdge[root])
	{
		if (treeNum[e] != 0 || e == cent)
			continue;

		treeDfs(e, k);
	}
}

int comp(int root)
{
	int res = 0;
	if (!usingTree[treeNum[root]])
	{
		res += treeSize[treeNum[root]];
		usingTree[treeNum[root]] = true;
	}
	visited[root] = true;

	for (auto& e : edge[root])
	{
		if (visited[e] || e == cent)
			continue;

		res += comp(e);
	}

	return res;
}

void findTree(int root, int sz)
{
	if (usingSize >= sz)
		return;

	if (!usingTree[treeNum[root]])
	{
		usingSize += treeSize[treeNum[root]];
		usingTree[treeNum[root]] = true;
	}
	visited[root] = true;

	for (auto& e : edge[root])
	{
		if (visited[e] || e == cent)
			continue;

		findTree(e, sz);
	}
}

void mark(int root, int v, int& sz)
{
	if (sz == 0)
		return;

	val[root] = v;
	sz--;

	for (auto& e : edge[root])
	{
		if (val[e] != 0 || !usingTree[treeNum[e]])
			continue;

		mark(e, v, sz);
	}
}

void mark2(int root, int v, int& sz)
{
	if (sz == 0)
		return;
	
	val[root] = v;
	sz--;

	for (auto& e : edge[root])
	{
		if (val[e] != 0)
			continue;

		mark2(e, v, sz);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	vector<ii> v = { { a, 1 }, { b, 2 }, { c, 3 } };

	for (int i = 0; i < p.size(); i++)
	{
		edge[p[i]].push_back(q[i]);
		edge[q[i]].push_back(p[i]);
	}

	dfs(0);

	sort(all(v));

	cent = findCent(0, n);

	// centroid 제외한 그래프에서 a이상의 크기인 트리가 있는지 확인, 있으면 go
	int tr = 1;
	for (auto& e : edge[cent])
	{
		treeDfs(e, tr);
		tr++;
	}

	int k = 0;
	for (int i = 0; i < n; i++)
	{
		if (treeNum[i] != 0)
			k++;

		treeSize[treeNum[i]]++;
	}

	assert(k == n - 1);

	for(int i = 1; i < tr;i++)
	{
		if (treeSize[i] >= v[0].xx)
		{
			int e = -1;

			for (int j = 0; j < n; j++)
			{
				if (treeNum[j] == i)
					e = j;
			}

			//이 경우, 얘 하나만 써도 OK
			usingTree[i] = true;
			mark(e, v[0].yy, v[0].xx);
			mark2(cent, v[1].yy, v[1].xx);

			for (int j = 0; j < n; j++)
				if (val[j] == 0)
					val[j] = v[2].yy;

			vector<int> result(n);
			for (int j = 0; j < n; j++)
				result[j] = val[j];

			return result;
		}

		tr++;
	}

	memset(visited, false, sizeof(visited));
	for (auto& e : edge[cent])
	{
		int c = comp(e);

		if (c < v[0].xx)
			continue;

		// 합해서 a이상 되는 트리 확인 후, 그 트리에 속하는 원소들만 이용해서 a개수 만든다
		memset(visited, false, sizeof(visited));
		memset(usingTree, false, sizeof(usingTree));
		findTree(e, v[0].xx);

		mark(e, v[0].yy, v[0].xx);
		mark2(cent, v[1].yy, v[1].xx);

		for (int i = 0; i < n; i++)
			if (val[i] == 0)
				val[i] = v[2].yy;

		break;
	}

	vector<int> result(n);
	for (int i = 0; i < n; i++)
		result[i] = val[i];

	return result;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:179:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++)
                  ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5116 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 154 ms 22396 KB ok, correct split
8 Correct 144 ms 20088 KB ok, correct split
9 Correct 149 ms 19424 KB ok, correct split
10 Correct 134 ms 22904 KB ok, correct split
11 Correct 146 ms 22784 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 5116 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 152 ms 19576 KB ok, correct split
5 Correct 131 ms 15240 KB ok, correct split
6 Correct 149 ms 22776 KB ok, correct split
7 Correct 139 ms 19964 KB ok, correct split
8 Correct 178 ms 17044 KB ok, correct split
9 Correct 124 ms 14968 KB ok, correct split
10 Correct 92 ms 16084 KB ok, correct split
11 Correct 98 ms 16152 KB ok, correct split
12 Correct 97 ms 16112 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 121 ms 15192 KB ok, correct split
3 Correct 51 ms 9080 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 165 ms 17784 KB ok, correct split
6 Correct 146 ms 17272 KB ok, correct split
7 Correct 172 ms 17064 KB ok, correct split
8 Correct 161 ms 18552 KB ok, correct split
9 Correct 143 ms 16964 KB ok, correct split
10 Incorrect 40 ms 8440 KB invalid split: #1=0, #2=11111, #3=22222
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Incorrect 6 ms 4984 KB invalid split: #1=0, #2=2, #3=4
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5116 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 154 ms 22396 KB ok, correct split
8 Correct 144 ms 20088 KB ok, correct split
9 Correct 149 ms 19424 KB ok, correct split
10 Correct 134 ms 22904 KB ok, correct split
11 Correct 146 ms 22784 KB ok, correct split
12 Correct 6 ms 4984 KB ok, correct split
13 Correct 6 ms 5116 KB ok, correct split
14 Correct 6 ms 4984 KB ok, correct split
15 Correct 152 ms 19576 KB ok, correct split
16 Correct 131 ms 15240 KB ok, correct split
17 Correct 149 ms 22776 KB ok, correct split
18 Correct 139 ms 19964 KB ok, correct split
19 Correct 178 ms 17044 KB ok, correct split
20 Correct 124 ms 14968 KB ok, correct split
21 Correct 92 ms 16084 KB ok, correct split
22 Correct 98 ms 16152 KB ok, correct split
23 Correct 97 ms 16112 KB ok, correct split
24 Correct 6 ms 4984 KB ok, correct split
25 Correct 121 ms 15192 KB ok, correct split
26 Correct 51 ms 9080 KB ok, correct split
27 Correct 6 ms 4984 KB ok, correct split
28 Correct 165 ms 17784 KB ok, correct split
29 Correct 146 ms 17272 KB ok, correct split
30 Correct 172 ms 17064 KB ok, correct split
31 Correct 161 ms 18552 KB ok, correct split
32 Correct 143 ms 16964 KB ok, correct split
33 Incorrect 40 ms 8440 KB invalid split: #1=0, #2=11111, #3=22222
34 Halted 0 ms 0 KB -