Submission #51786

#	Time	Username	Problem	Language	Result	Execution time	Memory
51786		ainta	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	43 ms	24416 KiB

Joi

#include "Joi.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define N_ 10100
using namespace std;

struct TTT {
	vector<int>E[N_];
	vector<int>G[N_];
	int Dep[N_], D[N_], C[N_], v[N_], par[N_];
	long long c = 0;
	struct point {
		int a, d;
		bool operator <(const point &p)const {
			return d > p.d;
		}
	};
	void DFS(int a, int pp) {
		C[a] = 1;
		D[a] = 1;
		v[a] = 1;
		vector<point>V;
		for (auto &x : E[a]) {
			if (v[x])continue;
			Dep[x] = Dep[a] + 1;
			DFS(x, a);
			D[a] = max(D[a], D[x] + 1);
			C[a] += C[x];
			par[x] = a;
			V.push_back({ x,D[x] });
		}
		if (!V.empty()) {
			sort(V.begin(), V.end());
			for (auto &x : V) {
				G[a].push_back(x.a);
			}
		}
	}
	int cnt = 0;
	long long xx;
	void Go(int a) {
		MessageBoard(a, (xx >> (cnt % 60)) & 1);
		cnt++;
		for (auto &x : G[a]) {
			Go(x);
		}
	}

}TT;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	TT.xx = X;
	int i;
	for (i = 0; i < M; i++) {
		TT.E[A[i]].push_back(B[i]);
		TT.E[B[i]].push_back(A[i]);
	}
	TT.DFS(0, -1);
	TT.Go(0);
}

Ioi

#include "Ioi.h"

#include <cstdio>
#include <algorithm>
#include <vector>
#define N_ 10100
using namespace std;

vector<int>E[N_];
vector<int>G[N_];
int Dep[N_], D[N_], C[N_], par[N_], v[N_];
long long c = 0;
struct point {
	int a, d;
	bool operator <(const point &p)const {
		return d > p.d;
	}
};
void DFS(int a, int pp) {
	C[a] = 1;
	D[a] = 1;
	v[a] = 1;
	vector<point>V;
	for (auto &x : E[a]) {
		if (v[x])continue;
		Dep[x] = Dep[a] + 1;
		DFS(x, a);
		D[a] = max(D[a], D[x] + 1);
		C[a] += C[x];
		par[x] = a;
		V.push_back({ x,D[x] });
	}
	if (!V.empty()) {
		sort(V.begin(), V.end());
		for (auto &x : V) {
			G[a].push_back(x.a);
		}
	}
}
int cnt = 0, U[N_], Num[N_], Ed[N_], ReNum[N_];
long long xx;
void Go(int a) {
	U[a] = cnt % 60;
	cnt++;
	Num[a] = cnt;
	ReNum[cnt] = a;
	for (auto &x : G[a]) {
		Go(x);
	}
	Ed[a] = cnt;
}
int pv;
long long res;
void Add(int a, int x) {
	res += (1ll << U[a])*x;
}
void Calc(int a, int pp) {
	int ck = 0;
	if (a == pv)return;
	for (auto &x : G[a]) {
		if (Num[x] > 60)continue;
		if (Num[x] <= Num[pv] && Num[pv] <= Ed[x])continue;
		Add(x, Move(x));
		Calc(x, a);
	}
	for (auto &x : G[a]) {
		if (Num[x] <= Num[pv] && Num[pv] <= Ed[x]) {
			Add(x, Move(x));
			Calc(x, a);
			return;
		}
	}
	if (pp == -1) {
		while (1) {}
	}
	Move(pp);
	return;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	int i;
	for (i = 0; i < M; i++) {
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	DFS(0, -1);
	Go(0);
	int a = P;
	while (a != 0 && D[a] < 60) {
		V = Move(par[a]);
		a = par[a];
	}
	Add(a, V);
	if (D[a] >= 60) {
		for (i = 0; i < 59; i++) {
			V = Move(G[a][0]);
			a = G[a][0];
			Add(a, V);
		}
		return res;
	}
	for (i = 1; i <= 60; i++) {
		if (Dep[ReNum[i]] == D[0]-1)pv = ReNum[i];
	}
	Calc(a,-1);
	return res;
}

Compilation message (stderr)

Ioi.cpp: In function 'void Calc(int, int)':
Ioi.cpp:58:6: warning: unused variable 'ck' [-Wunused-variable]
  int ck = 0;
      ^~

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