제출 #1291285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291285		am_aadvik	Amusement Park (JOI17_amusement_park)	C++20	10 / 100	3097 ms	2128 KiB

Joi

#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 1

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <set>
#include<vector>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

//grader
#if (SUBMIT == 0)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);

static int32_t N, M, A[MMAX], B[MMAX], P, T;
static long long X;
static int given_msg[NMAX];
static int pos, n_move;
static set<pair<int, int> > edges;

void WrongAnswer(int e)
{
	printf("Wrong Answer[%d]\n", e);
	exit(1);
}

void MessageBoard(int attr, int msg)
{
	if (!(0 <= attr && attr <= N - 1)) {
		WrongAnswer(1);
	}
	if (given_msg[attr] != -1) {
		WrongAnswer(2);
	}
	if (!(msg == 0 || msg == 1)) {
		WrongAnswer(3);
	}
	given_msg[attr] = msg;
}

int Move(int dest)
{
	if (!(0 <= dest && dest <= N - 1)) {
		WrongAnswer(6);
	}
	if (!edges.count({ pos, dest })) {
		WrongAnswer(7);
	}
	++n_move;
	if (n_move > MOVEMAX) {
		WrongAnswer(8);
	}
	pos = dest;
	return given_msg[pos];
}

int32_t main(void)
{
	int i;
	long long max_code;

	scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
	for (int i = 0; i < M; ++i) {
		scanf("%d%d", &(A[i]), &(B[i]));
		edges.insert({ A[i], B[i] });
		edges.insert({ B[i], A[i] });
	}
	for (int i = 0; i < N; ++i) {
		given_msg[i] = -1;
	}

	Joi((int32_t)N, (int32_t)M, A, B, X, (int32_t)T);

	for (i = 0; i < N; ++i) {
		if (given_msg[i] == -1) {
			WrongAnswer(4);
		}
	}

	n_move = 0;
	pos = P;
	long long answer = Ioi(N, M, A, B, P, given_msg[P], T);

	if (answer != X) {
		WrongAnswer(5);
	}

	printf("Accepted : #move=%d\n", n_move);
	return 0;
}
#endif

//-------------------------------------------------------------------------------------------------------
//                                             code starts here

//common code
vector<int> g[200005];
vector<bool> vis;
vector<int> label(int n) {
	queue<pair<int, int>> q; q.push({ 0, 0 });
	vector<int> lb(n, -1); lb[0] = 0;
	while (!q.empty()) {
		auto f = q.front(); q.pop();
		for (auto x : g[f.first])
			if (lb[x] == -1) lb[x] = f.second + 1, q.push({ x, lb[x] });
	}
	return lb;
}

// joi
#if SUBMIT <= 1
#if SUBMIT == 1
void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
void MessageBoard(int32_t attr, int32_t msg);
#endif
int dfsA(int node, int r, int c, vector<int> &res) {
	vis[node] = 1; res[node] = ((r & (1ll << c)) > 0); c += 1;
	for (auto x : g[node])
		if ((c < 60) && (!vis[x])) 
			c = dfsA(x, r, c, res);
	return c;
}
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long r, int32_t t) {
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back((int)b[i]),
		g[(int)b[i]].push_back((int)a[i]);
	vector<int> lab = label(n), res(n, 0);
	if ((*max_element(lab.begin(), lab.end()) < 59))
		vis.assign(n, 0), dfsA(0, r, 0, res);
	else 
		for (int i = 0; i < n; ++i)
			res[i] = ((r & (1ll << (int)(lab[i] % 60ll))) > 0ll);
	for (int i = 0; i < n; ++i) MessageBoard(i, res[i]);
}
#endif

//ioi
#if SUBMIT % 2 == 0
#if SUBMIT == 2
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);
int Move(int32_t dest);
#endif
vector<int> res;
int dfsB(int node, int c, int s) {
	vis[node] = 1, c += 1;
	if (node == s) res.push_back(0);
	else res.push_back(Move(node));
	for (auto x : g[node])
		if ((c < 60) && (!vis[x]))
			c = dfsB(x, c, s), Move(node);
	return c;
}
long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t) {
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back((int)b[i]),
		g[(int)b[i]].push_back((int)a[i]);
	auto lab = label(n);
	int cur = v, op = p;
	while ((lab[p] % 60) != 0)
		for(auto x: g[p]) 
			if (lab[x] == (lab[p] - 1)) {
				cur = Move(x); op = p = x; break;
			}
	if ((*max_element(lab.begin(), lab.end()) < 59)) {
		res.clear(), vis.assign(n, 0), dfsB(p, 0, p);
		int ans = cur;
		for (int i = 1; i < 60; ++i)
			ans += (res[i] * (1ll << i));
		return ans;
	}
	else {
		res = { p };
		while (1) {
			if ((p % 60) == 1) break;
			int np = p;
			for (auto x : g[p])
				if (lab[x] == (lab[p] - 1)) {
					res.push_back(x); p = x; break;
				}
			if (p == np) break;
		}
		if (res.size() != 60) {
			p = op; res = { p };
			while (1) {
				if((p % 60) == 59) break;
				for (auto x : g[p])
					if (lab[x] == (lab[p] + 1)) {
						res.push_back(x); p = x; break;
					}
			}
		}
	}
	vector<pair<int, int>> val = { {op%60, cur} };
	for (int i = 1; i < res.size(); ++i)
		val.push_back({ res[i]%60, Move(res[i]) });
	sort(val.begin(), val.end());
	int ans = 0;
	for (int i = 0; i < 60; ++i)
		ans += (val[i].second * (1ll << i));
	return ans;
}
#endif

Ioi

#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 2

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <set>
#include<vector>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

