Submission #26590

#	Time	Username	Problem	Language	Result	Execution time	Memory
26590		Bruteforceman	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	155 ms	8696 KiB

Joi

#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
vector <int> g[10010];
vector <int> t[10010];
bool vis[10010];

const int bit = 60; // 60;

int nodes;
int par[10010];
int ans[10010];

void dfs(int x) {
	vis[x] = true;
	for(auto i : g[x]) {
		if(vis[i] == false) {
			t[x].push_back(i);
			par[i] = x;
			dfs(i);
		}
	}
}

int cnt;
bool good[10010];
void get_first(int x) {
	if(cnt >= bit) {
		return ;
	}
	good[x] = true;
	++cnt;
	for(auto i : t[x]) {
		get_first(i);
	}
}
int degree(int x) {
	int cnt = 0;
	for(auto i : t[x]) {
		cnt += good[i];
	}
	if(x != 0) {
		cnt += good[par[x]];
	}
	return cnt;
}
void solve(int x) {
	int leaf = -1;
	for(int i = 0; i < nodes; i++) {
		if(good[i] && par[x] != i) {
			if(degree(i) == 1) {
				leaf = i;
				break;
			}
		}
	}
	good[x] = true;
	good[leaf] = false;
	ans[x] = ans[leaf];
	for(auto i : t[x]) {
		solve(i);
	}
	good[x] = false;
	good[leaf] = true;
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i = 0; i < N; i++) {
		g[i].clear();
		t[i].clear();
		good[i] = false;
		vis[i] = false;
		ans[i] = -1;
	}
	nodes = N;
	for(int i = 0; i < M; i++) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	for(int i = 0; i < N; i++) {
		sort(g[i].begin(), g[i].end());
	}
	
	dfs(0);
	get_first(0);
	
	int cur = 0;
	for(int i = 0; i < N; i++) {
		if(good[i]) {
			ans[i] = cur++;
		}
	}
	for(int i = 0; i < N; i++) {
		if(good[i] == false && good[par[i]] == true) {
			solve(i);
		}
	}
	for(int i = 0; i < N; i++) {
		int val = (X >> ans[i]) & 1;
		MessageBoard(i, val);
	}
	return ;
}

Ioi

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

#define g G
#define t TT
#define vis Vis
#define bit Bit
#define nodes Nodes
#define par Par
#define ans Ans
#define dfs Dfs
#define good Good
#define get_first Get_first
#define degree Degree
#define cnt Cnt
#define solveNow SolveNow
#define solve Solve

vector <int> g[10010];
vector <int> t[10010];
vector <int> Tree[10010];
bool vis[10010];

const int bit = 60; // 60;

int nodes;
int par[10010];
int ans[10010];

void dfs(int x) {
	vis[x] = true;
	for(auto i : g[x]) {
		if(vis[i] == false) {
			t[x].push_back(i);
			Tree[x].push_back(i);
			Tree[i].push_back(x);
			par[i] = x;
			dfs(i);
		}
	}
}

int cnt;
bool good[10010];
void get_first(int x) {
	if(cnt >= bit) {
		return ;
	}
	good[x] = true;
	++cnt;
	for(auto i : t[x]) {
		get_first(i);
	}
}
int degree(int x) {
	int cnt = 0;
	for(auto i : t[x]) {
		cnt += good[i];
	}
	if(x != 0) {
		cnt += good[par[x]];
	}
	return cnt;
}

int src;
long long Res;
int init;
set <int> s;

void shit(int x, int parent, int val) {
	if(val) {
		Res |= (1LL << ans[x]);
	}
	for(auto i : Tree[x]) {
		if(good[i] == true && i != parent) {
			shit(i, x, Move(i));
			Move(x);
		}
	}
}
void solveNow() {
	Res = 0;
	shit(src, -1, init);
}

void solve(int x) {
	int leaf = 0;
	for(int i = 0; i < nodes; i++) {
		if(good[i] && par[x] != i) {
			if(degree(i) == 1) {
				leaf = i;
				break;
			}
		}
	}
	good[x] = true;
	good[leaf] = false;
	ans[x] = ans[leaf];
	
	if(x == src) {
		solveNow();
	}
	for(auto i : t[x]) {
		solve(i);
	}
	good[x] = false;
	good[leaf] = true;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	for(int i = 0; i < N; i++) {
		g[i].clear();
		t[i].clear();
		Tree[i].clear();
		good[i] = false;
		vis[i] = false;
		ans[i] = -1;
	}
	nodes = N;
	for(int i = 0; i < M; i++) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	for(int i = 0; i < N; i++) {
		sort(g[i].begin(), g[i].end());
	}
	src = P;
	init = V;
	
	dfs(0);
	get_first(0);
	int cur = 0;
	for(int i = 0; i < N; i++) {
		if(good[i]) {
			ans[i] = cur++;
		}
	}
	if(good[src] == true) {
		solveNow();
	}
	for(int i = 0; i < N; i++) {
		if(good[i] == false && good[par[i]] == true) {
			solve(i);
		}
	}

	return Res;
}

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