Submission #51429

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51429	2018-06-18T02:00:37 Z	shoemakerjo	Amusement Park (JOI17_amusement_park)	C++14	73 / 100	40 ms	9512 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] = 0;
	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 (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[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[v]) {
					loc = v;
					bit[label[loc]] = move(loc);
					fin = true;
					// alseen[v] = true;
					break;
				}
				// alseen[loc] = true;
			}
			if (!fin) alseen[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);
	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

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3484 KB	Output is correct
2	Correct	6 ms	6016 KB	Output is correct
3	Correct	7 ms	6328 KB	Output is correct
4	Correct	6 ms	6328 KB	Output is correct
5	Correct	7 ms	6328 KB	Output is correct
6	Correct	6 ms	6328 KB	Output is correct
7	Correct	7 ms	6328 KB	Output is correct
8	Correct	6 ms	6328 KB	Output is correct
9	Incorrect	6 ms	6328 KB	Wrong Answer [7]
10	Halted	0 ms	0 KB	-

Subtask #2

10.0 / 10.0

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

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	8784 KB	Output is correct
2	Correct	6 ms	8784 KB	Output is correct
3	Correct	6 ms	8784 KB	Output is correct
4	Correct	8 ms	8784 KB	Output is correct
5	Correct	8 ms	8784 KB	Output is correct
6	Correct	8 ms	8784 KB	Output is correct
7	Correct	9 ms	8784 KB	Output is correct
8	Correct	8 ms	8784 KB	Output is correct
9	Correct	22 ms	9056 KB	Output is correct
10	Correct	20 ms	9420 KB	Output is correct
11	Correct	17 ms	9512 KB	Output is correct
12	Correct	8 ms	9512 KB	Output is correct
13	Correct	6 ms	9512 KB	Output is correct
14	Correct	5 ms	9512 KB	Output is correct
15	Correct	7 ms	9512 KB	Output is correct

Subtask #4

53.0 / 55.0

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

Subtask #5

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	9512 KB	Output is correct
2	Correct	33 ms	9512 KB	Output is correct
3	Correct	31 ms	9512 KB	Output is correct
4	Correct	20 ms	9512 KB	Output is correct
5	Correct	27 ms	9512 KB	Output is correct
6	Correct	28 ms	9512 KB	Output is correct
7	Correct	22 ms	9512 KB	Output is correct
8	Correct	20 ms	9512 KB	Output is correct
9	Correct	22 ms	9512 KB	Output is correct
10	Correct	23 ms	9512 KB	Output is correct
11	Correct	19 ms	9512 KB	Output is correct
12	Incorrect	20 ms	9512 KB	Output isn't correct
13	Halted	0 ms	0 KB	-