oj.uz

Submission #157119

# Submission time Handle Problem Language Result Execution time Memory
157119 2019-10-09T16:26:28 Z Saboon Amusement Park (JOI17_amusement_park) C++14
100 / 100
 76 ms 20740 KB 
#include "Joi.h"

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

static const int NMAX = 10000;
static const int BITS = 60;

namespace {
vector<int> tree[NMAX];
int N;

int union_find[NMAX];
int root(int p)
{
	return union_find[p] < 0 ? p : (union_find[p] = root(union_find[p]));
}
bool join(int p, int q)
{
	p = root(p);
	q = root(q);
	if (p == q) return false;
	union_find[p] += union_find[q];
	union_find[q] = p;
	return true;
}
void SpanningTree(int M, int A[], int B[]) {
	fill(union_find, union_find + N, -1);
	for (int i = 0; i < M; ++i) {
		if (join(A[i], B[i])) {
			tree[A[i]].push_back(B[i]);
			tree[B[i]].push_back(A[i]);
		}
	}
	for (int i = 0; i < N; ++i) sort(tree[i].begin(), tree[i].end());
}

bool HasEdge(int u, int v) {
	return binary_search(tree[u].begin(), tree[u].end(), v);
}

vector<int> subtree[NMAX];
int idx[NMAX];

void InitialSubtree(int p, int rt, vector<int> &sto)
{
	if (sto.size() >= BITS) return;
	idx[p] = sto.size();
	sto.push_back(p);
	for (int q : tree[p]) if (q != rt) {
		InitialSubtree(q, p, sto);
	}
}
void ComputeSubtrees(int p, int rt, vector<pair<int, int> > sub)
{
	bool has = false;
	for (auto v : sub) if (v.first == p) has = true;

	if (!has) {
		int purge = -1;
		for (int i = 0; i < sub.size(); ++i) {
			if (sub[i].second == 1 && sub[i].first != rt) {
				purge = i;
				break;
			}
		}
		for (int i = 0; i < sub.size(); ++i) {
			if (HasEdge(sub[i].first, sub[purge].first)) {
				--sub[i].second;
			}
		}
		idx[p] = idx[sub[purge].first];
		sub[purge] = make_pair(p, 1);
		for (int i = 0; i < sub.size(); ++i) {
			if (sub[i].first == rt) {
				++sub[i].second;
			}
		}
	}

	for (auto v : sub) subtree[p].push_back(v.first);
	for (int q : tree[p]) if (q != rt) {
		ComputeSubtrees(q, p, sub);
	}
}
void CommonProc(int N_, int M, int A[], int B[]) {
	N = N_;
	SpanningTree(M, A, B);

	vector<int> tree;
	InitialSubtree(0, -1, tree);

	vector<pair<int, int> > tree_deg;
	for (int i = 0; i < tree.size(); ++i) {
		int deg = 0;
		for (int j = 0; j < tree.size(); ++j) {
			if (HasEdge(tree[i], tree[j])) ++deg;
		}
		tree_deg.push_back({ tree[i], deg });
	}
	ComputeSubtrees(0, -1, tree_deg);
}
}
void Joi(int N_, int M, int A[], int B[], long long X, int T) {
	CommonProc(N_, M, A, B);

	for (int i = 0; i < N; ++i) {
		MessageBoard(i, (int)((X >> idx[i]) & 1));
	}
}

#include "Ioi.h"

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

static const int NMAX = 10000;
static const int BITS = 60;

