Submission #1284039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284039		baotoan655	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	17 ms	2892 KiB

Joi

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

const int Z = 1e4;

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

long long x;

int init(int u, int d = 0) {
    vis[u] = 1;
    e[u] = d;
    for(int v : g[u]) if(!vis[v]) {
            e[u] = max(e[u], init(v, d + 1));
            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) {
    MessageBoard(u, bool(x & (1LL << (++dfsTimer % 60))));
    for(const int &v : h[u]) dfs(v);
}

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

Ioi

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

const int N = 1e4;

int L[N], R[N], dfsTimer, e[N], p[N];
vector<int> g[N], h[N];

int init(int u, int d = 0) {
	L[u] = ++dfsTimer;
	e[u] = d;
	for(int v : g[u]) if(!L[v]) {
		p[v] = u;
		e[u] = max(e[u], init(v, d + 1));
		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);
	}
}

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

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