Submission #1293260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293260		am_aadvik	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	31 ms	3652 KiB

Joi

//possibly the messiest jungle ive had the displeasure to create
#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<pair<int, int>> g[200005];
vector<bool> vis;
vector<int> sub;
pair<vector<int>, pair<set<int>, int>> label(int n) {
	queue<pair<int, int>> q; q.push({ 0, 0 });
	set<int> s;
	vector<int> lb(n, -1), p(n); lb[0] = 0;
	while (!q.empty()) {
		auto f = q.front(); q.pop();
		for (auto x : g[f.first])
			if (lb[x.first] == -1)
				lb[x.first] = f.second + 1, q.push({ x.first, lb[x.first] }),
				p[x.first] = ((f.first == 0) ? x.first : p[f.first]), s.insert(x.second);
	}
	int mx = *max_element(lb.begin(), lb.end());
	for (int i = 0; i < n; ++i) if (lb[i] == mx) {
		return { lb, {s, p[i]} };
	}
}
int pre(int node, set<int>& s, int cdep) {
	sub[node] = cdep, vis[node] = 1;
	for (auto x : g[node])
		if (!vis[x.first] && (s.find(x.second) != s.end())) 
			sub[node] = max(sub[node], pre(x.first, s, cdep + 1));
	return sub[node];
}

// 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 c, int av, int l, set<int>& s, vector<int>& ans, bool best) {
	vis[node] = 1;
	ans.push_back(node);
	c += 1; if (best)--l;
	int mx = 0, mxv = 0;
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()))
			if (sub[x.first] > mx) mxv = x.first, mx = sub[x.first];
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && ((x.first != mxv) || (!best)) && (c < (60 - l)))
			c = dfsA(x.first, c, -1, l, s, ans, 0);
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && (x.first == mxv) && best)
			c = dfsA(x.first, c, -1, l, s, ans, 1);
	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 < n; ++i) g[i].clear();
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back({ (int)b[i], i }),
		g[(int)b[i]].push_back({ (int)a[i], i });
	for (int i = 0; i < n; ++i) sort(g[i].begin(), g[i].end());
	auto lab = label(n);
	vis.assign(n, 0), sub.assign(n, 0), pre(0, lab.second.first, 0), vis.assign(n, 0);
	vector<int> res(n, 0), ans;
	if ((*max_element(lab.first.begin(), lab.first.end()) < 59))
		vis.assign(n, 0), dfsA(0, 0, -1, *max_element(lab.first.begin(), lab.first.end())+1, lab.second.first, ans, 1), vis.assign(n, 0);
	else
		for (int i = 0; i < n; ++i)
			res[i] = ((r & (1ll << (int)(lab.first[i] % 60ll))) > 0ll);
	//for (auto x : ans) cout << x << " "; cout << endl;
	if (ans.size()) for (int i = 0; i < 60; ++i) res[ans[i]] = ((r & (1ll << i)) > 0);
	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 av, int l, set<int>& s, vector<pair<int, int>>& ans, bool best) {
	vis[node] = 1;
	if (node) ans.push_back({ node, Move(node) });
	c += 1; if (best)--l;
	int mx = 0, mxv = 0;
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()))
			if (sub[x.first] > mx) mxv = x.first, mx = sub[x.first];
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && ((x.first != mxv) || (!best)) && (c < (60 - l)))
			c = dfsB(x.first, c, -1, l, s, ans, 0), ans.push_back({ node, Move(node) });
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && (x.first == mxv) && best)
			c = dfsB(x.first, c, -1, l, s, ans, 1);
	return c;
}
bool dfs2B(int node, vector<int>& lab) {
	vis[node] = 1, res.push_back(node);
	if ((lab[node] % 60) == 1) return 1;
	for (auto x : g[node])
		if ((lab[x.first] == (lab[node] - 1)) && (!vis[x.first]))
			if (dfs2B(x.first, lab)) return 1;
	res.pop_back(); return 0;
}
bool dfs3B(int node, vector<int>& lab) {
	vis[node] = 1, res.push_back(node);
	if ((lab[node] % 60) == 59) return 1;
	for (auto x : g[node])
		if ((lab[x.first] == (lab[node] + 1)) && (!vis[x.first]))
			if (dfs3B(x.first, lab)) return 1;
	res.pop_back(); return 0;
}
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 < n; ++i) g[i].clear();
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back({ (int)b[i], i }),
		g[(int)b[i]].push_back({ (int)a[i], i });
	for (int i = 0; i < n; ++i) sort(g[i].begin(), g[i].end());
	auto lab = label(n);
	vis.assign(n, 0), sub.assign(n, 0), pre(0, lab.second.first, 0), vis.assign(n, 0);
	int cur = v, op = p;
	while ((lab.first[p] % 60) != 0)
		for (auto x : g[p])
			if (lab.first[x.first] == (lab.first[p] - 1)) {
				cur = Move(x.first); op = p = x.first; break;
			}
	if ((*max_element(lab.first.begin(), lab.first.end()) < 59)) {
		vector<pair<int, int>> res2 = { {0, cur} };
		res.clear(), vis.assign(n, 0), dfsB(p, 0, lab.second.second, *max_element(lab.first.begin(), lab.first.end())+1, lab.second.first, res2,1);
		vis.assign(n, 0);
		int ans = 0;
		//for (auto x : res) cout << x << " "; cout << endl;
		int j = 0;
		for (int i = 0; i < res2.size(); ++i)
			if (!vis[res2[i].first]) {
				ans += (res2[i].second * (1ll << j)),
					vis[res2[i].first] = 1;
				//cout << res2[i].first << " ";
				j += 1;
				if (j > 60) break;
			}
		vis.assign(n, 0);
		return ans;
	}
	else {
		res.clear();
		vis.assign(n, 0);
		if (!dfs2B(p, lab.first))
			vis.assign(n, 0), dfs3B(p, lab.first), vis.assign(n, 0);
	}
	vector<pair<int, int>> val = { {lab.first[op] % 60, cur} };
	for (int i = 1; i < res.size(); ++i)
		val.push_back({ lab.first[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

//possibly the messiest jungle ive had the displeasure to create
#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<pair<int, int>> g[200005];
vector<bool> vis;
vector<int> sub;
pair<vector<int>, pair<set<int>, int>> label(int n) {
	queue<pair<int, int>> q; q.push({ 0, 0 });
	set<int> s;
	vector<int> lb(n, -1), p(n); lb[0] = 0;
	while (!q.empty()) {
		auto f = q.front(); q.pop();
		for (auto x : g[f.first])
			if (lb[x.first] == -1)
				lb[x.first] = f.second + 1, q.push({ x.first, lb[x.first] }),
				p[x.first] = ((f.first == 0) ? x.first : p[f.first]), s.insert(x.second);
	}
	int mx = *max_element(lb.begin(), lb.end());
	for (int i = 0; i < n; ++i) if (lb[i] == mx) {
		return { lb, {s, p[i]} };
	}
}
int pre(int node, set<int>& s, int cdep) {
	sub[node] = cdep, vis[node] = 1;
	for (auto x : g[node])
		if (!vis[x.first] && (s.find(x.second) != s.end())) 
			sub[node] = max(sub[node], pre(x.first, s, cdep + 1));
	return sub[node];
}

// 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 c, int av, int l, set<int>& s, vector<int>& ans, bool best) {
	vis[node] = 1;
	ans.push_back(node);
	c += 1; if (best)--l;
	int mx = 0, mxv = 0;
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()))
			if (sub[x.first] > mx) mxv = x.first, mx = sub[x.first];
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && ((x.first != mxv) || (!best)) && (c < (60 - l)))
			c = dfsA(x.first, c, -1, l, s, ans, 0);
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && (x.first == mxv) && best)
			c = dfsA(x.first, c, -1, l, s, ans, 1);
	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 < n; ++i) g[i].clear();
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back({ (int)b[i], i }),
		g[(int)b[i]].push_back({ (int)a[i], i });
	for (int i = 0; i < n; ++i) sort(g[i].begin(), g[i].end());
	auto lab = label(n);
	vis.assign(n, 0), sub.assign(n, 0), pre(0, lab.second.first, 0), vis.assign(n, 0);
	vector<int> res(n, 0), ans;
	if ((*max_element(lab.first.begin(), lab.first.end()) < 59))
		vis.assign(n, 0), dfsA(0, 0, -1, *max_element(lab.first.begin(), lab.first.end())+1, lab.second.first, ans, 1), vis.assign(n, 0);
	else
		for (int i = 0; i < n; ++i)
			res[i] = ((r & (1ll << (int)(lab.first[i] % 60ll))) > 0ll);
	//for (auto x : ans) cout << x << " "; cout << endl;
	if (ans.size()) for (int i = 0; i < 60; ++i) res[ans[i]] = ((r & (1ll << i)) > 0);
	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 av, int l, set<int>& s, vector<pair<int, int>>& ans, bool best) {
	vis[node] = 1;
	if (node) ans.push_back({ node, Move(node) });
	c += 1; if (best)--l;
	int mx = 0, mxv = 0;
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()))
			if (sub[x.first] > mx) mxv = x.first, mx = sub[x.first];
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && ((x.first != mxv) || (!best)) && (c < (60 - l)))
			c = dfsB(x.first, c, -1, l, s, ans, 0), ans.push_back({ node, Move(node) });
	for (auto x : g[node])
		if ((!vis[x.first]) && (s.find(x.second) != s.end()) && (x.first == mxv) && best)
			c = dfsB(x.first, c, -1, l, s, ans, 1);
	return c;
}
bool dfs2B(int node, vector<int>& lab) {
	vis[node] = 1, res.push_back(node);
	if ((lab[node] % 60) == 1) return 1;
	for (auto x : g[node])
		if ((lab[x.first] == (lab[node] - 1)) && (!vis[x.first]))
			if (dfs2B(x.first, lab)) return 1;
	res.pop_back(); return 0;
}
bool dfs3B(int node, vector<int>& lab) {
	vis[node] = 1, res.push_back(node);
	if ((lab[node] % 60) == 59) return 1;
	for (auto x : g[node])
		if ((lab[x.first] == (lab[node] + 1)) && (!vis[x.first]))
			if (dfs3B(x.first, lab)) return 1;
	res.pop_back(); return 0;
}
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 < n; ++i) g[i].clear();
	for (int i = 0; i < m; ++i)
		g[(int)a[i]].push_back({ (int)b[i], i }),
		g[(int)b[i]].push_back({ (int)a[i], i });
	for (int i = 0; i < n; ++i) sort(g[i].begin(), g[i].end());
	auto lab = label(n);
	vis.assign(n, 0), sub.assign(n, 0), pre(0, lab.second.first, 0), vis.assign(n, 0);
	int cur = v, op = p;
	while ((lab.first[p] % 60) != 0)
		for (auto x : g[p])
			if (lab.first[x.first] == (lab.first[p] - 1)) {
				cur = Move(x.first); op = p = x.first; break;
			}
	if ((*max_element(lab.first.begin(), lab.first.end()) < 59)) {
		vector<pair<int, int>> res2 = { {0, cur} };
		res.clear(), vis.assign(n, 0), dfsB(p, 0, lab.second.second, *max_element(lab.first.begin(), lab.first.end())+1, lab.second.first, res2,1);
		vis.assign(n, 0);
		int ans = 0;
		//for (auto x : res) cout << x << " "; cout << endl;
		int j = 0;
		for (int i = 0; i < res2.size(); ++i)
			if (!vis[res2[i].first]) {
				ans += (res2[i].second * (1ll << j)),
					vis[res2[i].first] = 1;
				//cout << res2[i].first << " ";
				j += 1;
				if (j > 60) break;
			}
		vis.assign(n, 0);
		return ans;
	}
	else {
		res.clear();
		vis.assign(n, 0);
		if (!dfs2B(p, lab.first))
			vis.assign(n, 0), dfs3B(p, lab.first), vis.assign(n, 0);
	}
	vector<pair<int, int>> val = { {lab.first[op] % 60, cur} };
	for (int i = 1; i < res.size(); ++i)
		val.push_back({ lab.first[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

Compilation message (stderr)

# 1번째 컴파일 단계

Joi.cpp: In function 'std::pair<std::vector<long long int>, std::pair<std::set<long long int>, long long int> > label(long long int)':
Joi.cpp:124:1: warning: control reaches end of non-void function [-Wreturn-type]
  124 | }
      | ^

# 2번째 컴파일 단계

Ioi.cpp: In function 'std::pair<std::vector<long long int>, std::pair<std::set<long long int>, long long int> > label(long long int)':
Ioi.cpp:124:1: warning: control reaches end of non-void function [-Wreturn-type]
  124 | }
      | ^

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