oj.uz

Submission #51428

# Submission time Handle Problem Language Result Execution time Memory
51428 2018-06-18T01:58:44 Z shoemakerjo Amusement Park (JOI17_amusement_park) C++14
10 / 100
 69 ms 9264 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[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 (!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 6 ms 3516 KB Output is correct
2 Correct 6 ms 5788 KB Output is correct
3 Correct 6 ms 5820 KB Output is correct
4 Correct 6 ms 5832 KB Output is correct
5 Correct 7 ms 5868 KB Output is correct
6 Correct 7 ms 5948 KB Output is correct
7 Correct 7 ms 6144 KB Output is correct
8 Correct 7 ms 6296 KB Output is correct
9 Incorrect 6 ms 6296 KB Wrong Answer [7]
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7472 KB Output is correct
2 Correct 31 ms 8648 KB Output is correct
3 Correct 33 ms 8648 KB Output is correct
4 Correct 28 ms 8648 KB Output is correct
5 Correct 30 ms 8648 KB Output is correct
6 Correct 22 ms 8648 KB Output is correct
7 Correct 27 ms 8656 KB Output is correct
8 Correct 28 ms 8664 KB Output is correct
9 Correct 28 ms 8664 KB Output is correct
10 Correct 65 ms 8664 KB Output is correct
11 Correct 69 ms 8664 KB Output is correct
12 Correct 23 ms 8664 KB Output is correct
13 Correct 23 ms 8664 KB Output is correct
14 Correct 25 ms 8664 KB Output is correct
15 Correct 26 ms 8664 KB Output is correct
16 Correct 27 ms 8664 KB Output is correct
17 Correct 28 ms 8664 KB Output is correct
18 Incorrect 33 ms 8664 KB Wrong Answer [8]
19 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8664 KB Output is correct
2 Correct 6 ms 8664 KB Output is correct
3 Correct 7 ms 8664 KB Output is correct
4 Correct 8 ms 8664 KB Output is correct
5 Correct 10 ms 8664 KB Output is correct
6 Correct 8 ms 8664 KB Output is correct
7 Correct 9 ms 8664 KB Output is correct
8 Correct 11 ms 8664 KB Output is correct
9 Correct 19 ms 8964 KB Output is correct
10 Correct 19 ms 9264 KB Output is correct
11 Correct 19 ms 9264 KB Output is correct
12 Correct 6 ms 9264 KB Output is correct
13 Correct 6 ms 9264 KB Output is correct
14 Correct 6 ms 9264 KB Output is correct
15 Correct 6 ms 9264 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9264 KB Output is correct
2 Correct 31 ms 9264 KB Output is correct
3 Correct 31 ms 9264 KB Output is correct
4 Incorrect 25 ms 9264 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9264 KB Output is correct
2 Correct 32 ms 9264 KB Output is correct
3 Correct 32 ms 9264 KB Output is correct
4 Incorrect 25 ms 9264 KB Output isn't correct
5 Halted 0 ms 0 KB -