namespace {
vector<int> tree[NMAX];
int N;

int union_find[NMAX];
int root(int p)
{
	return union_find[p] < 0 ? p : (union_find[p] = root(union_find[p]));
}
bool join(int p, int q)
{
	p = root(p);
	q = root(q);
	if (p == q) return false;
	union_find[p] += union_find[q];
	union_find[q] = p;
	return true;
}
void SpanningTree(int M, int A[], int B[]) {
	fill(union_find, union_find + N, -1);
	for (int i = 0; i < M; ++i) {
		if (join(A[i], B[i])) {
			tree[A[i]].push_back(B[i]);
			tree[B[i]].push_back(A[i]);
		}
	}
	for (int i = 0; i < N; ++i) sort(tree[i].begin(), tree[i].end());
}

bool HasEdge(int u, int v) {
	return binary_search(tree[u].begin(), tree[u].end(), v);
}

vector<int> subtree[NMAX];
int idx[NMAX];

void InitialSubtree(int p, int rt, vector<int> &sto)
{
	if (sto.size() >= BITS) return;
	idx[p] = sto.size();
	sto.push_back(p);
	for (int q : tree[p]) if (q != rt) {
		InitialSubtree(q, p, sto);
	}
}
void ComputeSubtrees(int p, int rt, vector<pair<int, int> > sub)
{
	bool has = false;
	for (auto v : sub) if (v.first == p) has = true;

	if (!has) {
		int purge = -1;
		for (int i = 0; i < sub.size(); ++i) {
			if (sub[i].second == 1 && sub[i].first != rt) {
				purge = i;
				break;
			}
		}
		for (int i = 0; i < sub.size(); ++i) {
			if (HasEdge(sub[i].first, sub[purge].first)) {
				--sub[i].second;
			}
		}
		idx[p] = idx[sub[purge].first];
		sub[purge] = make_pair(p, 1);
		for (int i = 0; i < sub.size(); ++i) {
			if (sub[i].first == rt) {
				++sub[i].second;
			}
		}
	}

	for (auto v : sub) subtree[p].push_back(v.first);
	for (int q : tree[p]) if (q != rt) {
		ComputeSubtrees(q, p, sub);
	}
}
void CommonProc(int N_, int M, int A[], int B[]) {
	N = N_;
	SpanningTree(M, A, B);

	vector<int> tree;
	InitialSubtree(0, -1, tree);

	vector<pair<int, int> > tree_deg;
	for (int i = 0; i < tree.size(); ++i) {
		int deg = 0;
		for (int j = 0; j < tree.size(); ++j) {
			if (HasEdge(tree[i], tree[j])) ++deg;
		}
		tree_deg.push_back({ tree[i], deg });
	}
	ComputeSubtrees(0, -1, tree_deg);
}

long long ans;
bool target[NMAX];

void Solve(int p, int rt, int v)
{
	ans |= (long long)v << idx[p];
	for (int q : tree[p]) if (q != rt && target[q]) {
		int v2 = Move(q);
		Solve(q, p, v2);
		Move(p);
	}
}
}
long long Ioi(int N_, int M, int A[], int B[], int P, int V, int T) {
	CommonProc(N_, M, A, B);

	ans = 0;
	for (int i = 0; i < N; ++i) target[i] = false;
	for (auto p : subtree[P]) target[p] = true;

	Solve(P, -1, V);
	return ans;
}

Compilation message

