oj.uz

답안 #590542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590542 2022-07-06T06:01:52 Z 장태환(#8413) Amusement Park (JOI17_amusement_park) C++14
0 / 100
 1206 ms 80644 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[tt[n][i]].size(); j++)
			{
				if (cnt[tt[n][i]][tt[tt[n][i]][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]] = 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;
			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[tt[n][i]].size(); j++)
			{
				if (cnt[tt[n][i]][tt[tt[n][i]][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]] = 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;
			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[tt[n][i]].size(); j++)
      |                ~~^~~~~~~~~~~~~~~~~~~~~
Joi.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Joi.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (j = 0; j < tt[n].size(); j++)
      |                ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void {anonymous}::dfs2(int, int)':
Joi.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  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[tt[n][i]].size(); j++)
      |                ~~^~~~~~~~~~~~~~~~~~~~~
Ioi.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Ioi.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for (j = 0; j < tt[n].size(); j++)
      |                ~~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::dfs2(int, int)':
Ioi.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (i = 0; i < link[n].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::dfs3(int, int)':
Ioi.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   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:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (i = 0; i < fs.size(); i++)
      |              ~~^~~~~~~~~~~
Ioi.cpp:118:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for (i = 0; i < tt[P].size(); i++)
      |              ~~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2824 KB Output is correct
2 Incorrect 2 ms 3348 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 79848 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 3348 KB Output is correct
3 Correct 2 ms 3340 KB Output is correct
4 Correct 1206 ms 29708 KB Output is correct
5 Incorrect 1062 ms 29756 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 114 ms 78404 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 175 ms 80644 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -