oj.uz

Submission #257020

# Submission time Handle Problem Language Result Execution time Memory
257020 2020-08-03T14:02:54 Z Blagojce Amusement Park (JOI17_amusement_park) C++17
0 / 100
 14 ms 7424 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 n, m;

vector<int> g[mxn];

int depth[mxn];
int mx_depth[mxn];

int parent[mxn];

void dfs(int u, int p){
	
	parent[u] = p;
	mx_depth[u] = depth[u];
	
	for(auto e : g[u]){
		if(e == p) continue;
		depth[e] = depth[u]+1;
		dfs(e, u);
		mx_depth[u] = max(mx_depth[u], mx_depth[e]);
	}
}



int pos;
ll res;
void dfs2(int u, int p){
	if(res & (1 << pos)) MessageBoard(u, 1);
	else MessageBoard(u, 0);
	
	++pos;
	pos %= 60;
	for(auto e : g[u]){
		if(e == p) continue;
		dfs2(u, e);	
	}
}
void mark_tree(){
	dfs(0, 0);
	if(mx_depth[0] < 59){
		dfs2(0, 0); 
	}
	else{
		fr(i, 0, n){
			if(res&(1<<(depth[i]%60))) MessageBoard(i, 1);
			else MessageBoard(i, 0); 
		}
	}
}


int link[mxn];
int sz[mxn];
int cnt = 0;
int findx(int x){
	if(link[x] == x) return x;
	else{
		link[x] = findx(link[x]);
		return link[x];
	}
}
void unite(int a, int b){
	a = findx(a);
	b = findx(b);
	if(a == b) return;
	g[a].pb(b);
	g[b].pb(a);
	++cnt;
	if(sz[a] < sz[b]) swap(a, b);
	link[b] = link[a];
	sz[a] += sz[b];
}

int a[mxn], b[mxn];
void build_tree(){
	fr(i, 0, n) link[i] = i, sz[i] = 1;
	fr(i, 0, m){
		unite(a[i], b[i]);
	}
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	res = X;
	n = N, m = M;
	fr(i, 0, M) a[i] = A[i], b[i] = B[i];
	build_tree();
	
	mark_tree();
}

#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"

vector<int> g[mxn];

int depth[mxn];
int mx_depth[mxn];

int parent[mxn];

void dfs(int u, int p){
	
	parent[u] = p;
	mx_depth[u] = depth[u];
	
	for(auto e : g[u]){
		if(e == p) continue;
		depth[e] = depth[u]+1;
		dfs(e, u);
		mx_depth[u] = max(mx_depth[u], mx_depth[e]);
	}
}
ll res;
int pos;
void dfs2(int u, int p, int val){
	if(pos > 59) return;
	res |= (val << pos);
	++pos;
	if(pos > 59) return;
	for(auto e : g[u]){
		if(e == p) continue;
		dfs2(u, e, Move(e));	
		if(pos > 59) return;
	}
	if(u != p) Move(p);
}

void edge_case(int val){
	dfs2(0, 0, val);
}

void solve_tree(int x, int val){
	dfs(0, 0);
	
	while(depth[x] % 60 != 0)val = Move(parent[x]), x = parent[x];
	
	
	if(mx_depth[x] < 59){
		if(x == 0) edge_case(val);
		else{
			val = Move(parent[x]);
			x = parent[x];
			fr(i, 0, 60){
				res |= (val << (59-i));
				val = Move(parent[x]);
				x = parent[x];
			}
		}
	}
	else{
		
		fr(i, 0, 60){
			res |= (val << i);
			int id = -1;
			for(auto u : g[x]){
				if(u == parent[x]) continue;
				if(mx_depth[x] == mx_depth[u]+1){
					id = u;
					break;
				}
			}
			if(id == -1) break;
			val = Move(id);
			x = id;
		}
	}
}
int link[mxn];
int sz[mxn];
int findx(int x){
	if(link[x] == x) return x;
	else{
		link[x] = findx(link[x]);
		return link[x];
	}
}
void unite(int a, int b){
	a = findx(a);
	b = findx(b);
	if(a == b) return;
	g[a].pb(b);
	g[b].pb(a);
	if(sz[a] < sz[b]) swap(a, b);
	link[b] = link[a];
	sz[a] += sz[b];
}
int n, m;
int a[mxn], b[mxn];
void build_tree(){
	fr(i, 0, n) link[i] = i, sz[i] = 1;
	fr(i, 0, m){
		unite(a[i], b[i]);
	}
}
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];
	build_tree();
	solve_tree(P, V);
	return res;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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