Submission #684036

#	Time	Username	Problem	Language	Result	Execution time	Memory
684036		flappybird	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	191 ms	7132 KiB

Joi

#include "Joi.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define MAX 10101
#define LEN 60
namespace JOI {
	vector<int> adj[MAX];
	vector<int> tree[MAX];
	queue<int> q;
	int cnt = 0;
	int col[MAX];
	int ans[MAX];
	int num[MAX];
	int vis[MAX];
	int prt[MAX];
	void dfs(int x, int p, int c) {
		col[x] = c;
		ans[x] = ++cnt;
		for (auto v : tree[x]) if (p != v) {
			if (cnt < LEN) dfs(v, x, c);
			else q.push(v);
		}
	}
	void getnum(int x, int p = -1) {
		if (~p) tree[p].push_back(x), tree[x].push_back(p), prt[x] = p;
		num[x] = 1;
		vis[x] = 1;
		for (auto v : adj[x]) if (!vis[v]) {
			getnum(v, x);
			num[x] += num[v];
		}
	}
	vector<int> lst;
	void make_lst(int x, int p, int c) {
		for (auto v : tree[x]) if (v != p && col[v] == c) make_lst(v, x, c);
		lst.push_back(x);
	}
	void color_rem(int x, int p, int c) {
		ans[x] = ans[lst.back()];
		lst.pop_back();
		col[x] = c;
		for (auto v : tree[x]) if (v != p) color_rem(v, x, c);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	int i;
	for (i = 0; i < M; i++) JOI::adj[A[i]].push_back(B[i]), JOI::adj[B[i]].push_back(A[i]);
	JOI::getnum(0);
	JOI::q.push(0);
	int cols = 0;
	vector<int> rem;
	while (JOI::q.size()) {
		int t = JOI::q.front();
		JOI::q.pop();
		if (JOI::num[t] < LEN) rem.push_back(t);
		else JOI::cnt = 0, JOI::dfs(t, JOI::prt[t], ++cols);
	}
	for (auto v : rem) {
		cols++;
		JOI::make_lst(JOI::prt[v], -1, JOI::col[JOI::prt[v]]);
		reverse(JOI::lst.begin(), JOI::lst.end());
		JOI::color_rem(v, JOI::prt[v], cols);
		JOI::lst.clear();
	}
	for (i = 0; i < N; i++) MessageBoard(i, (X >> (JOI::ans[i] - 1)) & 1ll);
}

Ioi

#include "Ioi.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define MAX 10101
#define LEN 60
namespace IOI {
	vector<int> adj[MAX];
	vector<int> tree[MAX];
	queue<int> q;
	int cnt = 0;
	int col[MAX];
	int ans[MAX];
	int num[MAX];
	int vis[MAX];
	int prt[MAX];
	void dfs(int x, int p, int c) {
		col[x] = c;
		ans[x] = ++cnt;
		for (auto v : tree[x]) if (p != v) {
			if (cnt < LEN) dfs(v, x, c);
			else q.push(v);
		}
	}
	void getnum(int x, int p = -1) {
		if (~p) tree[p].push_back(x), tree[x].push_back(p), prt[x] = p;
		num[x] = 1;
		vis[x] = 1;
		for (auto v : adj[x]) if (!vis[v]) {
			getnum(v, x);
			num[x] += num[v];
		}
	}
	vector<int> lst;
	void make_lst(int x, int p, int c) {
		for (auto v : tree[x]) if (v != p && col[v] == c) make_lst(v, x, c);
		lst.push_back(x);
	}
	void color_rem(int x, int p, int c) {
		ans[x] = ans[lst.back()];
		lst.pop_back();
		col[x] = c;
		for (auto v : tree[x]) if (v != p) color_rem(v, x, c);
	}
	vector<int> rems[MAX];
	int chk[MAX];
	int Xs[MAX];
	void getans(int x, int p = -1) {
		for (auto v : tree[x]) if (v != p && chk[v]) {
			Xs[ans[v] - 1] = Move(v);
			getans(v, x);
			Move(x);
		}
	}
}
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++) IOI::adj[A[i]].push_back(B[i]), IOI::adj[B[i]].push_back(A[i]);
	IOI::getnum(0);
	IOI::q.push(0);
	int cols = 0;
	vector<int> rem;
	while (IOI::q.size()) {
		int t = IOI::q.front();
		IOI::q.pop();
		if (IOI::num[t] < LEN) rem.push_back(t);
		else IOI::cnt = 0, IOI::dfs(t, IOI::prt[t], ++cols);
	}
	int x = cols;
	for (auto v : rem) {
		cols++;
		IOI::make_lst(IOI::prt[v], -1, IOI::col[IOI::prt[v]]);
		reverse(IOI::lst.begin(), IOI::lst.end());
		IOI::color_rem(v, IOI::prt[v], cols);
		swap(IOI::lst, IOI::rems[cols]);
		IOI::lst.clear();
	}
	int C = IOI::col[P];
	for (i = 0; i < N; i++) if (IOI::col[i] == C) IOI::chk[i] = 1;
	for (auto v : IOI::rems[C]) IOI::chk[v] = 1;
	IOI::Xs[IOI::ans[P] - 1] = V;
	IOI::getans(P);
	ll X = 0;
	for (i = 0; i < LEN; i++) X |= (ll)IOI::Xs[i] << (ll)i;
	return X;
}

Compilation message (stderr)

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:71:6: warning: unused variable 'x' [-Wunused-variable]
   71 |  int x = cols;
      |      ^

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