oj.uz

Submission #51490

# Submission time Handle Problem Language Result Execution time Memory
51490 2018-06-18T04:17:27 Z shoemakerjo Amusement Park (JOI17_amusement_park) C++14
0 / 100
 46 ms 15964 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 <= 113);
	// 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 6112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12524 KB Output is correct
2 Correct 34 ms 13944 KB Output is correct
3 Correct 46 ms 14132 KB Output is correct
4 Correct 33 ms 14208 KB Output is correct
5 Correct 25 ms 14224 KB Output is correct
6 Correct 33 ms 14240 KB Output is correct
7 Correct 25 ms 14240 KB Output is correct
8 Correct 23 ms 14240 KB Output is correct
9 Correct 22 ms 14240 KB Output is correct
10 Runtime error 27 ms 14904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15568 KB Output is correct
2 Runtime error 9 ms 15568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15568 KB Output is correct
2 Correct 33 ms 15568 KB Output is correct
3 Correct 35 ms 15568 KB Output is correct
4 Correct 25 ms 15568 KB Output is correct
5 Correct 27 ms 15568 KB Output is correct
6 Correct 20 ms 15568 KB Output is correct
7 Correct 23 ms 15568 KB Output is correct
8 Correct 28 ms 15568 KB Output is correct
9 Correct 24 ms 15568 KB Output is correct
10 Runtime error 24 ms 15568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 15964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -