oj.uz

Submission #112826

# Submission time Handle Problem Language Result Execution time Memory
112826 2019-05-22T06:19:57 Z MAMBA Amusement Park (JOI17_amusement_park) C++17
0 / 100
 31 ms 4444 KB 
#include <bits/stdc++.h>
#include "Joi.h"

using namespace std;

typedef long long ll;
typedef vector<int> vi;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back

constexpr int N = 1e4 + 10;

int root = -1, len = -1;
int lvl[N], val[N];
vi adj[N];
bitset<N << 1> m1, m2;

void dfs0(int v, int a[], int b[]) {
	m1[v] = true;
	for (auto e : adj[v]) {
		int u = v ^ a[e] ^ b[e];
		if (!m1[u]) {
			m2[e] = true;
			dfs0(u, a, b);
		}
	}
}

void dfs1(int v, int par = -1) {
	for (auto e : adj[v])
		if (par ^ e) {
			lvl[e] = lvl[v] + 1;
			dfs1(e , v);
		}
}

int cnt;
bool dfs2(int v , int dst , int par = -1) {
	for (auto e :adj[v])
		if (e ^ par && dfs2(e  , dst , v)) {
			m1[v] = true;
			val[v] = ++cnt;
			return true;
		}
}

void dfs3(int v, int par = -1) {
	if (!m1[v]) val[v] = ++cnt;
	for (auto e :adj[v]) 
		if (e ^ par)
			dfs3(e , v);
}

inline void init(int n , int m , int a[], int b[]) {
	rep(i , 0 , m) 
	{	adj[a[i]].pb(i);
		adj[b[i]].pb(i);
	}
	dfs0(0, a, b);
	rep(i , 0 , n) adj[i].clear();
	rep(i , 0 , m) if(m2[i]) {
		adj[a[i]].pb(b[i]);
		adj[b[i]].pb(a[i]);
	}
	lvl[0] = 1;
	dfs1(0);
	root = max_element(lvl , lvl + n) - lvl;
	lvl[root] = 1;
	dfs1(root);
	len = *max_element(lvl , lvl + n);
	return;
}

void Joi(int n, int m, int a[] , int b[], ll x , int t) {
	init(n , m , a , b);
	if (len >= 60) {
		rep(i , 0 , n) 
			MessageBoard(i , (x >> (lvl[i] % 60)) & 1);		
	}
	else {
		int root2 = max_element(lvl , lvl + n) - lvl;
		m1.reset();
		dfs2(root , root2);
		dfs3(root);
		rep(i , 0 , n)
			MessageBoard(i , (x >> (val[i] - 1)) & 1);	
	}
	return;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back

constexpr int N = 1e4 + 10;

int root = -1, len = -1;
int lvl[N], val[N];
vi adj[N];
bitset<N << 1> m1, m2;

void dfs0(int v, int a[], int b[]) {
	m1[v] = true;
	for (auto e : adj[v]) {
		int u = v ^ a[e] ^ b[e];
		if (!m1[u]) {
			m2[e] = true;
			dfs0(u, a, b);
		}
	}
}

void dfs1(int v, int par = -1) {
	for (auto e : adj[v])
		if (par ^ e) {
			lvl[e] = lvl[v] + 1;
			dfs1(e , v);
		}
}

int cnt;
bool dfs2(int v , int dst , int par = -1) {
	for (auto e :adj[v])
		if (e ^ par && dfs2(e  , dst , v)) {
			m1[v] = true;
			val[v] = ++cnt;
			return true;
		}
}

void dfs3(int v, int par = -1) {
	if (!m1[v]) val[v] = ++cnt;
	for (auto e :adj[v]) 
		if (e ^ par)
			dfs3(e , v);
}

inline void init(int n , int m , int a[], int b[]) {
	rep(i , 0 , m) 
	{	adj[a[i]].pb(i);
		adj[b[i]].pb(i);
	}
	dfs0(0, a, b);
	rep(i , 0 , n) adj[i].clear();
	rep(i , 0 , m) if(m2[i]) {
		adj[a[i]].pb(b[i]);
		adj[b[i]].pb(a[i]);
	}
	lvl[0] = 1;
	dfs1(0);
	root = max_element(lvl , lvl + n) - lvl;
	lvl[root] = 1;
	dfs1(root);
	len = *max_element(lvl , lvl + n);
	return;
}

ll res = 0;

void dfs4(int v, int &p , int &me, int par = -1) {
	res |= (1ll * me) << (val[v] - 1);
	for (auto e : adj[v]) 
		if (e ^ par && !m1[e] && val[e] <= 60) {
			me = Move(e);
			p = e;
			dfs4(e , p , me , v);
		}
	for (auto e :adj[v])
		if (e ^ par && m1[e] && val[e] <= 60) {
			me = Move(e);
			p = e;
			dfs4(e , p  , me , v);
		}
	if (!m1[v]) {
		me = Move(par);
		p = par;
	}
}


ll Ioi(int n, int m, int a[], int b[], int p ,int me, int t) {
	init(n , m , a , b);
	if (len >= 60) {
		m1.reset();
		dfs2(p , root);
		if (lvl[p] >= 60) {
			rep(i , 0 , 60) {
				res |= (1ll * me) << (lvl[p] % 60);
				for (auto e : adj[p])
					if (m1[e]) {
						me = Move(e);
						m1[p] = false;
						p = e;
						break;
					}
			}
		}
		else {
			while(true) {
				bool flag = false;
				for (auto e : adj[p]) 
					if (m1[e]) {
						me = Move(e);
						m1[p] = false;
						flag = true;
						p = e;
						break;
					}
				if (!flag) break;
			}
			int root2 = max_element(lvl , lvl + n) - lvl;
			dfs2(p , root2);
			rep(i , 0 , 60) {
				res |= (1ll * me) << (lvl[p] % 60);
				for (auto e : adj[p])
					if (m1[e]) {
						me = Move(e);
						m1[p] = false;
						p = e;
						break;
					}
			}
		}
		return res;		
	}
	////////////////////////////////////////
	int root2 = max_element(lvl , lvl + n) - lvl;


	m1.reset();
	dfs2(p  ,root);

	while(true) {
		bool flag = false;
		for (auto e : adj[p]) 
			if (m1[e]) {
				me = Move(e);
				m1[p] = false;
				flag = true;
				p = e;
				break;
			}
		if (!flag) break;
	}
	cnt = 0;
	m1.reset();
	dfs2(root , root2);
	dfs3(root);
	m1.reset();
	dfs4(root, p , me);
	return res;
}

Compilation message

Joi.cpp: In function 'bool dfs2(int, int, int)':
Joi.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Ioi.cpp: In function 'bool dfs2(int, int, int)':
Ioi.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1280 KB Output is correct
2 Incorrect 4 ms 1380 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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