Submission #394662

#	Time	Username	Problem	Language	Result	Execution time	Memory
394662		jsannemo	Amusement Park (JOI17_amusement_park)	C++14	28 / 100	61 ms	5432 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; i++){
		int b = (i % 60);
		MessageBoard(vis[i], (X >> b) & 1);
	}
}

Ioi

#include "Ioi.h"

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

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;
static set<int> tovis;

void dfs2(int at) {
	cerr << "at " << at << " with bit " << bit[at] << endl;
	tovis.erase(at);
	for (int it : adj[at]) {
		if (!tovis.count(it)) continue;
		bits[bit[it]] = Move(it);
		dfs2(it);
		if (bits.size() == 60) break;
		Move(at);
	}
	cerr << "backtrack " << at << endl;
}

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; i++){
		int b = (i % 60);
		bit[vis[i]] = b;
	}
	bits[bit[P]] = V;
	map<int, int> occ;
	for (int i = ord.size() - 1; i >= 0; --i) occ[ord[i]] = i;

	int idx = find(vis.begin(), vis.end(), P) - vis.begin();
	cerr << "i am at idx " << idx << " vert " << P << endl;
	int lo = max(0, idx - 59);
	int hi = lo + 59;
	int at1 = occ[vis[lo]], at2 = occ[vis[hi]];

	for (int nlo = max(0, idx - 59); nlo < min(N - 60, idx); ++nlo) {
		int nhi = nlo + 60;
		int nat1 = occ[vis[nlo]], nat2 = occ[vis[nhi]];
		if (nat2 - nat1 < at2 - at1) {
			at1 = nat1, at2 = nat2;
		}
	}
	cerr << "go for " << at1 << " to " << at2 << endl;

	for (int v = at1; v <= at2; ++v) tovis.insert(ord[v]);
	dfs2(P);
	cerr << "got " << bits.size() << endl;

	//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