Submission #51488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51488	2018-06-18T04:16:00 Z	shoemakerjo	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	41 ms	9560 KB

Joi

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
// #define LOCAL
#define maxn 10010
#define adj SPENCER_COMPTON
#define n spence
#define m king_of_hottub
#define par king_of_sice
#define label king_of_ditch
#define seen double_desk
#define desired guuuuu
#define dep blahblahblahblah
#define maxd guuuuuuuuuuuu
#define dfs guuu
#define findset gkadsflk
#define unionset dsflkasdh
#define gobig king_of_tinder
#define preorder ihatethis
#define postorder nocompile
#define dfs2 adsklf
#define gosmall PATEL

vector<vector<int>> adj(maxn);
int n;
int m;
int par[maxn];
int dep[maxn];
int label[maxn]; //which bit i correspond to
int seen = 0; //we can just  use seen for making desired and labeling it
bool desired[maxn];
long long x2;

int maxd = 0;

void dfs(int u, int p) {
	dep[u] = p == - 1 ? 1 : dep[p]+1;
	maxd = max(maxd, dep[u]);
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);

	}
}

int findset(int u) {
	if (par[u] == u) return u;
	return par[u] = findset(par[u]);
}

void unionset(int a, int b) {
	a = findset(a);
	b = findset(b);
	par[a] = b;
}

void gobig() {
	for (int i = 1; i <= n; i++) {
		if (dep[i] % 60 != 0) 
			label[i] = dep[i] % 60; //easy way to do it
		else label[i] = 60;
	}
	//this is all we need
}

void preorder(int u, int p) {
	desired[u] = true;
	seen++;

	for (int v : adj[u]) {
		if (seen == 60 || v == p) continue;
		preorder(v, u);
	}
}

void postorder(int u, int p) {
	for (int v : adj[u]) {
		if (v == p) continue;
		if (desired[v]) {
			postorder(v, u);
		}
	}
	label[u] = ++seen;
}

void dfs2(int u, int p, int dl) {
	if (!desired[u]) {
		label[u] = dep[u] - dl;
	}
	else dl = dep[u];
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs2(v, u, dl);
	}
}

void gosmall() {
	seen = 0;
	preorder(1, -1);
	seen = 0;
	postorder(1, -1);
	dfs2(1,  -1, 0);
}

#ifdef LOCAL
	void MessageBoard(int attr, int msg) {

	}
#endif

void constructLabels() {
	for (int i = 1; i <= n; i++) {
		if (x2 & (1LL << (label[i]-1))) {
			MessageBoard(i-1, 1);
		}
		else MessageBoard(i-1, 0);
	}
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	n = N;
	m = M;
	x2 = X;
	for (int i = 1; i <= n; i++) {
		par[i] = i;
	}
	for (int i = 0; i < m; i++) {
		int v1 = A[i]+1;
		int v2 = B[i]+1;
		if (findset(v1) != findset(v2)) {
			unionset(v1, v2);
			adj[v1].push_back(v2);
			adj[v2].push_back(v1);
		}
	}
	dfs(1, -1); //set up the trees
	if (maxd >= 60) {
		gobig();
	}
	else {
		gosmall();
		// assert(false);
	}
	constructLabels(); //specific to Joi version
}

#ifdef LOCAL
int main() {

}
#endif

//run the same labelling scheme
//label each index according to which bit it stores
//difference is that the first guy sets the corresponding bit,
//    the second guy has to figure it out.

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define ll long long
// #define LOCAL
const  int maxni = 100010;
int bit[62];
vector<vector<int>> adj(maxni);
int n;
int m;
int par[maxni];
int dep[maxni];
int label[maxni]; //which bit i correspond to
int seen = 0;
bool alseen[maxni]; //already seen this label
int pc[maxni];
int furthestdown[maxni];
int bestnode[maxni];
bool desired[maxni];
int maxd = 0;
int loc; //initial location
int val; //value at attraction p
int numcalls;


#ifdef LOCAL
	int Move(int val) {
		return 1;
	}
#endif

	
int move(int loc) {
	numcalls++;
	assert(numcalls <= 119);
	// cout << "going to " << loc <<  endl;
	return Move(loc-1);
}

