oj.uz

Submission #257852

# Submission time Handle Problem Language Result Execution time Memory
257852 2020-08-04T22:37:57 Z Blagojce Amusement Park (JOI17_amusement_park) C++17
10 / 100
 39 ms 14508 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int i_inf = 1e9;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 1e5;
 
#include "Joi.h"
/*int VAL[mxn];
void MessageBoard(int u, int val){
	VAL[u] = val;
	return;
}*/
 
int n, m;
int a[mxn], b[mxn];
bool vis[mxn];
vector<int> g[mxn];
 
int itopos[mxn];
int temp_p = 0;
 
int depth[mxn];
int mx_depth[mxn];
int best_child[mxn];

vector<int> G[mxn];

void dfs(int u){
	itopos[u] = temp_p++;
	vis[u] = true;
	mx_depth[u] = depth[u];
	best_child[u] = u;
	for(auto e : g[u]){
		if(vis[e]) continue;
		depth[e] = depth[u] + 1;
		G[u].pb(e);
		
		dfs(e);
		if(mx_depth[u] < mx_depth[e]){
			mx_depth[u] = mx_depth[e];
			best_child[u] = e;
		}
	}
}
int REM;
int pos_to_mark;
ll x;
void dfs2(int u, int flag){
	if(flag == 0){
		if(x&(1LL<<pos_to_mark)) MessageBoard(u, 1);
		else MessageBoard(u, 0);
		++pos_to_mark;
	}
	else{
		if(REM > 0){
			if(x&(1LL<<pos_to_mark)) MessageBoard(u, 1);
			else MessageBoard(u, 0);
			++pos_to_mark;
			--REM;
		}
		else{
			MessageBoard(u, 0);
		}
	}
	if(flag == 1){
		for(auto e : G[u]){
			dfs2(e, 1);
		}
	}
	else{
		for(auto e : G[u]){
			if(e == best_child[u]) continue;
			dfs2(e, 1);
		}
		dfs2(best_child[u], 0);
	}
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	n = N, m = M, x = X;
	fr(i, 0, m) a[i] = A[i], b[i] = B[i];
	fr(i, 0, m){
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	dfs(0);
	int mxd = 0;
	fr(i, 0, n) mxd = max(mxd, depth[i]);
	if(mxd < 59){
		REM = 60 - (mx_depth[0]+1);
		dfs2(0, 0);
		/*fr(i, 0, n){
			if(X&(1LL<<(itopos[i]%60))) MessageBoard(i,1); 
			else MessageBoard(i,0);
		}*/
	}
	else{
		fr(i, 0, n){
			if(X&(1LL<<(depth[i]%60)))MessageBoard(i,1); 
			else MessageBoard(i,0);
		}
	}
	
}

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int i_inf = 1e9;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 1e5;
#include "Ioi.h"
/*
int mark[60] = {1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int Move(int u){
	cout<<u<<endl;
	return mark[u];
}*/

int n, m;
int a[mxn], b[mxn];
bool vis[mxn];
vector<int> g[mxn];

int postoi[mxn];
int temp_p = 0;

vector<int> v;

int val[mxn];
int parent[mxn];
int depth[mxn];
int mx_depth[mxn];

int best_child[mxn];
vector<int> G[mxn];

void dfs(int u, int p){
	parent[u] = p;
	postoi[temp_p] = u;
	++temp_p;
	
	vis[u] = true;
	mx_depth[u] = depth[u];
	best_child[u] = u;
	for(auto e : g[u]){
		if(vis[e]) continue;		
		G[u].pb(e);
		
		depth[e] = depth[u] + 1;
		dfs(e, u);
		if(mx_depth[e] > mx_depth[u]){
			mx_depth[u] = mx_depth[e];
			best_child[u] = e;
		}
	
	}
}
/*
int loc_pos;
void dfs2(int u, int p, int tv){
	loc_pos ++;
	val[u] = tv;
	vis[u] = true;
	if(loc_pos == 60) return;
	
	for(auto e : g[u]){
		if(vis[e]) continue;
		dfs2(e, u, Move(e));
		if(loc_pos == 60) return;
	}
	
	if(u != p) Move(parent[u]);
}*/

int REM;
int pos_to_mark;
ll x;
void dfs2(int u, int flag, int tv){
	
	x |= (1LL<<pos_to_mark)*tv;
	++pos_to_mark;
	if(pos_to_mark == 60) return;
	
	if(flag == 1){
		--REM;
		if(REM == 0){
			Move(parent[u]);
			return;
		}
	}
	
	if(flag == 1){
		for(auto e : G[u]){
			dfs2(e, 1, Move(e));
			if(REM == 0) break;
		}
		Move(parent[u]);
	}
	else{
		for(auto e : G[u]){
			if(e == best_child[u]) continue;
			dfs2(e, 1, Move(e));
			if(REM == 0) break;
		}
		dfs2(best_child[u], 0, Move(best_child[u]));
		return;
	}
}


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	n = N, m = M;
	fr(i, 0, m) a[i] = A[i], b[i] = B[i];
	fr(i, 0, m){
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	dfs(0, 0);
	
	if(mx_depth[0] < 59){	
		while(P != 0) V = Move(parent[P]), P = parent[P];
		
		REM = 60 - (mx_depth[0]+1);
		dfs2(0, 0, V);
		
		/*while(P != 0) V = Move(parent[P]), P = parent[P];
		val[0] = V;
		
		memset(vis, false, sizeof(vis));
		dfs2(0, 0, V);
		
		ll X = 0;
		fr(i, 0, 60){
			X |= (1LL<<i)*val[postoi[i]];
		}*/
		return x;
	}
	else{
		while(depth[P]%60 != 0) V = Move(parent[P]), P = parent[P];
		ll X = 0;
		if(mx_depth[P]-depth[P]<59){
			fr(i, 0, 60){
				V = Move(parent[P]);
				P = parent[P];
				X  |= (1LL<<(59-i))*V;
			}
		}
		else{
			X |= (1LL << 0)*V;
			fr(i, 1, 60){
				V = Move(best_child[P]);
				P = best_child[P];
				X |= (1LL<<i)*V;
			}
		}
		return X;
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 10368 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14508 KB Output is correct
2 Correct 35 ms 14488 KB Output is correct
3 Correct 39 ms 14436 KB Output is correct
4 Incorrect 13 ms 12032 KB Wrong Answer [2]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10244 KB Output is correct
2 Correct 7 ms 10244 KB Output is correct
3 Correct 6 ms 10404 KB Output is correct
4 Correct 10 ms 10788 KB Output is correct
5 Correct 11 ms 11016 KB Output is correct
6 Correct 9 ms 11008 KB Output is correct
7 Correct 8 ms 10916 KB Output is correct
8 Correct 9 ms 10916 KB Output is correct
9 Correct 20 ms 14220 KB Output is correct
10 Correct 25 ms 14028 KB Output is correct
11 Correct 22 ms 14208 KB Output is correct
12 Correct 6 ms 10492 KB Output is correct
13 Correct 8 ms 10372 KB Output is correct
14 Correct 7 ms 10492 KB Output is correct
15 Correct 7 ms 10244 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14424 KB Output is correct
2 Correct 38 ms 14440 KB Output is correct
3 Correct 36 ms 14492 KB Output is correct
4 Incorrect 13 ms 12032 KB Wrong Answer [2]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 14308 KB Output is correct
2 Correct 36 ms 14496 KB Output is correct
3 Correct 36 ms 14500 KB Output is correct
4 Incorrect 13 ms 12032 KB Wrong Answer [2]
5 Halted 0 ms 0 KB -