oj.uz

Submission #146250

# Submission time Handle Problem Language Result Execution time Memory
146250 2019-08-23T06:13:42 Z jwvg0425 Split the Attractions (IOI19_split) C++17
18 / 100
 214 ms 23924 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, int c)
{
	visited[root] = true;

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

		mark(e, v, c);
	}

	if (marked[v].size() == c)
		return;

	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, v[0].xx);
		memset(visited, false, sizeof(visited));
		for (auto& mi : marked[0])
		{
			val[mi] = v[0].yy;
			visited[mi] = true;
		}

		mark(cent, 1, v[1].xx);


		for (auto& mi : marked[1])
			val[mi] = v[1].yy;

		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 'void mark(int, int, int)':
split.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (marked[v].size() == c)
      ~~~~~~~~~~~~~~~~~^~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:120: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 7 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 7 ms 5084 KB ok, correct split
6 Correct 6 ms 5112 KB ok, correct split
7 Correct 163 ms 23572 KB ok, correct split
8 Correct 152 ms 20904 KB ok, correct split
9 Correct 171 ms 20468 KB ok, correct split
10 Correct 204 ms 23524 KB ok, correct split
11 Correct 179 ms 23924 KB ok, correct split

Subtask #2
11.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 5116 KB ok, correct split
4 Correct 214 ms 21084 KB ok, correct split
5 Correct 134 ms 16244 KB ok, correct split
6 Correct 183 ms 23672 KB ok, correct split
7 Correct 167 ms 20980 KB ok, correct split
8 Correct 205 ms 18812 KB ok, correct split
9 Correct 148 ms 16088 KB ok, correct split
10 Correct 94 ms 15856 KB ok, correct split
11 Correct 107 ms 15776 KB ok, correct split
12 Correct 100 ms 15728 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Incorrect 136 ms 16344 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 5092 KB ok, no valid answer
3 Correct 6 ms 5112 KB ok, correct split
4 Incorrect 6 ms 5112 KB 2 components are not connected
5 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 7 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 7 ms 5084 KB ok, correct split
6 Correct 6 ms 5112 KB ok, correct split
7 Correct 163 ms 23572 KB ok, correct split
8 Correct 152 ms 20904 KB ok, correct split
9 Correct 171 ms 20468 KB ok, correct split
10 Correct 204 ms 23524 KB ok, correct split
11 Correct 179 ms 23924 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 5116 KB ok, correct split
15 Correct 214 ms 21084 KB ok, correct split
16 Correct 134 ms 16244 KB ok, correct split
17 Correct 183 ms 23672 KB ok, correct split
18 Correct 167 ms 20980 KB ok, correct split
19 Correct 205 ms 18812 KB ok, correct split
20 Correct 148 ms 16088 KB ok, correct split
21 Correct 94 ms 15856 KB ok, correct split
22 Correct 107 ms 15776 KB ok, correct split
23 Correct 100 ms 15728 KB ok, correct split
24 Correct 6 ms 5112 KB ok, correct split
25 Incorrect 136 ms 16344 KB 2 components are not connected
26 Halted 0 ms 0 KB -