oj.uz

답안 #112836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
112836 2019-05-22T06:39:16 Z Mahdi_Jfri Amusement Park (JOI17_amusement_park) C++14
10 / 100
 30 ms 5788 KB 
#include "Joi.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)

const int maxn = 1e4 + 20;

vector<int> g1[maxn] , adj1[maxn] , shit1;

bool visited1[maxn];

int n1 , m1 , h1[maxn];

void plant1(int v)
{
	visited1[v] = 1;
	shit1.pb(v);
	for(auto u : g1[v])
		if(!visited1[u])
		{
			adj1[v].pb(u);
			h1[u] = h1[v] + 1;
			plant1(u);
		}
}

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	n1 = N , m1 = M;
	for(int i = 0; i < m1; i++)
		g1[A[i]].pb(B[i]) , g1[B[i]].pb(A[i]);
	plant1(0);

	int val = *max_element(h1 , h1 + n1) + 1;
	if(val < 60)
	{
		for(int i = 0; i < n1; i++)
		{
			if(i < 60)
				MessageBoard(shit1[i] , bit(X , i));
			else
				MessageBoard(shit1[i] , bit(X , h1[shit1[i]]));
		}
	}
	else
		for(int i = 0; i < n1; i++)
			MessageBoard(i , (X >> (h1[i] % 60))&1);
}















#include "Ioi.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)

const int maxn = 1e4 + 20;

vector<int> g[maxn] , adj[maxn] , shit;

bool visited[maxn];

int n , m , h[maxn] , par[maxn];

void plant(int v)
{
	visited[v] = 1;
	shit.pb(v);
	for(auto u : g[v])
		if(!visited[u])
		{
			adj[v].pb(u);
			h[u] = h[v] + 1;
			par[u] = v;
			plant(u);
		}
}

vector<int> go(int v)
{
	vector<int> res;
	while(v)
		res.pb(v) , v = par[v];
	res.pb(v);

	reverse(res.begin() , res.end());
	return res;
}

void getval(int st , ll &V , int v)
{
	if(st == v)
		return;
	auto b = go(v);

	int ind = -1;
	for(int i = 0; i < h[v] + 1; i++)
		if(b[i] == st)
			ind = i;

	if(ind == -1)
	{
		assert(st != par[st]);
		st = par[st];
		V = Move(st);
		getval(st , V , v);
	}
	else
	{
		assert(st != b[ind + 1]);
		st = b[ind + 1];
		V = Move(st);
		getval(st , V , v);
	}
}

ll Ioi(int N, int M, int A[], int B[], int st , int VV, int T)
{
	ll V = VV;
	n = N , m = M;
	for(int i = 0; i < m; i++)
		g[A[i]].pb(B[i]) , g[B[i]].pb(A[i]);
	plant(0);

	int val = *max_element(h , h + n) + 1;

	ll res = 0;
	if(val < 60)
	{
		cout << 1/0;
		int have = h[st];
		while(st)
		{
			res |= (V << h[st]);
			V = Move(par[st]);
			st = par[st];
		}

		res |= (V << h[0]);
		for(int i = have + 1; i < 60; i++)
		{
			getval(st , V , shit[i]);
			st = shit[i];
			res |= (V << i);
		}
	}
	else
	{
		if(h[st] + 1 < 60)
		{
			while(st)
				V = Move(par[st]) , st = par[st];

			auto tmp = go(max_element(h , h + n) - h);

			for(int i = 0; i < 60; i++)
			{
				if(st != tmp[i])
					V = Move(tmp[i]);
				st = tmp[i];
				res |= (V << i);
			}
		}
		else
		{
			for(int i = 0; i < 60; i++)
			{
				res |= (V << (h[st] % 60));
				if(st != par[st])
					V = Move(par[st]);
				st = par[st];
			}
		}
	}

	return res;
}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:83:12: warning: division by zero [-Wdiv-by-zero]
   cout << 1/0;
           ~^~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 2304 KB Execution killed with signal 4 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5252 KB Output is correct
2 Correct 28 ms 5632 KB Output is correct
3 Correct 28 ms 5788 KB Output is correct
4 Runtime error 20 ms 5304 KB Execution killed with signal 4 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2040 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 7 ms 2364 KB Output is correct
5 Correct 6 ms 2364 KB Output is correct
6 Correct 7 ms 2500 KB Output is correct
7 Correct 7 ms 2492 KB Output is correct
8 Correct 7 ms 2444 KB Output is correct
9 Correct 16 ms 5308 KB Output is correct
10 Correct 15 ms 5432 KB Output is correct
11 Correct 16 ms 5432 KB Output is correct
12 Correct 4 ms 1668 KB Output is correct
13 Correct 5 ms 1804 KB Output is correct
14 Correct 5 ms 1804 KB Output is correct
15 Correct 4 ms 1796 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 5204 KB Output is correct
2 Correct 30 ms 5524 KB Output is correct
3 Correct 28 ms 5760 KB Output is correct
4 Runtime error 22 ms 5296 KB Execution killed with signal 4 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5460 KB Output is correct
2 Correct 28 ms 5780 KB Output is correct
3 Correct 28 ms 5656 KB Output is correct
4 Runtime error 20 ms 5304 KB Execution killed with signal 4 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -