Submission #205566

#	Time	Username	Problem	Language	Result	Execution time	Memory
205566		amoo_safar	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	62 ms	10752 KiB

Joi

#ifndef safar
#include<Joi.h>
#endif

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

typedef long long ll;
const int N = 1e4 + 10;
const int Log = 60;

static vector<int> G[N], Gd, T[N], O;
static int mk[N], id[N];
static int fn = 0;
void dfs(int u){
	if(fn == Log) return ;
	id[u] = fn;
	fn ++;
	mk[u] = 1;
	Gd.pb(u);
	for(auto adj : G[u]) if(!mk[adj]) dfs(adj);
}
void DFS(int u){
	O.pb(u);
	mk[u] = 1;
	for(auto adj : G[u]){
		if(!mk[adj]) DFS(adj);
	}
}

void DFS2(int u){
	mk[u] = 1;
	for(auto adj : G[u]){
		if(!mk[adj]){
			T[adj].pb(adj);
			for(auto x : T[u]) T[adj].pb(x);
			id[adj] = id[T[adj].back()];
			T[adj].pop_back();
			DFS2(adj);
		}
	}
}
void Joi(int n, int m, int A[], int B[], ll X, int Tc){
	for(int i = 0; i < m; i++){
		G[A[i]].pb(B[i]);
		G[B[i]].pb(A[i]);	
	}
	dfs(1);
	for(auto x : Gd){
		fill(mk, mk + N, 1);
		for(auto x : Gd) mk[x] = 0;
		O.clear();
		DFS(x);
		for(auto y : O) T[x].pb(y);
	}
	memset(mk, 0, sizeof mk);
	for(auto x : Gd) mk[x] = 1;
	for(auto x : Gd) DFS2(x);

	assert(n >= 60);
	assert(-1 <= Tc);
	for(int i = 0; i < n; i++) MessageBoard(i, X >> id[i] & 1);
	return ;
}

Ioi

#ifndef safar
#include<Ioi.h>
#endif

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

typedef long long ll;
const int N = 1e4 + 10;
const int Log = 60;

static vector<int> G[N], Gd, T[N], O;
static int mk[N], id[N];
static int fn = 0;
void dfs(int u){
	if(fn == Log) return ;
	id[u] = fn;
	fn ++;
	mk[u] = 1;
	Gd.pb(u);
	for(auto adj : G[u]) if(!mk[adj]) dfs(adj);
}
void DFS(int u){
	O.pb(u);
	mk[u] = 1;
	for(auto adj : G[u]){
		if(!mk[adj]) DFS(adj);
	}
}

void DFS2(int u){
	mk[u] = 1;
	for(auto adj : G[u]){
		if(!mk[adj]){
			T[adj].pb(adj);
			for(auto x : T[u]) T[adj].pb(x);
			id[adj] = id[T[adj].back()];
			T[adj].pop_back();
			DFS2(adj);
		}
	}
}
static ll Ans = 0;
void Find(int u){
	mk[u] = 1;
	for(auto adj : G[u]){
		if(mk[adj]) continue;
		ll res = Move(adj);
		if(res) Ans |= (1ll << id[adj]);
		Find(adj);
		Move(u);
	}
}

ll Ioi(int n, int m, int A[], int B[], int P, int V, int Tc){
	for(int i = 0; i < m; i++){
		G[A[i]].pb(B[i]);
		G[B[i]].pb(A[i]);	
	}
	dfs(1);
	for(auto x : Gd){
		fill(mk, mk + N, 1);
		for(auto x : Gd) mk[x] = 0;
		O.clear();
		DFS(x);
		for(auto y : O) T[x].pb(y);
	}
	memset(mk, 0, sizeof mk);
	for(auto x : Gd) mk[x] = 1;
	for(auto x : Gd) DFS2(x);

	if(V) Ans |= (1ll << id[P]);
	assert(n >= 60);
	assert(-1 <= Tc);
	fill(mk, mk + N, 1);
	for(auto x : T[P]) mk[x] = 0;
	Find(P);
	return Ans;
}

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