oj.uz

Submission #676954

# Submission time Handle Problem Language Result Execution time Memory
676954 2023-01-01T18:03:53 Z ymm Amusement Park (JOI17_amusement_park) C++17
10 / 100
 22 ms 4432 KB 
#include "Joi.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace shared_joi {
	const int M = 60;
	const int N = 16384;
	vector<int> A[N];
	int par[N], dis[N];
	bool dia[N];
	int bit[N];
	int s, t;
	int n;

	namespace dsu {
		int par[N];
		int rt(int v) {return par[v]==-1?v:(par[v]=rt(par[v]));}
		bool unite(int v, int u) {
			v = rt(v);
			u = rt(u);
			if (v == u)
				return 0;
			par[u] = v;
			return 1;
		}
	}

	pii dfs(int v, int p, int h) {
		par[v] = p;
		dis[v] = h;
		pii ans = {h, v};
		for (int u : A[v]) {
			if (u == p)
				continue;
			ans = max(ans, dfs(u, v, h+1));
		}
		return ans;
	}
	
	vector<int> ord;

	void dfs2(int v, int p, int &rem) {
		ord.push_back(v);
		int d = -1;
		for (int u : A[v]) {
			if (u == p)
				continue;
			if (dia[u]) {
				d = u;
				continue;
			}
			if (!rem)
				continue;
			--rem;
			dfs2(u, v, rem);
			ord.push_back(v);
		}
		if (d != -1)
			dfs2(d, v, rem);
	}

	void init(int _n, int m, int V[], int U[]) {
		n = _n;
		memset(dsu::par, -1, sizeof(dsu::par));
		Loop (i,0,m) {
			if (!dsu::unite(V[i], U[i]))
				continue;
			A[V[i]].push_back(U[i]);
			A[U[i]].push_back(V[i]);
		}
		s = dfs(0, -1, 0).second;
		t = dfs(s, -1, 0).second;
		for (int v = t; v != -1; v = par[v])
			dia[v] = 1;
		if (dis[t] >= (M-1)) {
			Loop (i,0,n)
				bit[i] = dis[i]%M;
			return;
		}
		memset(bit, -1, sizeof(bit));
		dfs2(s, -1, *new int((M-1)-dis[t]));
		int nxt = 0;
		for (int v : ord) {
			if (bit[v] == -1)
				bit[v] = nxt++;
		}
		assert(nxt == M);
	}
}
using namespace shared_joi;

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	init(N, M, A, B);
	Loop (i,0,N) {
		int x = bit[i] == -1? 0: ((X >> bit[i]) & 1);
		MessageBoard(i, x);
	}
}

#include "Ioi.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace shared_ioi {
	const int M = 60;
	const int N = 16384;
	vector<int> A[N];
	int par[N], dis[N];
	bool dia[N];
	int bit[N];
	int s, t;
	int n;

	namespace dsu {
		int par[N];
		int rt(int v) {return par[v]==-1?v:(par[v]=rt(par[v]));}
		bool unite(int v, int u) {
			v = rt(v);
			u = rt(u);
			if (v == u)
				return 0;
			par[u] = v;
			return 1;
		}
	}

	pii dfs(int v, int p, int h) {
		par[v] = p;
		dis[v] = h;
		pii ans = {h, v};
		for (int u : A[v]) {
			if (u == p)
				continue;
			ans = max(ans, dfs(u, v, h+1));
		}
		return ans;
	}
	
	vector<int> ord;

	void dfs2(int v, int p, int &rem) {
		ord.push_back(v);
		int d = -1;
		for (int u : A[v]) {
			if (u == p)
				continue;
			if (dia[u]) {
				d = u;
				continue;
			}
			if (!rem)
				continue;
			--rem;
			dfs2(u, v, rem);
			ord.push_back(v);
		}
		if (d != -1)
			dfs2(d, v, rem);
	}

	void init(int _n, int m, int V[], int U[]) {
		n = _n;
		memset(dsu::par, -1, sizeof(dsu::par));
		Loop (i,0,m) {
			if (!dsu::unite(V[i], U[i]))
				continue;
			A[V[i]].push_back(U[i]);
			A[U[i]].push_back(V[i]);
		}
		s = dfs(0, -1, 0).second;
		t = dfs(s, -1, 0).second;
		for (int v = t; v != -1; v = par[v])
			dia[v] = 1;
		if (dis[t] >= (M-1)) {
			Loop (i,0,n)
				bit[i] = dis[i]%M;
			return;
		}
		memset(bit, -1, sizeof(bit));
		dfs2(s, -1, *new int((M-1)-dis[t]));
		int nxt = 0;
		for (int v : ord) {
			if (bit[v] == -1)
				bit[v] = nxt++;
		}
		assert(nxt == M);
	}
}
using namespace shared_ioi;

int cur;
void mov(int v)
{
	cur = Move(v);
}

ll ans = 0;
void up(int bit, bool val)
{
	ans |= (ll)val << bit;
}

void solve1(int v)
{
	if (dis[v] >= (M-1)) {
		up(bit[v], cur);
		Loop (_,0,(M-1)) {
			mov(par[v]);
			v = par[v];
			up(bit[v], cur);
		}
	} else {
		while (v != s) {
			mov(par[v]);
			v = par[v];
		}
		up(bit[v], cur);
		Loop (_,0,(M-1)) {
			for (int u : A[v]) {
				if (u == par[v] || !dia[u])
					continue;
				mov(u);
				v = u;
				up(bit[v], cur);
				break;
			}
		}
	}
}

void solve2(int v)
{
	while (v != s) {
		mov(par[v]);
		v = par[v];
	}
	up(bit[v], cur);
	Loop (i,1,ord.size()) {
		int u = ord[i];
		mov(u);
		v = u;
		up(bit[v], cur);
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
	init(N, M, A, B);
	Loop (i,0,N)
	cur = V;
	if (dis[t] >= (M-1))
		solve1(P);
	else
		solve2(P);
	return ans;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 2 ms 1544 KB Output is correct
3 Correct 2 ms 1544 KB Output is correct
4 Correct 2 ms 1948 KB Output is correct
5 Correct 3 ms 1948 KB Output is correct
6 Correct 3 ms 1948 KB Output is correct
7 Correct 2 ms 1956 KB Output is correct
8 Correct 4 ms 1948 KB Output is correct
9 Correct 11 ms 4408 KB Output is correct
10 Correct 10 ms 4432 KB Output is correct
11 Correct 9 ms 4432 KB Output is correct
12 Correct 2 ms 1544 KB Output is correct
13 Correct 2 ms 1544 KB Output is correct
14 Correct 1 ms 1536 KB Output is correct
15 Correct 2 ms 1544 KB Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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