oj.uz

Submission #298108

# Submission time Handle Problem Language Result Execution time Memory
298108 2020-09-12T11:59:15 Z pit4h Amusement Park (JOI17_amusement_park) C++14
0 / 100
 18 ms 3840 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int _N = 1e4+1, _B = 60;
vector<int> g[_N];
bool vis[_N];
int dep[_N], par[_N];
vector<int> roots;
ll X;
void dfs(int x) {
	vis[x] = 1;
	if(dep[x]%_B==0) {
		roots.push_back(x);
	}
	for(int i: g[x]) {
		if(!vis[i]) {
			par[i] = x;
			dep[i] = dep[x]+1;
			dfs(i);
		}
	}
}
void set_board(int x, int &bit) {
	vis[x] = 1;	
	if(X&(1LL<<bit)) {
		MessageBoard(x, 1);
	}
	else {
		MessageBoard(x, 0);
	}
	if(bit==_B-1) return;
	for(int i: g[x]) {
		if(!vis[i] && par[i] != x) {
			bit++;
			set_board(i, bit);
		}
	}
}
void Joi(int N, int M, int A[], int B[], ll _X, int T) {
	// MessageBoard();
	X = _X;
	for(int i=0; i<M; ++i) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	for(int i=0; i<N; ++i) {
		sort(g[i].begin(), g[i].end());
	}
	dfs(0);
	for(int i=0; i<N; ++i) vis[i] = 0;
	for(int i: roots) {
		int bit = 0;
		set_board(i, bit);
	}
	for(int i=0; i<N; ++i) {
		if(!vis[i]) {
			MessageBoard(i, 0);
		}
	}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int __N = 1e4+1;
const int bits = 60;
void _dfs(int x, vector<int>& vis, vector<vector<int>>& g, vector<int>& par, vector<int>& dep) {
	vis[x] = 1;
	for(int i: g[x]) {
		if(!vis[i]) {
			par[i] = x;
			dep[i] = dep[x]+1;
			_dfs(i, vis, g, par, dep);
		}
	}
}
void get_X(int x, int v, int& bit, ll& X, vector<int>& vis, vector<vector<int>>& g, vector<int>& par) { 
	vis[x] = 1;
	X += (ll)v * (1LL<<bit);
	if(bit==bits-1) return;
	for(int i: g[x]) {
		if(!vis[i] && par[i]==x) {
			bit++;
			if(bit < bits-1)get_X(i, Move(i), bit, X, vis, g, par);
		}
	}
	if(par[x] != x && bit < bits-1) {
		Move(par[x]);
	}
}	
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	vector<vector<int>> g(N);
	vector<int> vis(N), par(N), dep(N);
	for(int i=0; i<M; ++i) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	for(int i=0; i<N; ++i) {
		sort(g[i].begin(), g[i].end());
	}
	_dfs(0, vis, g, par, dep);
	while(dep[P]%bits != 0) {
		P = par[P];
		V = Move(P);
	}
	for(int i=0; i<N; ++i) {
		vis[i] = 0;
	}
	int bit = 0;
	ll X = 0;
	get_X(P, V, bit, X, vis, g, par);
	return X;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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