oj.uz

Submission #146245

# Submission time Handle Problem Language Result Execution time Memory
146245 2019-08-23T04:33:19 Z jwvg0425 Split the Attractions (IOI19_split) C++17
29 / 100
 2000 ms 23056 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];

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)
{
	if (c == 0)
		return;

	val[root] = v;
	c--;

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

		mark(e, v, c);
	}
}

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(1);

	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;

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

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

	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 7 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 7 ms 5036 KB ok, correct split
4 Correct 7 ms 5112 KB ok, correct split
5 Correct 6 ms 5096 KB ok, correct split
6 Correct 7 ms 5112 KB ok, correct split
7 Correct 180 ms 23056 KB ok, correct split
8 Correct 149 ms 20856 KB ok, correct split
9 Correct 144 ms 20088 KB ok, correct split
10 Correct 148 ms 22588 KB ok, correct split
11 Correct 156 ms 22136 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 5112 KB ok, correct split
4 Correct 177 ms 20872 KB ok, correct split
5 Correct 130 ms 15864 KB ok, correct split
6 Correct 155 ms 22620 KB ok, correct split
7 Correct 188 ms 20700 KB ok, correct split
8 Correct 345 ms 18808 KB ok, correct split
9 Correct 147 ms 16004 KB ok, correct split
10 Execution timed out 2041 ms 14996 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 134 ms 15924 KB ok, correct split
3 Correct 49 ms 9464 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 212 ms 18356 KB ok, correct split
6 Correct 144 ms 18040 KB ok, correct split
7 Correct 154 ms 17912 KB ok, correct split
8 Correct 153 ms 19184 KB ok, correct split
9 Correct 155 ms 17796 KB ok, correct split
10 Correct 38 ms 8568 KB ok, no valid answer
11 Correct 56 ms 10360 KB ok, no valid answer
12 Correct 113 ms 15848 KB ok, no valid answer
13 Correct 139 ms 15608 KB ok, no valid answer
14 Correct 97 ms 16184 KB ok, no valid answer

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 5112 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 invalid split: #1=4, #2=2, #3=6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 7 ms 5036 KB ok, correct split
4 Correct 7 ms 5112 KB ok, correct split
5 Correct 6 ms 5096 KB ok, correct split
6 Correct 7 ms 5112 KB ok, correct split
7 Correct 180 ms 23056 KB ok, correct split
8 Correct 149 ms 20856 KB ok, correct split
9 Correct 144 ms 20088 KB ok, correct split
10 Correct 148 ms 22588 KB ok, correct split
11 Correct 156 ms 22136 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 5112 KB ok, correct split
15 Correct 177 ms 20872 KB ok, correct split
16 Correct 130 ms 15864 KB ok, correct split
17 Correct 155 ms 22620 KB ok, correct split
18 Correct 188 ms 20700 KB ok, correct split
19 Correct 345 ms 18808 KB ok, correct split
20 Correct 147 ms 16004 KB ok, correct split
21 Execution timed out 2041 ms 14996 KB Time limit exceeded
22 Halted 0 ms 0 KB -