oj.uz

답안 #298163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298163 2020-09-12T13:02:13 Z pit4h Amusement Park (JOI17_amusement_park) C++14
0 / 100
 10 ms 1924 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))>0) {
		MessageBoard(x, 1);
	}
	else {
		MessageBoard(x, 0);
	}
	if(bit>=_B-1) return;
	for(int i: g[x]) {
		if(!vis[i] && par[i] == x) {
			bit++;
			if(dep[i]%_B!=0 && bit<_B) 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) {
		if(A[i] !=i || B[i] != i+1) assert(false);
		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, 1);
		}
	}
}
#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);
		}
	}
}
int cnt;
map<int, int> Map[__N];
int cur_pos;
int mv(int x) {
	cnt++;
	if(!Map[cur_pos][x] || cnt > 200) assert(false);
	cur_pos = x;
	return Move(x);
}
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) get_X(i, mv(i), bit, X, vis, g, par);
		}
	}
	if(par[x] != x && bit < bits-1) {
		mv(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) {
		Map[A[i]][B[i]] = 1;
		Map[B[i]][A[i]] = 1;
		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);
	cur_pos = P;
	while(dep[P]%bits != 0) {
		P = par[P];
		V = mv(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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 1664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1544 KB Output is correct
2 Correct 2 ms 1924 KB Output is correct
3 Incorrect 2 ms 1668 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 1664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 1664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -