Submission #100247

#	Time	Username	Problem	Language	Result	Execution time	Memory
100247		jasony123123	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	94 ms	14576 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
/****************************************************/

namespace com {
	const int MAXN = 10000, BITS = 60;

	v<int> adj[MAXN];
	v<pii> subt[MAXN];
	int key[MAXN];

	template <int SZ> struct UnionFind {
		int par[SZ];
		UnionFind() {
			FOR(i, 0, SZ) par[i] = i;
		}
		int find(int x) {
			if (par[x] != x) par[x] = find(par[x]);
			return par[x];
		}
		bool unite(int x, int y) {
			x = find(x), y = find(y);
			if (x == y) return false;
			par[y] = x;
			return true;
		}
	};

	void make_tree(int m, int A[], int B[]) {
		UnionFind<MAXN> uf;
		FOR(i, 0, m) if (uf.unite(A[i], B[i])) {
			adj[A[i]].push_back(B[i]);
			adj[B[i]].push_back(A[i]);
		}
	}

	void getinit(int x, int p, v<pii> &tree) {
		if (tree.size() == BITS) return;
		tree.push_back({ x,0 });
		for (auto c : adj[x]) if (c != p) getinit(c, x, tree);
	}

	bool isEdge(int a, int b) {
		return binary_search(all(adj[a]), b);
	}

	void dfs(int x, int p) {
		if (subt[x].empty()) {
			v<pii> &tree = subt[x];
			tree = subt[p];

			int w = -1;
			FOR(i, 0, tree.size()) {
				if (tree[i].second == 1 && tree[i].first != p) {
					w = tree[i].first;
					tree.erase(tree.begin() + i);
					break;
				}
			}
			assert(w != -1);
			for (auto &i : tree) if (isEdge(w, i.first)) i.second--;

			tree.push_back({ x,1 });
			for (auto &i : tree) if (i.first == p) i.second++;
			key[x] = key[w];
		}
		for (auto c : adj[x]) if (c != p) dfs(c, x);
	}

	void setup(int N, int M, int A[], int B[]) {
		make_tree(M, A, B);
		FOR(i, 0, N) sort(all(adj[i]));

		v<pii> itree;
		getinit(0, -1, itree);
		for (auto &i : itree)
			for (auto j : itree)
				if (isEdge(i.first, j.first))
					i.second++;

		int k = 0;
		for (auto i : itree) {
			subt[i.first] = itree;
			key[i.first] = k++;
		}
		dfs(0, -1);

	/*	FOR(i, 0, N) {
			cout << "Node " << i << ":\nTree: ";
			v<int> present;
			for (auto x : subt[i]) {
				cout << x.first << ", ";
				present.push_back(key[x.first]);
			}
			sort(all(present));
			cout << "\nKeys: ";
			for (auto x : present)
				cout << x << ", ";
			cout << "\n";
		}*/
	}
}

using namespace com;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	setup(N, M, A, B);
//	cout << "JOI summary::\n";
	FOR(i, 0, N) {
		int msg = 0;
		if (X&(1LL << key[i])) msg = 1;
		MessageBoard(i, msg);
	//	pf("Node %d : key %d : Val %d\n", i, key[i], msg);
	}
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
/****************************************************/

namespace com2 {
	const int MAXN = 10000, BITS = 60;

	v<int> adj[MAXN];
	v<pii> subt[MAXN];
	int key[MAXN];

	int bits[BITS];
	v<int> tour;
	v<int> res;

	bool valid[MAXN];
	void gettour(int x, int p) {
		tour.push_back(x);
		for (auto c : adj[x]) if (c != p && valid[c]) {
			gettour(c, x);
			tour.push_back(x);
		}
	}

	template <int SZ> struct UnionFind {
		int par[SZ];
		UnionFind() {
			FOR(i, 0, SZ) par[i] = i;
		}
		int find(int x) {
			if (par[x] != x) par[x] = find(par[x]);
			return par[x];
		}
		bool unite(int x, int y) {
			x = find(x), y = find(y);
			if (x == y) return false;
			par[y] = x;
			return true;
		}
	};

	void make_tree(int m, int A[], int B[]) {
		UnionFind<MAXN> uf;
		FOR(i, 0, m) if (uf.unite(A[i], B[i])) {
			adj[A[i]].push_back(B[i]);
			adj[B[i]].push_back(A[i]);
		}
	}

	void getinit(int x, int p, v<pii> &tree) {
		if (tree.size() == BITS) return;
		tree.push_back({ x,0 });
		for (auto c : adj[x]) if (c != p) getinit(c, x, tree);
	}

	bool isEdge(int a, int b) {
		return binary_search(all(adj[a]), b);
	}

	void dfs(int x, int p) {
		if (subt[x].empty()) {
			v<pii> &tree = subt[x];
			tree = subt[p];

			int w = -1;
			FOR(i, 0, tree.size()) {
				if (tree[i].second == 1 && tree[i].first != p) {
					w = tree[i].first;
					tree.erase(tree.begin() + i);
					break;
				}
			}
			assert(w != -1);
			for (auto &i : tree) if (isEdge(w, i.first)) i.second--;

			tree.push_back({ x,1 });
			for (auto &i : tree) if (i.first == p) i.second++;
			key[x] = key[w];
		}
		for (auto c : adj[x]) if (c != p) dfs(c, x);
	}

	void setup(int N, int M, int A[], int B[]) {
		make_tree(M, A, B);
		FOR(i, 0, N) sort(all(adj[i]));

		v<pii> itree;
		getinit(0, -1, itree);
		for (auto &i : itree)
			for (auto j : itree)
				if (isEdge(i.first, j.first))
					i.second++;

		int k = 0;
		for (auto i : itree) {
			subt[i.first] = itree;
			key[i.first] = k++;
		}
		dfs(0, -1);

	/*	FOR(i, 0, N) {
			cout << "Node " << i << ":\nTree: ";
			v<int> present;
			for (auto x : subt[i]) {
				cout << x.first << ", ";
				present.push_back(key[x.first]);
			}
			sort(all(present));
			cout << "\nKeys: ";
			for (auto x : present)
				cout << x << ", ";
			cout << "\n";
		}*/
	}
}

using namespace com2;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	setup(N, M, A, B);
	for (auto i : subt[P]) valid[i.first] = 1;
	gettour(P, -1);
	res.push_back(V);
	FOR(i, 1, tour.size())
		res.push_back(Move(tour[i]));
	FOR(i, 0, tour.size())
		bits[key[tour[i]]] = res[i];

	ll ans = 0;
	FOR(i, 0, BITS)
		ans += (1LL << i)*bits[i];
	return ans;
}

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