Joi.cpp: In function 'void {anonymous}::ComputeSubtrees(int, int, std::vector<std::pair<int, int> >)':
Joi.cpp:63:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sub.size(); ++i) {
                   ~~^~~~~~~~~~~~
Joi.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sub.size(); ++i) {
                   ~~^~~~~~~~~~~~
Joi.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sub.size(); ++i) {
                   ~~^~~~~~~~~~~~
Joi.cpp: In function 'void {anonymous}::CommonProc(int, int, int*, int*)':
Joi.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tree.size(); ++i) {
                  ~~^~~~~~~~~~~~~
Joi.cpp:98:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < tree.size(); ++j) {
                   ~~^~~~~~~~~~~~~

Ioi.cpp: In function 'void {anonymous}::ComputeSubtrees(int, int, std::vector<std::pair<int, int> >)':
Ioi.cpp:63:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sub.size(); ++i) {
                   ~~^~~~~~~~~~~~
Ioi.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sub.size(); ++i) {
                   ~~^~~~~~~~~~~~
Ioi.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sub.size(); ++i) {
                   ~~^~~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::CommonProc(int, int, int*, int*)':
Ioi.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tree.size(); ++i) {
                  ~~^~~~~~~~~~~~~
Ioi.cpp:98:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < tree.size(); ++j) {
                   ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1884 KB Output is correct
2 Correct 6 ms 1904 KB Output is correct
3 Correct 6 ms 1916 KB Output is correct
4 Correct 5 ms 1908 KB Output is correct
5 Correct 5 ms 1788 KB Output is correct
6 Correct 6 ms 1912 KB Output is correct
7 Correct 6 ms 2272 KB Output is correct
8 Correct 6 ms 2044 KB Output is correct
9 Correct 6 ms 1916 KB Output is correct
10 Correct 6 ms 1908 KB Output is correct
11 Correct 9 ms 2112 KB Output is correct
12 Correct 6 ms 1656 KB Output is correct
13 Correct 6 ms 1916 KB Output is correct
14 Correct 6 ms 1916 KB Output is correct
15 Correct 7 ms 1916 KB Output is correct
16 Correct 8 ms 1916 KB Output is correct
17 Correct 6 ms 2044 KB Output is correct
18 Correct 6 ms 2176 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 11032 KB Output is correct
2 Correct 70 ms 10944 KB Output is correct
3 Correct 71 ms 10820 KB Output is correct
4 Correct 57 ms 10632 KB Output is correct
5 Correct 65 ms 15284 KB Output is correct
6 Correct 63 ms 11536 KB Output is correct
7 Correct 63 ms 12184 KB Output is correct
8 Correct 66 ms 13176 KB Output is correct
9 Correct 67 ms 12576 KB Output is correct
10 Correct 48 ms 9252 KB Output is correct
11 Correct 49 ms 9452 KB Output is correct
12 Correct 50 ms 9568 KB Output is correct
13 Correct 49 ms 9472 KB Output is correct
14 Correct 59 ms 9980 KB Output is correct
15 Correct 60 ms 10876 KB Output is correct
16 Correct 56 ms 10988 KB Output is correct
17 Correct 62 ms 10668 KB Output is correct
18 Correct 57 ms 10520 KB Output is correct
19 Correct 59 ms 10756 KB Output is correct
20 Correct 50 ms 15000 KB Output is correct
21 Correct 49 ms 14800 KB Output is correct
22 Correct 66 ms 12280 KB Output is correct
23 Correct 68 ms 11936 KB Output is correct
24 Correct 67 ms 12040 KB Output is correct
25 Correct 65 ms 12704 KB Output is correct
26 Correct 73 ms 12952 KB Output is correct
27 Correct 65 ms 11988 KB Output is correct
28 Correct 73 ms 12184 KB Output is correct
29 Correct 70 ms 11032 KB Output is correct
30 Correct 67 ms 11432 KB Output is correct
31 Correct 6 ms 1908 KB Output is correct
32 Correct 6 ms 1908 KB Output is correct
33 Correct 6 ms 1924 KB Output is correct
34 Correct 6 ms 1780 KB Output is correct
35 Correct 6 ms 1916 KB Output is correct
36 Correct 6 ms 1908 KB Output is correct
37 Correct 5 ms 1788 KB Output is correct
38 Correct 6 ms 1780 KB Output is correct
39 Correct 5 ms 1788 KB Output is correct
40 Correct 6 ms 1908 KB Output is correct
41 Correct 5 ms 1968 KB Output is correct
42 Correct 5 ms 2028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1904 KB Output is correct
2 Correct 4 ms 1972 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 12 ms 4752 KB Output is correct
5 Correct 12 ms 4776 KB Output is correct
6 Correct 14 ms 4624 KB Output is correct
7 Correct 13 ms 4792 KB Output is correct
8 Correct 12 ms 4780 KB Output is correct
9 Correct 57 ms 20740 KB Output is correct
10 Correct 54 ms 20544 KB Output is correct
11 Correct 54 ms 20544 KB Output is correct
12 Correct 4 ms 1868 KB Output is correct
13 Correct 4 ms 1940 KB Output is correct
14 Correct 4 ms 1912 KB Output is correct
15 Correct 5 ms 1940 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 11008 KB Output is correct
2 Correct 71 ms 11072 KB Output is correct
3 Correct 71 ms 11064 KB Output is correct
4 Correct 56 ms 10268 KB Output is correct
5 Correct 66 ms 16372 KB Output is correct
6 Correct 67 ms 12524 KB Output is correct
7 Correct 66 ms 11560 KB Output is correct
8 Correct 64 ms 11544 KB Output is correct
9 Correct 67 ms 13196 KB Output is correct
10 Correct 50 ms 9252 KB Output is correct
11 Correct 51 ms 9252 KB Output is correct
12 Correct 52 ms 9344 KB Output is correct
13 Correct 51 ms 9540 KB Output is correct
14 Correct 55 ms 9740 KB Output is correct
15 Correct 62 ms 11012 KB Output is correct
16 Correct 56 ms 10784 KB Output is correct
17 Correct 64 ms 10468 KB Output is correct
18 Correct 59 ms 10628 KB Output is correct
19 Correct 56 ms 10528 KB Output is correct
20 Correct 50 ms 14960 KB Output is correct
21 Correct 46 ms 14728 KB Output is correct
22 Correct 67 ms 12824 KB Output is correct
23 Correct 71 ms 12080 KB Output is correct
24 Correct 68 ms 12460 KB Output is correct
25 Correct 65 ms 11832 KB Output is correct
26 Correct 66 ms 11936 KB Output is correct
27 Correct 68 ms 13440 KB Output is correct
28 Correct 67 ms 12320 KB Output is correct
29 Correct 62 ms 11672 KB Output is correct
30 Correct 63 ms 11632 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10952 KB Output is correct
2 Correct 72 ms 11080 KB Output is correct
3 Correct 74 ms 11080 KB Output is correct
4 Correct 57 ms 10644 KB Output is correct
5 Correct 70 ms 18208 KB Output is correct
6 Correct 66 ms 13208 KB Output is correct
7 Correct 65 ms 12960 KB Output is correct
8 Correct 67 ms 12392 KB Output is correct
9 Correct 65 ms 11572 KB Output is correct
10 Correct 48 ms 9328 KB Output is correct
11 Correct 48 ms 9384 KB Output is correct
12 Correct 51 ms 9700 KB Output is correct
13 Correct 52 ms 9576 KB Output is correct
14 Correct 55 ms 9908 KB Output is correct
15 Correct 59 ms 10856 KB Output is correct
16 Correct 55 ms 10988 KB Output is correct
17 Correct 58 ms 10732 KB Output is correct
18 Correct 59 ms 10392 KB Output is correct
19 Correct 57 ms 10600 KB Output is correct
20 Correct 53 ms 14992 KB Output is correct
21 Correct 48 ms 14676 KB Output is correct
22 Correct 67 ms 12044 KB Output is correct
23 Correct 64 ms 11936 KB Output is correct
24 Correct 69 ms 12396 KB Output is correct
25 Correct 66 ms 12568 KB Output is correct
26 Correct 65 ms 12092 KB Output is correct
27 Correct 66 ms 12952 KB Output is correct
28 Correct 71 ms 13248 KB Output is correct
29 Correct 62 ms 12288 KB Output is correct
30 Correct 61 ms 11464 KB Output is correct
31 Correct 6 ms 1780 KB Output is correct
32 Correct 6 ms 1780 KB Output is correct
33 Correct 6 ms 1920 KB Output is correct
34 Correct 5 ms 1908 KB Output is correct
35 Correct 4 ms 1784 KB Output is correct
36 Correct 4 ms 1780 KB Output is correct
37 Correct 4 ms 1916 KB Output is correct
38 Correct 4 ms 1780 KB Output is correct
39 Correct 4 ms 1780 KB Output is correct
40 Correct 4 ms 1780 KB Output is correct
41 Correct 5 ms 1780 KB Output is correct
42 Correct 4 ms 1780 KB Output is correct