제출 #533114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533114		sidon	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	31 ms	5792 KiB

Joi

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;

namespace JOI {
	const int Z = 1e4;

	int L[Z], R[Z], dfsTimer, d[Z], e[Z];
	bool vis[Z];
	vector<int> g[Z], h[Z];

	long long x;

	int init(int u) {
		L[u] = 1;
		for(const int &v : g[u]) if(!L[v]) {
			e[v] = d[v] = d[u] + 1;
			e[u] = max(e[u], init(v));
			h[u].push_back(v);
		}
		sort(begin(h[u]), end(h[u]), [&](const int &i, const int &j) {
			return e[i] > e[j];
		});
		return e[u];
	}

	void dfs(int u) {
		L[u] = ++dfsTimer;
		for(const int &v : h[u]) dfs(v);
		R[u] = 1+dfsTimer;

		MessageBoard(u, bool(x & (1LL<<(L[u] % 60))));
	}
	void Joi(int N, int M, int A[], int B[], long long X, int _T) {
		x = X;
		for(int i = 0; i < M; ++i) {
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
		init(0);
		dfs(0);
	}
};

void Joi(int N, int M, int A[], int B[], long long X, int _T) {
	JOI::Joi(N, M, A, B, X, _T);
}

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;

namespace IOI {
	const int Z = 1e4;

	int L[Z], R[Z], dfsTimer, d[Z], e[Z], p[Z];
	bool vis[Z];
	vector<int> g[Z], h[Z];

	int init(int u) {
		L[u] = ++dfsTimer;
		for(const int &v : g[u]) if(!L[v]) {
			p[v] = u;
			e[v] = d[v] = d[u] + 1;
			e[u] = max(e[u], init(v));
			h[u].push_back(v);
		}
		sort(begin(h[u]), end(h[u]), [&](const int &i, const int &j) {
			return e[i] > e[j];
		});
		R[u] = 1+dfsTimer;
		return e[u];
	}

	int r;
	vector<pair<int, int>> path;

#define valid(X) (L[r] <= X && X < L[r] + 60)

	void dfs(int u) {
		L[u] = ++dfsTimer;
		for(const int &v : h[u]) {
			if(valid(L[u]) && valid(dfsTimer+1))
				path.emplace_back(u, v);
			dfs(v);
			if(valid(L[u]) && valid(L[v]))
				path.emplace_back(v, u);
		}
		R[u] = 1+dfsTimer;
	}

	long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
		for(int i = 0; i < M; ++i) {
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
		init(0);
		r = P;
		while(R[r] - L[r] < 60)	V = Move(r = p[r]);

		dfs(dfsTimer = 0);

		long long x {};
		set<int> done;

		done.insert(L[r] % 60);
		if(V) x |= 1LL << (L[r] % 60);

		while(size(done) < 60) {
			auto [v, pos] = path.back();
			path.pop_back();

			done.insert(pos = L[v] % 60);
			if(Move(r = v))
				x |= 1LL << pos;
		}
		return x;
	}
};

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	return IOI::Ioi(N, M, A, B, P, V, T);
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17