oj.uz

Submission #49909

# Submission time Handle Problem Language Result Execution time Memory
49909 2018-06-04T20:32:28 Z MatheusLealV Amusement Park (JOI17_amusement_park) C++17
0 / 100
 589 ms 529296 KB 
#include "Joi.h"
#define maxn 10005
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> grafo[maxn], tree[maxn];

int deep[maxn], used[maxn];

void dfs(int x)
{
	used[x] = 1;

	for(auto v: grafo[x])
	{
		if(used[v]) continue;

		tree[x].push_back(v);

		tree[v].push_back(x);

		dfs(v);
	}
}

void dfs2(int x, int p)
{
	for(auto v: tree[x])
	{
		if(v == p) continue;

		deep[v] = (deep[x] + 1)%60;

		dfs2(v, x);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	for(int i = 0; i < M; i++)
	{
		int a = A[i], b = B[i];

		grafo[a].push_back(b);

		grafo[b].push_back(a);
	}

	dfs(0);

	dfs2(0, 0);

	for(int i = 0; i < N; i++)
	{
		int bit = ( ( X & (1LL<<deep[i])) ? 1 : 0);

		MessageBoard(i, bit);
	}
}

#include "Ioi.h"
#define maxn 10005
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> grafo2[maxn], tree2[maxn];

int deep2[maxn], used2[maxn], dp[maxn], pai[maxn], dist[maxn];

void dfsi(int x)
{
	used2[x] = 1;

	for(auto v: grafo2[x])
	{
		if(used2[v]) continue;

		tree2[x].push_back(v);

		tree2[v].push_back(x);

		dfsi(v);
	}
}

void dfs2i(int x, int p)
{
	pai[x] = p;

	for(auto v: tree2[x])
	{
		if(v == p) continue;

		deep2[v] = (deep2[x] + 1)%60;

		dfs2i(v, x);
	}
}

int dfsbest(int x, int p)
{
	dp[x] = 0;

	for(auto v: grafo2[x])
	{
		if(v == p) continue;

		dfsbest(v, x);

		dp[x] = max(dp[x], dp[v] + 1);
	}
}

void distdfs(int x, int p)
{
	pai[x] = p;

	for(auto v: grafo2[x])
	{
		if(v == p) continue;

		dist[v] = dist[x] + 1;

		distdfs(v, x);
	}
}

ll ans = 0;

set<int> inside, usados;

void solve2(int P)
{
	vector<int> path;

	usados.insert(deep2[P]);

	while(true) // DESCER ATÉ CHEGAR NO DEEP = D(P) - 1 MOD 60
	{
		int melhor = -1, id = -1;

		for(auto v: grafo2[P])
		{
			if(v == pai[P]) continue;

			if(dp[v] > melhor)
			{
				melhor = dp[v];

				id = v;
			}
		}

		if(id == -1 || usados.count(deep2[id])) break;

		P = id;

		path.push_back(P);

		usados.insert(deep2[P]);

		//cout<<P<<" ";
	}

	P = pai[P];

	usados.insert(deep2[P]);

	path.push_back(P);

	//cout<<P<<" ";

	while(usados.size() != 60)
	{
		P = pai[P];

		usados.insert(deep2[P]);

		path.push_back(deep2[P]);

		//cout<<P<<" ";
	}

	//reverse(path.begin(), path.end());

	for(auto p: path)
	{
		int val = Move(p);

		//cout<<p<<" "<<val<<"\n";

		if(!inside.count(deep2[p])) ans += (1LL<<(deep2[p]))*val;

		inside.insert(deep2[p]);
	}

	//cout<<"\n"<<path.size()<<"\n";
}

bool solve1(int N, int P)
{
	vector<int> path;

	distdfs(P, P);

	bool ok = false;

	for(int i = 0; i < N; i++)
	{
		if(deep2[i] == 59 && dist[i] >= 60)
		{
			while(i != P)
			{
				path.push_back(i);

				i = pai[i];
			}

			ok = true;

			break;
		}
	}

	if(!ok) return false;

	reverse(path.begin(), path.end());

	for(auto p: path)
	{
		int val = Move(p);

		if(!inside.count(deep2[p])) ans += (1LL<<(deep2[p]))*val;

		inside.insert(deep2[p]);
	}

	return true;
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
	for(int i = 0; i < M; i++)
	{
		int a = A[i], b = B[i];

		grafo2[a].push_back(b);

		grafo2[b].push_back(a);
	}

	dfsi(0);

	dfs2i(0, 0);

	//if(solve1()) return ans;

	solve2(P);

	return ans;
}

Compilation message

Ioi.cpp: In function 'int dfsbest(int, int)':
Ioi.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 589 ms 265536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 529296 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 529296 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 529296 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 529296 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -