oj.uz

Submission #146253

# Submission time Handle Problem Language Result Execution time Memory
146253 2019-08-23T06:20:50 Z jwvg0425 Split the Attractions (IOI19_split) C++17
7 / 100
 290 ms 24300 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 treeSize[100005];
int parent[100005];
vector<int> marked[2];

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)
{
	treeSize[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;

		treeSize[root] += treeSize[e];

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

	if (isCent && treeSize[root] >= (n + 1) / 2)
		return root;

	return -1;
}

int comp(int root)
{
	// cent 방향 안 가면서 크기 계산
	int res = 1;
	visited[root] = true;

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

		res += comp(e);
	}

	return res;
}

void mark(int root, int v)
{
	visited[root] = true;

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

		mark(e, v);
		marked[v].push_back(root);
	}

	marked[v].push_back(root);
}

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
	memset(visited, false, sizeof(visited));

	for (auto& e : edge[cent])
	{
		int sz = comp(e);

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

		memset(visited, false, sizeof(visited));

		visited[cent] = true;
		mark(e, 0);
		memset(visited, false, sizeof(visited));
		int now0 = 0;

		for (auto& mi : marked[0])
		{
			if (now0 == v[0].xx)
				break;

			if (val[mi] != 0)
				continue;

			val[mi] = v[0].yy;
			visited[mi] = true;
			now0++;
		}

		mark(cent, 1);

		int now1 = 0;

		for (auto& mi : marked[1])
		{
			if (now1 == v[01].xx)
				break;

			if (val[mi] != 0)
				continue;

			val[mi] = v[1].yy;
			now1++;
		}

		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:118: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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Correct 6 ms 5116 KB ok, correct split
7 Correct 203 ms 23104 KB ok, correct split
8 Correct 170 ms 20844 KB ok, correct split
9 Correct 178 ms 20204 KB ok, correct split
10 Correct 290 ms 24192 KB ok, correct split
11 Correct 181 ms 24300 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 5160 KB ok, correct split
4 Correct 194 ms 20788 KB ok, correct split
5 Incorrect 142 ms 15644 KB 2 components are not connected
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5156 KB ok, correct split
2 Incorrect 136 ms 15840 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, no valid answer
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5084 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Correct 6 ms 5112 KB ok, correct split
7 Incorrect 6 ms 5112 KB 2 components are not connected
8 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Correct 6 ms 5116 KB ok, correct split
7 Correct 203 ms 23104 KB ok, correct split
8 Correct 170 ms 20844 KB ok, correct split
9 Correct 178 ms 20204 KB ok, correct split
10 Correct 290 ms 24192 KB ok, correct split
11 Correct 181 ms 24300 KB ok, correct split
12 Correct 6 ms 5112 KB ok, correct split
13 Correct 6 ms 5112 KB ok, correct split
14 Correct 6 ms 5160 KB ok, correct split
15 Correct 194 ms 20788 KB ok, correct split
16 Incorrect 142 ms 15644 KB 2 components are not connected
17 Halted 0 ms 0 KB -