oj.uz

Submission #590551

# Submission time Handle Problem Language Result Execution time Memory
590551 2022-07-06T06:19:00 Z 장태환(#8413) Amusement Park (JOI17_amusement_park) C++14
100 / 100
 122 ms 134520 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
	int uf[10100];
	int f(int n)
	{
		return uf[n] == n ? n : uf[n] = f(uf[n]);
	}
	void u(int n, int m)
	{
		uf[f(n)] = f(m);
	}
	vector<int>link[10100];
	vector<int>tt[10100];
	bool cnt[10100][10100];
	int bass[100100];
	void dfs(int n, int p)
	{
		int i;
		for (i = 0; i < tt[n].size(); i++)
		{
			if (tt[n][i] == n)
				continue;
			int j;
			int r = 0;
			for (j = 0; j < tt[n].size(); j++)
			{
				if (i == j)
					continue;
				if (cnt[tt[n][i]][tt[n][j]])
				{
					r++;
				}
			}
			if (r == 1)
				break;
		}
		int ers = tt[n][i];
		for (i = 0; i < link[n].size(); i++)
		{
			if (link[n][i] == p)
				continue;
			int j;
			if (tt[link[n][i]].size())
				goto T;
			for (j = 0; j < tt[n].size(); j++)
			{
				if (tt[n][j] != ers)
				{
					tt[link[n][i]].push_back(tt[n][j]);
				}
			}
			bass[link[n][i]] = bass[ers];
			tt[link[n][i]].push_back(link[n][i]);
		T:
			dfs(link[n][i], n);
		}
	}
	vector<int>fs;
	void dfs2(int n, int p)
	{
		if (fs.size() == 60)
		{
			return;
		}
		int i;
		bass[n] = fs.size();
		fs.push_back(n);
		for (i = 0; i < link[n].size(); i++)
		{
			if (link[n][i] == p)
				continue;
			dfs2(link[n][i], n);
		}
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) 
{
	memset(bass, -1, sizeof(bass));
	int i;
	for (i = 0; i < N; i++)
	{
		uf[i] = i;
	}
	for (i = 0; i < M; i++)
	{
		if (f(A[i]) != f(B[i]))
		{
			u(A[i], B[i]);
			cnt[A[i]][B[i]] = true;
			cnt[B[i]][A[i]] = true;
			link[A[i]].push_back(B[i]);
			link[B[i]].push_back(A[i]);
		}
	}
	dfs2(0, -1);
	for (i = 0; i < fs.size(); i++)
	{
		tt[fs[i]] = fs;
	}
	dfs(0, -1);
	for (i = 0; i < N; i++)
	{
		MessageBoard(i, (int)((X >> (bass[i]))&1));
	}
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
	int uf[10100];
	int f(int n)
	{
		return uf[n] == n ? n : uf[n] = f(uf[n]);
	}
	void u(int n, int m)
	{
		uf[f(n)] = f(m);
	}
	vector<int>link[10100];
	vector<int>tt[10100];
	bool cnt[10100][10100];
	int bass[100100];
	void dfs(int n, int p)
	{
		int i;
		for (i = 0; i < tt[n].size(); i++)
		{
			if (tt[n][i] == n)
				continue;
			int j;
			int r = 0;
			for (j = 0; j < tt[n].size(); j++)
			{
				if (i == j)
					continue;
				if (cnt[tt[n][i]][tt[n][j]])
				{
					r++;
				}
			}
			if (r == 1)
				break;
		}
		int ers = tt[n][i];
		for (i = 0; i < link[n].size(); i++)
		{
			if (link[n][i] == p)
				continue;
			int j;
			if (tt[link[n][i]].size())
				goto T;
			for (j = 0; j < tt[n].size(); j++)
			{
				if (tt[n][j] != ers)
				{
					tt[link[n][i]].push_back(tt[n][j]);
				}
			}
			bass[link[n][i]] = bass[ers];
			tt[link[n][i]].push_back(link[n][i]);
		T:
			dfs(link[n][i], n);
		}
	}
	vector<int>fs;
	void dfs2(int n, int p)
	{
		if (fs.size() == 60)
		{
			return;
		}
		int i;
		bass[n] = fs.size();
		fs.push_back(n);
		for (i = 0; i < link[n].size(); i++)
		{
			if (link[n][i] == p)
				continue;
			dfs2(link[n][i], n);
		}
	}
	int ans[60];
	bool ind[20010];
	void dfs3(int n, int p)
	{
		int i;
		for (i = 0; i < link[n].size(); i++)
		{
			if (link[n][i] == p)
				continue;
			if (!ind[link[n][i]])
				continue;
			ans[bass[link[n][i]]] = Move(link[n][i]);
			dfs3(link[n][i], n);
			Move(n);
		}
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	memset(bass, -1, sizeof(bass));
	int i;
	for (i = 0; i < N; i++)
	{
		uf[i] = i;
	}
	for (i = 0; i < M; i++)
	{
		if (f(A[i]) != f(B[i]))
		{
			u(A[i], B[i]);
			cnt[A[i]][B[i]] = true;
			cnt[B[i]][A[i]] = true;
			link[A[i]].push_back(B[i]);
			link[B[i]].push_back(A[i]);
		}
	}
	dfs2(0, -1);
	for (i = 0; i < fs.size(); i++)
	{
		tt[fs[i]] = fs;
	}
	dfs(0, -1);
	ans[bass[P]] = V;
	for (i = 0; i < tt[P].size(); i++)
	{
		ind[tt[P][i]] = 1;
	}
	dfs3(P, -1);
	long long rans = 0;
	for (i = 0; i < 60; i++)
	{
		rans += (1LL << i) * ans[i];
	}
	return rans;
}

Compilation message

Joi.cpp: In function 'void {anonymous}::dfs(int, int)':
Joi.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (i = 0; i < tt[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~
Joi.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    for (j = 0; j < tt[n].size(); j++)
      |                ~~^~~~~~~~~~~~~~
Joi.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Joi.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for (j = 0; j < tt[n].size(); j++)
      |                ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void {anonymous}::dfs2(int, int)':
Joi.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:99:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (i = 0; i < fs.size(); i++)
      |              ~~^~~~~~~~~~~

Ioi.cpp: In function 'void {anonymous}::dfs(int, int)':
Ioi.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for (i = 0; i < tt[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~
Ioi.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (j = 0; j < tt[n].size(); j++)
      |                ~~^~~~~~~~~~~~~~
Ioi.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Ioi.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for (j = 0; j < tt[n].size(); j++)
      |                ~~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::dfs2(int, int)':
Ioi.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::dfs3(int, int)':
Ioi.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for (i = 0; i < fs.size(); i++)
      |              ~~^~~~~~~~~~~
Ioi.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for (i = 0; i < tt[P].size(); i++)
      |              ~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3088 KB Output is correct
2 Correct 2 ms 3600 KB Output is correct
3 Correct 4 ms 5136 KB Output is correct
4 Correct 2 ms 3340 KB Output is correct
5 Correct 2 ms 3336 KB Output is correct
6 Correct 3 ms 3864 KB Output is correct
7 Correct 4 ms 5148 KB Output is correct
8 Correct 3 ms 4840 KB Output is correct
9 Correct 4 ms 4628 KB Output is correct
10 Correct 3 ms 3652 KB Output is correct
11 Correct 5 ms 3748 KB Output is correct
12 Correct 2 ms 2836 KB Output is correct
13 Correct 2 ms 5084 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5140 KB Output is correct
16 Correct 5 ms 4896 KB Output is correct
17 Correct 4 ms 5012 KB Output is correct
18 Correct 4 ms 4884 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 126560 KB Output is correct
2 Correct 81 ms 127160 KB Output is correct
3 Correct 95 ms 126872 KB Output is correct
4 Correct 75 ms 122712 KB Output is correct
5 Correct 109 ms 133956 KB Output is correct
6 Correct 83 ms 127664 KB Output is correct
7 Correct 94 ms 126884 KB Output is correct
8 Correct 91 ms 127520 KB Output is correct
9 Correct 92 ms 127096 KB Output is correct
10 Correct 68 ms 93396 KB Output is correct
11 Correct 72 ms 94320 KB Output is correct
12 Correct 70 ms 115196 KB Output is correct
13 Correct 71 ms 115600 KB Output is correct
14 Correct 75 ms 121140 KB Output is correct
15 Correct 79 ms 128992 KB Output is correct
16 Correct 84 ms 128768 KB Output is correct
17 Correct 72 ms 123592 KB Output is correct
18 Correct 81 ms 123836 KB Output is correct
19 Correct 87 ms 123652 KB Output is correct
20 Correct 66 ms 90548 KB Output is correct
21 Correct 71 ms 89348 KB Output is correct
22 Correct 82 ms 126708 KB Output is correct
23 Correct 104 ms 126944 KB Output is correct
24 Correct 93 ms 127100 KB Output is correct
25 Correct 88 ms 127300 KB Output is correct
26 Correct 87 ms 127272 KB Output is correct
27 Correct 84 ms 127212 KB Output is correct
28 Correct 87 ms 126764 KB Output is correct
29 Correct 95 ms 115656 KB Output is correct
30 Correct 79 ms 121136 KB Output is correct
31 Correct 4 ms 3672 KB Output is correct
32 Correct 3 ms 3812 KB Output is correct
33 Correct 3 ms 4820 KB Output is correct
34 Correct 3 ms 3664 KB Output is correct
35 Correct 3 ms 3340 KB Output is correct
36 Correct 2 ms 3028 KB Output is correct
37 Correct 2 ms 3092 KB Output is correct
38 Correct 2 ms 2836 KB Output is correct
39 Correct 2 ms 2896 KB Output is correct
40 Correct 2 ms 3080 KB Output is correct
41 Correct 2 ms 3340 KB Output is correct
42 Correct 3 ms 3084 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3208 KB Output is correct
2 Correct 3 ms 3336 KB Output is correct
3 Correct 2 ms 3336 KB Output is correct
4 Correct 10 ms 16692 KB Output is correct
5 Correct 13 ms 16708 KB Output is correct
6 Correct 13 ms 16724 KB Output is correct
7 Correct 11 ms 16724 KB Output is correct
8 Correct 11 ms 16784 KB Output is correct
9 Correct 65 ms 90448 KB Output is correct
10 Correct 61 ms 90472 KB Output is correct
11 Correct 57 ms 90436 KB Output is correct
12 Correct 3 ms 3088 KB Output is correct
13 Correct 3 ms 3024 KB Output is correct
14 Correct 2 ms 2824 KB Output is correct
15 Correct 4 ms 2828 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 126472 KB Output is correct
2 Correct 104 ms 126696 KB Output is correct
3 Correct 90 ms 126420 KB Output is correct
4 Correct 102 ms 122920 KB Output is correct
5 Correct 122 ms 133800 KB Output is correct
6 Correct 98 ms 127220 KB Output is correct
7 Correct 89 ms 127244 KB Output is correct
8 Correct 84 ms 126672 KB Output is correct
9 Correct 88 ms 126844 KB Output is correct
10 Correct 90 ms 93848 KB Output is correct
11 Correct 64 ms 93928 KB Output is correct
12 Correct 80 ms 115172 KB Output is correct
13 Correct 82 ms 114984 KB Output is correct
14 Correct 94 ms 121020 KB Output is correct
15 Correct 97 ms 128840 KB Output is correct
16 Correct 83 ms 129280 KB Output is correct
17 Correct 96 ms 123892 KB Output is correct
18 Correct 82 ms 123396 KB Output is correct
19 Correct 98 ms 124340 KB Output is correct
20 Correct 72 ms 90592 KB Output is correct
21 Correct 63 ms 89224 KB Output is correct
22 Correct 111 ms 127408 KB Output is correct
23 Correct 113 ms 127284 KB Output is correct
24 Correct 90 ms 126952 KB Output is correct
25 Correct 112 ms 127360 KB Output is correct
26 Correct 102 ms 127484 KB Output is correct
27 Correct 105 ms 127924 KB Output is correct
28 Correct 101 ms 126920 KB Output is correct
29 Correct 100 ms 116060 KB Output is correct
30 Correct 87 ms 120856 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 126296 KB Output is correct
2 Correct 106 ms 127088 KB Output is correct
3 Correct 118 ms 127012 KB Output is correct
4 Correct 88 ms 122528 KB Output is correct
5 Correct 97 ms 134520 KB Output is correct
6 Correct 102 ms 127124 KB Output is correct
7 Correct 115 ms 126868 KB Output is correct
8 Correct 111 ms 127512 KB Output is correct
9 Correct 91 ms 127364 KB Output is correct
10 Correct 70 ms 94008 KB Output is correct
11 Correct 63 ms 94268 KB Output is correct
12 Correct 72 ms 114836 KB Output is correct
13 Correct 106 ms 115128 KB Output is correct
14 Correct 106 ms 120964 KB Output is correct
15 Correct 89 ms 128208 KB Output is correct
16 Correct 79 ms 129000 KB Output is correct
17 Correct 98 ms 124028 KB Output is correct
18 Correct 108 ms 123424 KB Output is correct
19 Correct 84 ms 124512 KB Output is correct
20 Correct 62 ms 90664 KB Output is correct
21 Correct 68 ms 89312 KB Output is correct
22 Correct 88 ms 126800 KB Output is correct
23 Correct 101 ms 126796 KB Output is correct
24 Correct 86 ms 126976 KB Output is correct
25 Correct 87 ms 127452 KB Output is correct
26 Correct 94 ms 127356 KB Output is correct
27 Correct 84 ms 127168 KB Output is correct
28 Correct 97 ms 127176 KB Output is correct
29 Correct 88 ms 116216 KB Output is correct
30 Correct 84 ms 121624 KB Output is correct
31 Correct 3 ms 3604 KB Output is correct
32 Correct 3 ms 3852 KB Output is correct
33 Correct 4 ms 4884 KB Output is correct
34 Correct 3 ms 3680 KB Output is correct
35 Correct 2 ms 3340 KB Output is correct
36 Correct 2 ms 3092 KB Output is correct
37 Correct 2 ms 3084 KB Output is correct
38 Correct 2 ms 2836 KB Output is correct
39 Correct 2 ms 2836 KB Output is correct
40 Correct 2 ms 3212 KB Output is correct
41 Correct 2 ms 3340 KB Output is correct
42 Correct 2 ms 3084 KB Output is correct