Submission #394657

#	Time	Username	Problem	Language	Result	Execution time	Memory
394657		jsannemo	Amusement Park (JOI17_amusement_park)	C++14	28 / 100	38 ms	5304 KiB

Joi

#include "Joi.h"

#include <vector>
#include <map>

using namespace std;

static vector<vector<int>> adj;

static vector<int> ord;
static vector<int> vis;
static vector<bool> seen;

static void dfs(int at) {
	seen[at] = true;
	vis.push_back(at);
	ord.push_back(at);
	for (int it : adj[at]) {
		if (seen[it]) continue;
		dfs(it);
		ord.push_back(at);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	adj.resize(N);
	seen.resize(N);
	for (int i = 0; i < M; i ++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0);
	ord.pop_back();
	for(int i = 0; i < N - 60; i++){
		int b = (i % 60);
		MessageBoard(vis[i], (X >> b) & 1);
	}
	for(int i = N - 60; i < N; i++){
		int b = i - (N - 60);
		MessageBoard(vis[i], (X >> b) & 1);
	}
}

Ioi

#include "Ioi.h"

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

static vector<vector<int>> adj;

static vector<int> ord;
static vector<int> vis;
static vector<bool> seen;

static void dfs(int at) {
	seen[at] = true;
	vis.push_back(at);
	ord.push_back(at);
	for (int it : adj[at]) {
		if (seen[it]) continue;
		dfs(it);
		ord.push_back(at);
	}
}

static map<int, int> bits;
static map<int, int> bit;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	adj.resize(N);
	seen.resize(N);
	for (int i = 0; i < M; i ++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0);
	ord.pop_back();
	for(int i = 0; i < N - 60; i++){
		int b = (i % 60);
		bit[vis[i]] = b;
	}
	for(int i = N - 60; i < N; i++){
		int b = i - (N - 60);
		bit[vis[i]] = b;
	}

	int idx = find(vis.begin(), vis.end(), P) - vis.begin();
	int d = 1;
	if (idx < N - 60) d = -1;

	int at = find(ord.begin(), ord.end(), P) - ord.begin();
	while (bits.size() != 60) {
		at = (at + d + ord.size()) % ord.size();
		cerr << "go to " << ord[at] << " get bit " << bit[ord[at]] << endl;
		bits[bit[ord[at]]] = Move(ord[at]);
	}

	long long X = 0;
	for (int i = 0; i < 60; ++i) {
		X |= (long long)bits[i] << i;
	}
	return X;
}

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