void dfs(int u, int p) {
	// cout << "dfs: : " << u << " " << p << endl;
	dep[u] = p == - 1 ? 1 : dep[p]+1;
	pc[u] = p;
	maxd = max(maxd, dep[u]);
	furthestdown[u] = dep[u];
	bestnode[u] = u;
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
		if (furthestdown[v] > furthestdown[u]) {
			furthestdown[u] = furthestdown[v];
			bestnode[u] = v;
		}
	}
}

int findset(int u) {
	if (par[u] == u) return u;
	return par[u] = findset(par[u]);
}

void unionset(int a, int b) {
	a = findset(a);
	b = findset(b);
	par[a] = b;
}

void gobig() {
	for (int i = 1; i <= n; i++) {
		if (dep[i] % 60 != 0) 
			label[i] = dep[i] % 60; //easy way to do it
		else label[i] = 60;
	}
	//this is all we need
}

void preorder(int u, int p) {
	// cout << u << " is desired " << endl;
	desired[u] = true;
	seen++;

	for (int v : adj[u]) {
		if (seen == 60 || v == p) continue;
		preorder(v, u);
	}
}

void postorder(int u, int p) {
	for (int v : adj[u]) {
		if (v == p) continue;
		if (desired[v]) {
			postorder(v, u);
		}
	}
	label[u] = ++seen;
}

void dfs2(int u, int p, int dl) {
	if (!desired[u]) {
		label[u] = dep[u] - dl;
	}
	else dl = dep[u];
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs2(v, u, dl);
	}
}

void gosmall() {
	seen = 0;
	preorder(1, -1);
	seen = 0;
	postorder(1, -1);
	dfs2(1,  -1, 0);
}


void ansbig() {
	// cout << "DOING BIG" << endl;
	//this is easy
	//remember loc is the initial place
	bit[label[loc]] = val;
	int quer = 0;
	while (loc != 1 && quer < 61) {
		// cout << "cur loc " << loc << " : " << pc[loc] << endl;
		loc = pc[loc];
		bit[label[loc]] = move(loc);
		quer++;
	}
	if (loc == 1 && quer < 61) {
		//keep going down while I can
		while (dep[loc] < 60) {
			loc = bestnode[loc];
			bit[label[loc]] = move(loc);
		}
	}

}



void anssmall() {
	// cout << "DOING SMALL" << endl;
	bit[label[loc]] = val;
	if (!desired[loc]) alseen[label[loc]] = true;
	while (!desired[loc]) {
		// cout << "trying to go up from " << loc << " : " << pc[loc] << endl;
		loc = pc[loc];
		bit[label[loc]] = move(loc);
		if (!desired[loc]) alseen[label[loc]] = true;
	}
	while (true) {
		// cout << "at " << loc << " with label " << label[loc] << endl;
		if (alseen[label[loc]]) {
			loc = pc[loc];
			if (loc == -1) break;
			// cout << "went to " << loc << " and it had label " << label[loc] << endl;
			bit[label[loc]] = move(loc);
		}
		else {
			bool fin = false;
			for (int v : adj[loc]) {
				if (v == pc[loc]) continue;
				if (desired[v] && !alseen[label[v]]) {
					loc = v;
					bit[label[loc]] = move(loc);
					fin = true;
					// alseen[v] = true;
					break;
				}
				// alseen[loc] = true;
			}
			if (!fin) alseen[label[loc]] = true;
		}
	}
}

ll constructans() {
	ll ans = 0LL;
	for (int i = 60; i >= 1; i--) {
		ans = (ans*2LL) + bit[i];
	}
	// cout << "ANS: " << ans << endl;
	return ans;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	//run stuff and then  do connstruct ans
	n = N;
	numcalls = 0;
	m = M;
	fill(bit, bit+62, 0);
	fill(desired, desired+maxni, false);
	fill(alseen, alseen+maxni, false);
	loc = P;
	loc++;
	val = V;
	for (int i = 1; i <= n; i++) {
		par[i] = i;
	}
	for (int i = 0; i < m; i++) {
		++A[i];
		++B[i];
		// cout << i << ":   looking at " << A[i] << " " << B[i] << endl;
		if (findset(A[i]) != findset(B[i])) {
			// cout << "unioned " << A[i] << " to " << B[i] << endl;
			// cout << "UNIONING A SET" << endl;
			unionset(A[i], B[i]);
			adj[A[i]].push_back(B[i]);
			adj[B[i]].push_back(A[i]);
		}
	}
	dfs(1, -1); //set up the trees
	if (maxd >= 60) {
		gobig();
		ansbig();
	}
	else {
		gosmall();
		// cout << "asddhfasldkhhldghk;gsk" << endl;
		anssmall();
	}

	return constructans();
}

