답안 #51496 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51496	2018-06-18T04:19:09 Z	shoemakerjo	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	40 ms	9728 KB

#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.

#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 <= 117);
	// 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

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	3644 KB	Output is correct
2	Correct	6 ms	6044 KB	Output is correct
3	Correct	6 ms	6120 KB	Output is correct
4	Correct	6 ms	6188 KB	Output is correct
5	Correct	7 ms	6200 KB	Output is correct
6	Correct	6 ms	6256 KB	Output is correct
7	Correct	6 ms	6436 KB	Output is correct
8	Correct	6 ms	6580 KB	Output is correct
9	Correct	6 ms	6616 KB	Output is correct
10	Correct	6 ms	6632 KB	Output is correct
11	Correct	9 ms	6632 KB	Output is correct
12	Correct	6 ms	6632 KB	Output is correct
13	Correct	7 ms	6648 KB	Output is correct
14	Correct	7 ms	6664 KB	Output is correct
15	Correct	6 ms	6664 KB	Output is correct
16	Correct	6 ms	6664 KB	Output is correct
17	Correct	6 ms	6664 KB	Output is correct
18	Correct	6 ms	6696 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	7852 KB	Output is correct
2	Correct	35 ms	8976 KB	Output is correct
3	Correct	31 ms	8976 KB	Output is correct
4	Correct	20 ms	8976 KB	Output is correct
5	Correct	27 ms	8976 KB	Output is correct
6	Correct	25 ms	8976 KB	Output is correct
7	Correct	22 ms	8976 KB	Output is correct
8	Correct	23 ms	8976 KB	Output is correct
9	Correct	20 ms	8976 KB	Output is correct
10	Correct	20 ms	8976 KB	Output is correct
11	Correct	20 ms	8976 KB	Output is correct
12	Correct	20 ms	8976 KB	Output is correct
13	Correct	20 ms	8976 KB	Output is correct
14	Correct	20 ms	8976 KB	Output is correct
15	Correct	24 ms	8976 KB	Output is correct
16	Correct	23 ms	8976 KB	Output is correct
17	Correct	22 ms	8976 KB	Output is correct
18	Correct	22 ms	8976 KB	Output is correct
19	Correct	22 ms	8976 KB	Output is correct
20	Correct	20 ms	8976 KB	Output is correct
21	Correct	20 ms	8976 KB	Output is correct
22	Correct	20 ms	8976 KB	Output is correct
23	Correct	20 ms	8976 KB	Output is correct
24	Correct	20 ms	8976 KB	Output is correct
25	Correct	20 ms	8976 KB	Output is correct
26	Correct	20 ms	8976 KB	Output is correct
27	Correct	23 ms	8976 KB	Output is correct
28	Correct	20 ms	8976 KB	Output is correct
29	Correct	20 ms	8976 KB	Output is correct
30	Correct	20 ms	8976 KB	Output is correct
31	Correct	6 ms	8976 KB	Output is correct
32	Correct	6 ms	8976 KB	Output is correct
33	Correct	7 ms	8976 KB	Output is correct
34	Correct	6 ms	8976 KB	Output is correct
35	Correct	6 ms	8976 KB	Output is correct
36	Correct	6 ms	8976 KB	Output is correct
37	Correct	6 ms	8976 KB	Output is correct
38	Correct	6 ms	8976 KB	Output is correct
39	Correct	6 ms	8976 KB	Output is correct
40	Correct	6 ms	8976 KB	Output is correct
41	Correct	7 ms	8976 KB	Output is correct
42	Correct	6 ms	8976 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	8976 KB	Output is correct
2	Correct	6 ms	8976 KB	Output is correct
3	Correct	7 ms	8976 KB	Output is correct
4	Correct	11 ms	8976 KB	Output is correct
5	Correct	8 ms	8976 KB	Output is correct
6	Correct	9 ms	8976 KB	Output is correct
7	Correct	8 ms	8976 KB	Output is correct
8	Correct	8 ms	8976 KB	Output is correct
9	Correct	18 ms	9224 KB	Output is correct
10	Correct	18 ms	9500 KB	Output is correct
11	Correct	19 ms	9628 KB	Output is correct
12	Correct	7 ms	9728 KB	Output is correct
13	Correct	8 ms	9728 KB	Output is correct
14	Correct	6 ms	9728 KB	Output is correct
15	Correct	6 ms	9728 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	9728 KB	Output is correct
2	Correct	33 ms	9728 KB	Output is correct
3	Correct	33 ms	9728 KB	Output is correct
4	Correct	22 ms	9728 KB	Output is correct
5	Correct	20 ms	9728 KB	Output is correct
6	Correct	22 ms	9728 KB	Output is correct
7	Correct	22 ms	9728 KB	Output is correct
8	Correct	22 ms	9728 KB	Output is correct
9	Correct	20 ms	9728 KB	Output is correct
10	Correct	20 ms	9728 KB	Output is correct
11	Correct	22 ms	9728 KB	Output is correct
12	Correct	20 ms	9728 KB	Output is correct
13	Correct	23 ms	9728 KB	Output is correct
14	Correct	20 ms	9728 KB	Output is correct
15	Correct	23 ms	9728 KB	Output is correct
16	Correct	24 ms	9728 KB	Output is correct
17	Correct	20 ms	9728 KB	Output is correct
18	Correct	23 ms	9728 KB	Output is correct
19	Correct	24 ms	9728 KB	Output is correct
20	Correct	18 ms	9728 KB	Output is correct
21	Correct	17 ms	9728 KB	Output is correct
22	Correct	24 ms	9728 KB	Output is correct
23	Correct	20 ms	9728 KB	Output is correct
24	Correct	22 ms	9728 KB	Output is correct
25	Correct	23 ms	9728 KB	Output is correct
26	Correct	20 ms	9728 KB	Output is correct
27	Correct	25 ms	9728 KB	Output is correct
28	Correct	22 ms	9728 KB	Output is correct
29	Correct	20 ms	9728 KB	Output is correct
30	Correct	20 ms	9728 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	9728 KB	Output is correct
2	Correct	40 ms	9728 KB	Output is correct
3	Correct	32 ms	9728 KB	Output is correct
4	Correct	27 ms	9728 KB	Output is correct
5	Correct	24 ms	9728 KB	Output is correct
6	Correct	24 ms	9728 KB	Output is correct
7	Correct	25 ms	9728 KB	Output is correct
8	Correct	22 ms	9728 KB	Output is correct
9	Correct	27 ms	9728 KB	Output is correct
10	Correct	23 ms	9728 KB	Output is correct
11	Correct	22 ms	9728 KB	Output is correct
12	Correct	20 ms	9728 KB	Output is correct
13	Correct	20 ms	9728 KB	Output is correct
14	Correct	23 ms	9728 KB	Output is correct
15	Correct	23 ms	9728 KB	Output is correct
16	Correct	25 ms	9728 KB	Output is correct
17	Correct	22 ms	9728 KB	Output is correct
18	Correct	22 ms	9728 KB	Output is correct
19	Correct	23 ms	9728 KB	Output is correct
20	Correct	26 ms	9728 KB	Output is correct
21	Correct	24 ms	9728 KB	Output is correct
22	Correct	20 ms	9728 KB	Output is correct
23	Correct	20 ms	9728 KB	Output is correct
24	Correct	22 ms	9728 KB	Output is correct
25	Correct	20 ms	9728 KB	Output is correct
26	Correct	20 ms	9728 KB	Output is correct
27	Correct	20 ms	9728 KB	Output is correct
28	Correct	20 ms	9728 KB	Output is correct
29	Correct	20 ms	9728 KB	Output is correct
30	Correct	24 ms	9728 KB	Output is correct
31	Correct	7 ms	9728 KB	Output is correct
32	Correct	6 ms	9728 KB	Output is correct
33	Correct	6 ms	9728 KB	Output is correct
34	Correct	6 ms	9728 KB	Output is correct
35	Correct	6 ms	9728 KB	Output is correct
36	Correct	6 ms	9728 KB	Output is correct
37	Correct	6 ms	9728 KB	Output is correct
38	Correct	6 ms	9728 KB	Output is correct
39	Correct	6 ms	9728 KB	Output is correct
40	Correct	7 ms	9728 KB	Output is correct
41	Correct	6 ms	9728 KB	Output is correct
42	Correct	6 ms	9728 KB	Output is correct

답안 #51496

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0