Submission #100247

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100247	2019-03-10T04:33:58 Z	jasony123123	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	94 ms	14576 KB

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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2168 KB	Output is correct
2	Correct	7 ms	1928 KB	Output is correct
3	Correct	8 ms	2060 KB	Output is correct
4	Correct	6 ms	1956 KB	Output is correct
5	Correct	6 ms	1792 KB	Output is correct
6	Correct	6 ms	1932 KB	Output is correct
7	Correct	7 ms	2052 KB	Output is correct
8	Correct	8 ms	2248 KB	Output is correct
9	Correct	6 ms	2284 KB	Output is correct
10	Correct	7 ms	1792 KB	Output is correct
11	Correct	10 ms	2116 KB	Output is correct
12	Correct	5 ms	1928 KB	Output is correct
13	Correct	7 ms	2188 KB	Output is correct
14	Correct	6 ms	2236 KB	Output is correct
15	Correct	6 ms	2236 KB	Output is correct
16	Correct	6 ms	2188 KB	Output is correct
17	Correct	7 ms	2188 KB	Output is correct
18	Correct	7 ms	2188 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	13948 KB	Output is correct
2	Correct	94 ms	13820 KB	Output is correct
3	Correct	67 ms	13832 KB	Output is correct
4	Correct	52 ms	13336 KB	Output is correct
5	Correct	50 ms	13712 KB	Output is correct
6	Correct	48 ms	13456 KB	Output is correct
7	Correct	46 ms	13584 KB	Output is correct
8	Correct	47 ms	13692 KB	Output is correct
9	Correct	47 ms	13704 KB	Output is correct
10	Correct	39 ms	13084 KB	Output is correct
11	Correct	40 ms	13256 KB	Output is correct
12	Correct	43 ms	12224 KB	Output is correct
13	Correct	40 ms	12128 KB	Output is correct
14	Correct	40 ms	12684 KB	Output is correct
15	Correct	41 ms	13312 KB	Output is correct
16	Correct	51 ms	13200 KB	Output is correct
17	Correct	55 ms	13356 KB	Output is correct
18	Correct	56 ms	13064 KB	Output is correct
19	Correct	47 ms	13280 KB	Output is correct
20	Correct	41 ms	13912 KB	Output is correct
21	Correct	41 ms	13728 KB	Output is correct
22	Correct	68 ms	13588 KB	Output is correct
23	Correct	65 ms	13684 KB	Output is correct
24	Correct	59 ms	13704 KB	Output is correct
25	Correct	63 ms	13668 KB	Output is correct
26	Correct	64 ms	13704 KB	Output is correct
27	Correct	67 ms	13656 KB	Output is correct
28	Correct	57 ms	13704 KB	Output is correct
29	Correct	53 ms	12628 KB	Output is correct
30	Correct	56 ms	12936 KB	Output is correct
31	Correct	6 ms	1824 KB	Output is correct
32	Correct	8 ms	1928 KB	Output is correct
33	Correct	8 ms	2180 KB	Output is correct
34	Correct	7 ms	2048 KB	Output is correct
35	Correct	6 ms	1920 KB	Output is correct
36	Correct	6 ms	1980 KB	Output is correct
37	Correct	5 ms	1856 KB	Output is correct
38	Correct	6 ms	1928 KB	Output is correct
39	Correct	6 ms	1864 KB	Output is correct
40	Correct	5 ms	1920 KB	Output is correct
41	Correct	5 ms	1920 KB	Output is correct
42	Correct	5 ms	1860 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1920 KB	Output is correct
2	Correct	6 ms	1920 KB	Output is correct
3	Correct	6 ms	1928 KB	Output is correct
4	Correct	16 ms	3632 KB	Output is correct
5	Correct	13 ms	3880 KB	Output is correct
6	Correct	10 ms	3744 KB	Output is correct
7	Correct	11 ms	3748 KB	Output is correct
8	Correct	12 ms	3748 KB	Output is correct
9	Correct	34 ms	14528 KB	Output is correct
10	Correct	40 ms	14576 KB	Output is correct
11	Correct	37 ms	14524 KB	Output is correct
12	Correct	6 ms	1928 KB	Output is correct
13	Correct	5 ms	1980 KB	Output is correct
14	Correct	6 ms	1792 KB	Output is correct
15	Correct	6 ms	1928 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	14000 KB	Output is correct
2	Correct	68 ms	13928 KB	Output is correct
3	Correct	59 ms	13964 KB	Output is correct
4	Correct	56 ms	13200 KB	Output is correct
5	Correct	55 ms	14220 KB	Output is correct
6	Correct	63 ms	13712 KB	Output is correct
7	Correct	55 ms	13752 KB	Output is correct
8	Correct	62 ms	13456 KB	Output is correct
9	Correct	59 ms	13476 KB	Output is correct
10	Correct	48 ms	13032 KB	Output is correct
11	Correct	43 ms	13200 KB	Output is correct
12	Correct	49 ms	12168 KB	Output is correct
13	Correct	51 ms	12200 KB	Output is correct
14	Correct	51 ms	12676 KB	Output is correct
15	Correct	48 ms	13296 KB	Output is correct
16	Correct	53 ms	13084 KB	Output is correct
17	Correct	56 ms	13116 KB	Output is correct
18	Correct	61 ms	13072 KB	Output is correct
19	Correct	65 ms	13200 KB	Output is correct
20	Correct	62 ms	13892 KB	Output is correct
21	Correct	44 ms	13816 KB	Output is correct
22	Correct	52 ms	13704 KB	Output is correct
23	Correct	56 ms	13712 KB	Output is correct
24	Correct	55 ms	13592 KB	Output is correct
25	Correct	56 ms	13740 KB	Output is correct
26	Correct	57 ms	13572 KB	Output is correct
27	Correct	52 ms	13840 KB	Output is correct
28	Correct	64 ms	13624 KB	Output is correct
29	Correct	65 ms	12672 KB	Output is correct
30	Correct	69 ms	13052 KB	Output is correct