#ifdef LOCAL

int main() {

}

#endif

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	3632 KB	Output is correct
2	Correct	8 ms	6000 KB	Output is correct
3	Correct	8 ms	6032 KB	Output is correct
4	Correct	6 ms	6252 KB	Output is correct
5	Correct	6 ms	6440 KB	Output is correct
6	Correct	7 ms	6440 KB	Output is correct
7	Correct	7 ms	6500 KB	Output is correct
8	Correct	8 ms	6560 KB	Output is correct
9	Correct	6 ms	6572 KB	Output is correct
10	Correct	6 ms	6584 KB	Output is correct
11	Correct	9 ms	6584 KB	Output is correct
12	Correct	7 ms	6584 KB	Output is correct
13	Correct	6 ms	6584 KB	Output is correct
14	Correct	7 ms	6584 KB	Output is correct
15	Correct	7 ms	6584 KB	Output is correct
16	Correct	6 ms	6584 KB	Output is correct
17	Correct	6 ms	6584 KB	Output is correct
18	Correct	7 ms	6652 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	7844 KB	Output is correct
2	Correct	31 ms	8968 KB	Output is correct
3	Correct	41 ms	8968 KB	Output is correct
4	Correct	32 ms	8968 KB	Output is correct
5	Correct	27 ms	8968 KB	Output is correct
6	Correct	35 ms	8968 KB	Output is correct
7	Correct	24 ms	8968 KB	Output is correct
8	Correct	30 ms	8968 KB	Output is correct
9	Correct	23 ms	8968 KB	Output is correct
10	Correct	26 ms	8968 KB	Output is correct
11	Correct	20 ms	8968 KB	Output is correct
12	Correct	20 ms	8968 KB	Output is correct
13	Correct	25 ms	8968 KB	Output is correct
14	Correct	23 ms	8968 KB	Output is correct
15	Correct	30 ms	8968 KB	Output is correct
16	Correct	29 ms	8968 KB	Output is correct
17	Correct	22 ms	8968 KB	Output is correct
18	Correct	32 ms	8968 KB	Output is correct
19	Correct	25 ms	8968 KB	Output is correct
20	Correct	20 ms	8968 KB	Output is correct
21	Correct	24 ms	8968 KB	Output is correct
22	Correct	27 ms	8968 KB	Output is correct
23	Correct	23 ms	9028 KB	Output is correct
24	Correct	20 ms	9088 KB	Output is correct
25	Correct	24 ms	9088 KB	Output is correct
26	Correct	24 ms	9088 KB	Output is correct
27	Correct	26 ms	9088 KB	Output is correct
28	Correct	27 ms	9088 KB	Output is correct
29	Correct	24 ms	9088 KB	Output is correct
30	Correct	25 ms	9088 KB	Output is correct
31	Correct	8 ms	9088 KB	Output is correct
32	Correct	8 ms	9088 KB	Output is correct
33	Correct	8 ms	9088 KB	Output is correct
34	Correct	7 ms	9088 KB	Output is correct
35	Correct	6 ms	9088 KB	Output is correct
36	Correct	6 ms	9088 KB	Output is correct
37	Correct	6 ms	9088 KB	Output is correct
38	Correct	6 ms	9088 KB	Output is correct
39	Correct	6 ms	9088 KB	Output is correct
40	Correct	6 ms	9088 KB	Output is correct
41	Correct	7 ms	9088 KB	Output is correct
42	Correct	8 ms	9088 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9088 KB	Output is correct
2	Correct	6 ms	9088 KB	Output is correct
3	Correct	7 ms	9088 KB	Output is correct
4	Correct	10 ms	9088 KB	Output is correct
5	Correct	9 ms	9088 KB	Output is correct
6	Correct	8 ms	9088 KB	Output is correct
7	Correct	8 ms	9088 KB	Output is correct
8	Correct	9 ms	9088 KB	Output is correct
9	Correct	20 ms	9324 KB	Output is correct
10	Correct	20 ms	9560 KB	Output is correct
11	Correct	25 ms	9560 KB	Output is correct
12	Correct	6 ms	9560 KB	Output is correct
13	Correct	7 ms	9560 KB	Output is correct
14	Correct	7 ms	9560 KB	Output is correct
15	Correct	6 ms	9560 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	9560 KB	Output is correct
2	Correct	31 ms	9560 KB	Output is correct
3	Correct	31 ms	9560 KB	Output is correct
4	Correct	23 ms	9560 KB	Output is correct
5	Correct	22 ms	9560 KB	Output is correct
6	Correct	20 ms	9560 KB	Output is correct
7	Correct	27 ms	9560 KB	Output is correct
8	Correct	24 ms	9560 KB	Output is correct
9	Correct	20 ms	9560 KB	Output is correct
10	Correct	20 ms	9560 KB	Output is correct
11	Correct	20 ms	9560 KB	Output is correct
12	Correct	20 ms	9560 KB	Output is correct
13	Correct	20 ms	9560 KB	Output is correct
14	Correct	20 ms	9560 KB	Output is correct
15	Correct	26 ms	9560 KB	Output is correct
16	Correct	23 ms	9560 KB	Output is correct
17	Correct	22 ms	9560 KB	Output is correct
18	Correct	26 ms	9560 KB	Output is correct
19	Correct	22 ms	9560 KB	Output is correct
20	Correct	17 ms	9560 KB	Output is correct
21	Correct	18 ms	9560 KB	Output is correct
22	Correct	22 ms	9560 KB	Output is correct
23	Correct	22 ms	9560 KB	Output is correct
24	Correct	23 ms	9560 KB	Output is correct
25	Correct	22 ms	9560 KB	Output is correct
26	Correct	24 ms	9560 KB	Output is correct
27	Correct	20 ms	9560 KB	Output is correct
28	Correct	23 ms	9560 KB	Output is correct
29	Correct	27 ms	9560 KB	Output is correct
30	Correct	23 ms	9560 KB	Output is correct

