Submission #676954

#	Time	Username	Problem	Language	Result	Execution time	Memory
676954		ymm	Amusement Park (JOI17_amusement_park)	C++17	10 / 100	22 ms	4432 KiB

Joi

#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);
	}
}

Ioi

#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
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17