Subtask #5

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	13912 KB	Output is correct
2	Correct	65 ms	13828 KB	Output is correct
3	Correct	67 ms	13836 KB	Output is correct
4	Correct	56 ms	13312 KB	Output is correct
5	Correct	56 ms	14436 KB	Output is correct
6	Correct	54 ms	13664 KB	Output is correct
7	Correct	49 ms	13456 KB	Output is correct
8	Correct	51 ms	13464 KB	Output is correct
9	Correct	64 ms	13684 KB	Output is correct
10	Correct	54 ms	13192 KB	Output is correct
11	Correct	50 ms	13116 KB	Output is correct
12	Correct	51 ms	12148 KB	Output is correct
13	Correct	46 ms	12288 KB	Output is correct
14	Correct	57 ms	12804 KB	Output is correct
15	Correct	62 ms	13148 KB	Output is correct
16	Correct	55 ms	13200 KB	Output is correct
17	Correct	65 ms	13120 KB	Output is correct
18	Correct	46 ms	13200 KB	Output is correct
19	Correct	57 ms	13336 KB	Output is correct
20	Correct	40 ms	13832 KB	Output is correct
21	Correct	46 ms	13712 KB	Output is correct
22	Correct	54 ms	13712 KB	Output is correct
23	Correct	57 ms	13496 KB	Output is correct
24	Correct	60 ms	13576 KB	Output is correct
25	Correct	52 ms	13712 KB	Output is correct
26	Correct	53 ms	13336 KB	Output is correct
27	Correct	52 ms	13712 KB	Output is correct
28	Correct	55 ms	13712 KB	Output is correct
29	Correct	48 ms	12704 KB	Output is correct
30	Correct	57 ms	13096 KB	Output is correct
31	Correct	6 ms	1940 KB	Output is correct
32	Correct	6 ms	1928 KB	Output is correct
33	Correct	6 ms	2120 KB	Output is correct
34	Correct	7 ms	1948 KB	Output is correct
35	Correct	6 ms	1996 KB	Output is correct
36	Correct	6 ms	1792 KB	Output is correct
37	Correct	6 ms	1888 KB	Output is correct
38	Correct	6 ms	1920 KB	Output is correct
39	Correct	6 ms	1860 KB	Output is correct
40	Correct	6 ms	1920 KB	Output is correct
41	Correct	7 ms	1928 KB	Output is correct
42	Correct	5 ms	1956 KB	Output is correct