oj.uz

Submission #51431

# Submission time Handle Problem Language Result Execution time Memory
51431 2018-06-18T02:04:25 Z shoemakerjo Amusement Park (JOI17_amusement_park) C++14
10 / 100
 40 ms 9216 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


#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[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);
	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 6 ms 3252 KB Output is correct
2 Correct 6 ms 5568 KB Output is correct
3 Correct 8 ms 5824 KB Output is correct
4 Correct 6 ms 6116 KB Output is correct
5 Correct 7 ms 6232 KB Output is correct
6 Correct 7 ms 6232 KB Output is correct
7 Correct 7 ms 6232 KB Output is correct
8 Correct 6 ms 6316 KB Output is correct
9 Correct 6 ms 6400 KB Output is correct
10 Correct 7 ms 6400 KB Output is correct
11 Correct 11 ms 6400 KB Output is correct
12 Correct 6 ms 6400 KB Output is correct
13 Correct 6 ms 6400 KB Output is correct
14 Correct 6 ms 6400 KB Output is correct
15 Incorrect 6 ms 6400 KB Wrong Answer [7]
16 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7480 KB Output is correct
2 Correct 32 ms 8560 KB Output is correct
3 Correct 32 ms 8564 KB Output is correct
4 Correct 25 ms 8568 KB Output is correct
5 Correct 20 ms 8568 KB Output is correct
6 Correct 28 ms 8568 KB Output is correct
7 Correct 26 ms 8576 KB Output is correct
8 Correct 27 ms 8584 KB Output is correct
9 Correct 28 ms 8584 KB Output is correct
10 Correct 32 ms 8584 KB Output is correct
11 Correct 22 ms 8584 KB Output is correct
12 Correct 27 ms 8584 KB Output is correct
13 Correct 25 ms 8584 KB Output is correct
14 Correct 24 ms 8584 KB Output is correct
15 Incorrect 31 ms 8584 KB Wrong Answer [7]
16 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8584 KB Output is correct
2 Correct 6 ms 8584 KB Output is correct
3 Correct 5 ms 8584 KB Output is correct
4 Correct 8 ms 8584 KB Output is correct
5 Correct 7 ms 8584 KB Output is correct
6 Correct 7 ms 8584 KB Output is correct
7 Correct 7 ms 8584 KB Output is correct
8 Correct 8 ms 8584 KB Output is correct
9 Correct 19 ms 8896 KB Output is correct
10 Correct 18 ms 9212 KB Output is correct
11 Correct 18 ms 9216 KB Output is correct
12 Correct 6 ms 9216 KB Output is correct
13 Correct 6 ms 9216 KB Output is correct
14 Correct 6 ms 9216 KB Output is correct
15 Correct 6 ms 9216 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9216 KB Output is correct
2 Correct 31 ms 9216 KB Output is correct
3 Correct 31 ms 9216 KB Output is correct
4 Correct 27 ms 9216 KB Output is correct
5 Correct 24 ms 9216 KB Output is correct
6 Correct 20 ms 9216 KB Output is correct
7 Correct 20 ms 9216 KB Output is correct
8 Correct 28 ms 9216 KB Output is correct
9 Correct 23 ms 9216 KB Output is correct
10 Correct 29 ms 9216 KB Output is correct
11 Correct 27 ms 9216 KB Output is correct
12 Correct 25 ms 9216 KB Output is correct
13 Partially correct 20 ms 9216 KB Partially correct
14 Incorrect 22 ms 9216 KB Wrong Answer [7]
15 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9216 KB Output is correct
2 Correct 33 ms 9216 KB Output is correct
3 Correct 33 ms 9216 KB Output is correct
4 Correct 27 ms 9216 KB Output is correct
5 Correct 28 ms 9216 KB Output is correct
6 Correct 24 ms 9216 KB Output is correct
7 Correct 24 ms 9216 KB Output is correct
8 Correct 25 ms 9216 KB Output is correct
9 Correct 25 ms 9216 KB Output is correct
10 Correct 31 ms 9216 KB Output is correct
11 Incorrect 22 ms 9216 KB Wrong Answer [7]
12 Halted 0 ms 0 KB -