Subtask #5

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	9560 KB	Output is correct
2	Correct	32 ms	9560 KB	Output is correct
3	Correct	38 ms	9560 KB	Output is correct
4	Correct	23 ms	9560 KB	Output is correct
5	Correct	20 ms	9560 KB	Output is correct
6	Correct	20 ms	9560 KB	Output is correct
7	Correct	22 ms	9560 KB	Output is correct
8	Correct	24 ms	9560 KB	Output is correct
9	Correct	23 ms	9560 KB	Output is correct
10	Correct	20 ms	9560 KB	Output is correct
11	Correct	22 ms	9560 KB	Output is correct
12	Correct	22 ms	9560 KB	Output is correct
13	Correct	20 ms	9560 KB	Output is correct
14	Correct	25 ms	9560 KB	Output is correct
15	Correct	26 ms	9560 KB	Output is correct
16	Correct	23 ms	9560 KB	Output is correct
17	Correct	22 ms	9560 KB	Output is correct
18	Correct	24 ms	9560 KB	Output is correct
19	Correct	23 ms	9560 KB	Output is correct
20	Correct	17 ms	9560 KB	Output is correct
21	Correct	17 ms	9560 KB	Output is correct
22	Correct	22 ms	9560 KB	Output is correct
23	Correct	20 ms	9560 KB	Output is correct
24	Correct	22 ms	9560 KB	Output is correct
25	Correct	20 ms	9560 KB	Output is correct
26	Correct	20 ms	9560 KB	Output is correct
27	Correct	22 ms	9560 KB	Output is correct
28	Correct	22 ms	9560 KB	Output is correct
29	Correct	23 ms	9560 KB	Output is correct
30	Correct	22 ms	9560 KB	Output is correct
31	Correct	7 ms	9560 KB	Output is correct
32	Correct	6 ms	9560 KB	Output is correct
33	Correct	6 ms	9560 KB	Output is correct
34	Correct	6 ms	9560 KB	Output is correct
35	Correct	8 ms	9560 KB	Output is correct
36	Correct	6 ms	9560 KB	Output is correct
37	Correct	6 ms	9560 KB	Output is correct
38	Correct	6 ms	9560 KB	Output is correct
39	Correct	7 ms	9560 KB	Output is correct
40	Correct	6 ms	9560 KB	Output is correct
41	Correct	7 ms	9560 KB	Output is correct
42	Correct	6 ms	9560 KB	Output is correct