//grader
#if (SUBMIT == 0)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);

static int32_t N, M, A[MMAX], B[MMAX], P, T;
static long long X;
static int given_msg[NMAX];
static int pos, n_move;
static set<pair<int, int> > edges;

void WrongAnswer(int e)
{
	printf("Wrong Answer[%d]\n", e);
	exit(1);
}

void MessageBoard(int attr, int msg)
{
	if (!(0 <= attr && attr <= N - 1)) {
		WrongAnswer(1);
	}
	if (given_msg[attr] != -1) {
		WrongAnswer(2);
	}
	if (!(msg == 0 || msg == 1)) {
		WrongAnswer(3);
	}
	given_msg[attr] = msg;
}

int Move(int dest)
{
	if (!(0 <= dest && dest <= N - 1)) {
		WrongAnswer(6);
	}
	if (!edges.count({ pos, dest })) {
		WrongAnswer(7);
	}
	++n_move;
	if (n_move > MOVEMAX) {
		WrongAnswer(8);
	}
	pos = dest;
	return given_msg[pos];
}

int32_t main(void)
{
	int i;
	long long max_code;

	scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
	for (int i = 0; i < M; ++i) {
		scanf("%d%d", &(A[i]), &(B[i]));
		edges.insert({ A[i], B[i] });
		edges.insert({ B[i], A[i] });
	}
	for (int i = 0; i < N; ++i) {
		given_msg[i] = -1;
	}

	Joi((int32_t)N, (int32_t)M, A, B, X, (int32_t)T);

	for (i = 0; i < N; ++i) {
		if (given_msg[i] == -1) {
			WrongAnswer(4);
		}
	}

	n_move = 0;
	pos = P;
	long long answer = Ioi(N, M, A, B, P, given_msg[P], T);

	if (answer != X) {
		WrongAnswer(5);
	}

	printf("Accepted : #move=%d\n", n_move);
	return 0;
}
#endif

//-------------------------------------------------------------------------------------------------------
//                                             code starts here

//common code
vector<int> g[200005];
vector<bool> vis;
vector<int> label(int n) {
	queue<pair<int, int>> q; q.push({ 0, 0 });
	vector<int> lb(n, -1); lb[0] = 0;
	while (!q.empty()) {
		auto f = q.front(); q.pop();
		for (auto x : g[f.first])
			if (lb[x] == -1) lb[x] = f.second + 1, q.push({ x, lb[x] });
	}
	return lb;
}

// joi
#if SUBMIT <= 1
#if SUBMIT == 1
void Joi(int32_t N, int32_t M, int32_t A[], int32_t B[], long long X, int32_t T);
void MessageBoard(int32_t attr, int32_t msg);
#endif
int dfsA(int node, int r, int c, vector<int> &res) {
	vis[node] = 1; res[node] = ((r & (1ll << c)) > 0); c += 1;
	for (auto x : g[node])
		if ((c < 60) && (!vis[x])) 
			c = dfsA(x, r, c, res);
	return c;
}
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long r, int32_t t) {
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back((int)b[i]),
		g[(int)b[i]].push_back((int)a[i]);
	vector<int> lab = label(n), res(n, 0);
	if ((*max_element(lab.begin(), lab.end()) < 59))
		vis.assign(n, 0), dfsA(0, r, 0, res);
	else 
		for (int i = 0; i < n; ++i)
			res[i] = ((r & (1ll << (int)(lab[i] % 60ll))) > 0ll);
	for (int i = 0; i < n; ++i) MessageBoard(i, res[i]);
}
#endif

//ioi
#if SUBMIT % 2 == 0
#if SUBMIT == 2
long long Ioi(int32_t N, int32_t M, int32_t A[], int32_t B[], int32_t P, int32_t V, int32_t T);
int Move(int32_t dest);
#endif
vector<int> res;
int dfsB(int node, int c, int s) {
	vis[node] = 1, c += 1;
	if (node == s) res.push_back(0);
	else res.push_back(Move(node));
	for (auto x : g[node])
		if ((c < 60) && (!vis[x]))
			c = dfsB(x, c, s), Move(node);
	return c;
}
long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t) {
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back((int)b[i]),
		g[(int)b[i]].push_back((int)a[i]);
	auto lab = label(n);
	int cur = v, op = p;
	while ((lab[p] % 60) != 0)
		for(auto x: g[p]) 
			if (lab[x] == (lab[p] - 1)) {
				cur = Move(x); op = p = x; break;
			}
	if ((*max_element(lab.begin(), lab.end()) < 59)) {
		res.clear(), vis.assign(n, 0), dfsB(p, 0, p);
		int ans = cur;
		for (int i = 1; i < 60; ++i)
			ans += (res[i] * (1ll << i));
		return ans;
	}
	else {
		res = { p };
		while (1) {
			if ((p % 60) == 1) break;
			int np = p;
			for (auto x : g[p])
				if (lab[x] == (lab[p] - 1)) {
					res.push_back(x); p = x; break;
				}
			if (p == np) break;
		}
		if (res.size() != 60) {
			p = op; res = { p };
			while (1) {
				if((p % 60) == 59) break;
				for (auto x : g[p])
					if (lab[x] == (lab[p] + 1)) {
						res.push_back(x); p = x; break;
					}
			}
		}
	}
	vector<pair<int, int>> val = { {op%60, cur} };
	for (int i = 1; i < res.size(); ++i)
		val.push_back({ res[i]%60, Move(res[i]) });
	sort(val.begin(), val.end());
	int ans = 0;
	for (int i = 0; i < 60; ++i)
		ans += (val[i].second * (1ll << i));
	return ans;
}
#endif

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