제출 #1291146

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

Joi

#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 1

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

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

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

static int 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(N, M, A, B, X, 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

//common code
vector<int> g[10005], res;
vector<bool> vis, ans;
void dfs(int node) {
	vis[node] = 1, res.push_back(node);
	if (res.size() < 60)
		for (auto x : g[node])
			if ((!vis[x]) && (res.size() < 60))
				dfs(x);
}

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

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]);
	vis.assign(n, 0), ans.assign(n, 0), dfs(0);
	int cur = 0;
	for (auto x : res) ans[x] = ((r & (1ll << cur)) > 0), cur += 1;
	for (int i = 0; i < n; ++i) MessageBoard((int32_t)i, (int32_t)ans[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> uni;
bool dfs2(int node) {
	if (node == 0) return 1;
	vis[node] = 1, res.push_back(node);
	for (auto x : g[node])
		if (!vis[x]) if (dfs2(x)) return 1;
	res.pop_back(); return 0;
}
void dfs3(int node) {
	vis[node] = 1; res.push_back(node);
	uni.push_back(node);
	if (uni.size() < 60)
		for (auto x : g[node])
			if ((!vis[x]) && (uni.size() < 60))
				dfs3(x), res.push_back(node);
}
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]);
	ans.clear(); res.clear(); vis.assign(n, 0); dfs2(p); vis.assign(n, 0); dfs3(0);

	bool f = 0;
	vector<bool> done(n);
	for (int i = 1; i < res.size(); ++i) {
		auto x = res[i];
		f = (f || (x == 0));
		if (f && (!done[x])) ans.push_back(Move((int32_t)x)), done[x] = 1;
		else Move(x);
	}
	int val = 0;
	for (int i = 0; i < ans.size(); ++i)
		val += (ans[i] * (1ll << i));
	return val;
}
#endif

Ioi

#define _CRT_SECURE_NO_WARNINGS
#define SUBMIT 2

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

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

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

static int 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(N, M, A, B, X, 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

//common code
vector<int> g[10005], res;
vector<bool> vis, ans;
void dfs(int node) {
	vis[node] = 1, res.push_back(node);
	if (res.size() < 60)
		for (auto x : g[node])
			if ((!vis[x]) && (res.size() < 60))
				dfs(x);
}

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

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]);
	vis.assign(n, 0), ans.assign(n, 0), dfs(0);
	int cur = 0;
	for (auto x : res) ans[x] = ((r & (1ll << cur)) > 0), cur += 1;
	for (int i = 0; i < n; ++i) MessageBoard((int32_t)i, (int32_t)ans[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> uni;
bool dfs2(int node) {
	if (node == 0) return 1;
	vis[node] = 1, res.push_back(node);
	for (auto x : g[node])
		if (!vis[x]) if (dfs2(x)) return 1;
	res.pop_back(); return 0;
}
void dfs3(int node) {
	vis[node] = 1; res.push_back(node);
	uni.push_back(node);
	if (uni.size() < 60)
		for (auto x : g[node])
			if ((!vis[x]) && (uni.size() < 60))
				dfs3(x), res.push_back(node);
}
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]);
	ans.clear(); res.clear(); vis.assign(n, 0); dfs2(p); vis.assign(n, 0); dfs3(0);

	bool f = 0;
	vector<bool> done(n);
	for (int i = 1; i < res.size(); ++i) {
		auto x = res[i];
		f = (f || (x == 0));
		if (f && (!done[x])) ans.push_back(Move((int32_t)x)), done[x] = 1;
		else Move(x);
	}
	int val = 0;
	for (int i = 0; i < ans.size(); ++i)
		val += (ans[i] * (1ll << i));
	return val;
}
#endif

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