Submission #51487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51487	2018-06-18T04:13:11 Z	shoemakerjo	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	36 ms	9848 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


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

	
int move(int loc) {
	// 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;
	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	7 ms	3776 KB	Output is correct
2	Correct	7 ms	6288 KB	Output is correct
3	Correct	6 ms	6304 KB	Output is correct
4	Correct	7 ms	6436 KB	Output is correct
5	Correct	7 ms	6552 KB	Output is correct
6	Correct	6 ms	6552 KB	Output is correct
7	Correct	6 ms	6552 KB	Output is correct
8	Correct	7 ms	6552 KB	Output is correct
9	Correct	6 ms	6640 KB	Output is correct
10	Correct	6 ms	6728 KB	Output is correct
11	Correct	9 ms	6728 KB	Output is correct
12	Correct	7 ms	6728 KB	Output is correct
13	Correct	6 ms	6728 KB	Output is correct
14	Correct	7 ms	6728 KB	Output is correct
15	Correct	6 ms	6728 KB	Output is correct
16	Correct	7 ms	6728 KB	Output is correct
17	Correct	6 ms	6776 KB	Output is correct
18	Correct	6 ms	6824 KB	Output is correct

Subtask #2

10.0 / 10.0

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

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9168 KB	Output is correct
2	Correct	7 ms	9168 KB	Output is correct
3	Correct	6 ms	9168 KB	Output is correct
4	Correct	8 ms	9168 KB	Output is correct
5	Correct	8 ms	9168 KB	Output is correct
6	Correct	9 ms	9168 KB	Output is correct
7	Correct	10 ms	9168 KB	Output is correct
8	Correct	10 ms	9168 KB	Output is correct
9	Correct	26 ms	9508 KB	Output is correct
10	Correct	18 ms	9848 KB	Output is correct
11	Correct	18 ms	9848 KB	Output is correct
12	Correct	7 ms	9848 KB	Output is correct
13	Correct	7 ms	9848 KB	Output is correct
14	Correct	7 ms	9848 KB	Output is correct
15	Correct	6 ms	9848 KB	Output is correct

Subtask #4

55.0 / 55.0

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

Subtask #5

17.0 / 17.0

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