oj.uz

Submission #69663

# Submission time Handle Problem Language Result Execution time Memory
69663 2018-08-21T11:12:07 Z zadrga Amusement Park (JOI17_amusement_park) C++14
0 / 100
 56 ms 17640 KB 
// 13.10 + 100 min

#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (2e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 10111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

vector<int> adj[maxn], tree[maxn], one, two, v;
int col[maxn], par[maxn], dep[maxn], max_dep, max_ind, cnt;
bool used[maxn];

void DFS(int x){
	used[x] = 1;
	if(max_dep < dep[x]){
		max_dep = dep[x];
		max_ind = x;
	}

	for(int u : adj[x]){
		if(!used[u]){
			tree[x].pb(u);
			dep[u] = dep[x] + 1;
			par[u] = x;
			DFS(u);
		}
	}
}

void colorBig(int x, ll num){
	int pos = dep[x] % 60;
	int val = (num >> pos) & 1;
	col[x] = val;

	for(int u : tree[x])
		colorBig(u, num);
}

void colorSmall(int x){
	v.pb(x);

	int last = -1;
	for(int u : tree[x]){
		if(used[u]){
			last = u;
			continue;
		}

		if(cnt <= 0)
			continue;
		
		cnt--;
		colorSmall(u);
	}

	if(last != -1)
		colorSmall(last);
}

void Joi(int N, int M, int A[], int B[], long long X, int T){
//	cout << "ans: " << X << endl;
	memset(col, 0, sizeof(col));
	for(int i = 0; i < M; i++){
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}

	par[0] = -1;
	dep[0] = 0;
	max_dep = -1;
	DFS(0);

	if(max_dep >= 59)
		colorBig(0, X);
	else{
		memset(used, 0, sizeof(used));
		int cur = max_ind;
		while(cur != -1){
			one.pb(cur);
			used[cur] = 1;
 			cur = par[cur];
		}

		cnt = 60 - one.size();
		colorSmall(0);

		sort(v.begin(), v.end());

		for(int i = 0; i < v.size(); i++)
			col[v[i]] = (X >> i) & 1;
	}

	for(int i = 0; i < N; i++)
		MessageBoard(i, col[i]);
}
#include "Ioi.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (2e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 10011

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;


vector<int> adj1[maxn], tree1[maxn], one1, two1, v1;
int col1[maxn], par1[maxn], dep1[maxn], max_dep1, max_ind1, cnt1;
bool used1[maxn];

void DFS1(int x){
	used1[x] = 1;
	if(max_dep1 < dep1[x]){
		max_dep1 = dep1[x];
		max_ind1 = x;
	}

	for(int u : adj1[x]){
		if(!used1[u]){
			tree1[x].pb(u);
			dep1[u] = dep1[x] + 1;
			par1[u] = x;
			DFS1(u);
		}
	}
}

void getSmall(int x){
	v1.pb(x);

	int last = -1;
	for(int u : tree1[x]){
		if(used1[u]){
			last = u;
			continue;
		}

		if(cnt1 <= 0)
			continue;

		cnt1--;
		col1[u] = Move(u);
		getSmall(u);
		col1[x] = Move(x);
	}

	if(last != -1){
		col1[last] = Move(last);
		getSmall(last);
	}
}


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	ll ans = 0;
	memset(col1, 0, sizeof(col1));
	for(int i = 0; i < M; i++){
		adj1[A[i]].pb(B[i]);
		adj1[B[i]].pb(A[i]);
	}

	par1[0] = -1;
	dep1[0] = 0;
	max_dep1 = -1;
	DFS1(0);

	memset(used1, 0, sizeof(used1));
	int cur = max_ind1;
	while(cur != -1){
		one1.pb(cur);
		used1[cur] = 1;
		cur = par1[cur];
	}

	reverse(one1.begin(), one1.end());

	if(max_dep1 >= 59){
		if(dep1[P] >= 59){	// just go up
	//		cout << "opt1" << endl;
			int cur = P;
			int pos = dep1[cur] % 60;
			int val = V;

			ans += (1LL << pos) * val;
			for(int i = 1; i < 60; i++){
				cur = par1[cur];
				val = Move(cur);
				pos = dep1[cur] % 60;
				ans += (1LL << pos) * val;
			}
		}
		else{
		//	cout << "opt2" << endl;
			cur = par1[P];	// go to 1 and then down
			while(cur != -1){
				V = Move(cur);
				cout << V << endl;
				cur = par1[cur];
			}

			int cur = 0;
			int pos = dep1[cur] % 60;
			int val = V;
			ans += (1LL << pos) * val;
			for(int i = 1; i < 60; i++){
				cur = one1[i];
				val = Move(cur);
				pos = dep1[cur] % 60;
				ans += (1LL << pos) * val;
			}
		}
	}
	else{
//		cout << "opt3" << endl;
		int cur = par1[P];	// Move to 1 and then do DFS traversal
		while(cur != -1){
			V = Move(cur);
			cur = par1[cur];
		}

		cnt1 = 60 - one1.size();
		col1[0] = V; 
		getSmall(0);

		sort(v1.begin(), v1.end());
		for(int i = 0; i < v1.size(); i++)
			ans += col1[v1[i]] * (1LL << i);
	}
//	cout << "my ans: " << ans << endl;
	return ans;
}

Compilation message

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:138:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v1.size(); i++)
                  ~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1776 KB Output is correct
2 Correct 6 ms 2008 KB Output is correct
3 Correct 8 ms 2240 KB Output is correct
4 Incorrect 7 ms 2432 KB Do not print anything on standard output.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6324 KB Output is correct
2 Correct 43 ms 6872 KB Output is correct
3 Correct 39 ms 7284 KB Output is correct
4 Correct 31 ms 7304 KB Output is correct
5 Correct 39 ms 7304 KB Output is correct
6 Correct 26 ms 7304 KB Output is correct
7 Correct 30 ms 7304 KB Output is correct
8 Correct 27 ms 7304 KB Output is correct
9 Correct 30 ms 7360 KB Output is correct
10 Correct 24 ms 7360 KB Output is correct
11 Correct 26 ms 7360 KB Output is correct
12 Correct 23 ms 7360 KB Output is correct
13 Correct 23 ms 7360 KB Output is correct
14 Correct 27 ms 7368 KB Output is correct
15 Correct 29 ms 8008 KB Output is correct
16 Correct 27 ms 8200 KB Output is correct
17 Correct 28 ms 8200 KB Output is correct
18 Correct 32 ms 8412 KB Output is correct
19 Correct 31 ms 8540 KB Output is correct
20 Correct 27 ms 9692 KB Output is correct
21 Correct 28 ms 9812 KB Output is correct
22 Incorrect 31 ms 9904 KB Do not print anything on standard output.
23 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9904 KB Do not print anything on standard output.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11240 KB Output is correct
2 Correct 49 ms 11608 KB Output is correct
3 Correct 56 ms 11872 KB Output is correct
4 Correct 27 ms 11904 KB Output is correct
5 Correct 34 ms 11936 KB Output is correct
6 Incorrect 31 ms 11968 KB Do not print anything on standard output.
7 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12920 KB Output is correct
2 Correct 40 ms 13336 KB Output is correct
3 Correct 38 ms 13696 KB Output is correct
4 Correct 32 ms 13848 KB Output is correct
5 Correct 27 ms 14024 KB Output is correct
6 Correct 26 ms 14160 KB Output is correct
7 Correct 27 ms 14160 KB Output is correct
8 Correct 27 ms 14160 KB Output is correct
9 Correct 24 ms 14160 KB Output is correct
10 Correct 23 ms 14160 KB Output is correct
11 Correct 23 ms 14160 KB Output is correct
12 Correct 30 ms 14160 KB Output is correct
13 Correct 27 ms 14160 KB Output is correct
14 Correct 23 ms 14160 KB Output is correct
15 Correct 28 ms 14524 KB Output is correct
16 Correct 23 ms 14724 KB Output is correct
17 Correct 24 ms 14872 KB Output is correct
18 Correct 22 ms 14956 KB Output is correct
19 Correct 22 ms 15124 KB Output is correct
20 Correct 18 ms 15980 KB Output is correct
21 Correct 23 ms 16312 KB Output is correct
22 Correct 26 ms 16344 KB Output is correct
23 Correct 27 ms 16344 KB Output is correct
24 Correct 27 ms 16488 KB Output is correct
25 Correct 26 ms 16692 KB Output is correct
26 Correct 28 ms 16732 KB Output is correct
27 Correct 28 ms 17224 KB Output is correct
28 Correct 25 ms 17544 KB Output is correct
29 Correct 24 ms 17608 KB Output is correct
30 Correct 24 ms 17640 KB Output is correct
31 Correct 5 ms 17640 KB Output is correct
32 Correct 9 ms 17640 KB Output is correct
33 Correct 6 ms 17640 KB Output is correct
34 Correct 5 ms 17640 KB Output is correct
35 Incorrect 7 ms 17640 KB Do not print anything on standard output.
36 Halted 0 ms 0 KB -