oj.uz

답안 #298174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298174 2020-09-12T13:42:15 Z pit4h Amusement Park (JOI17_amusement_park) C++14
10 / 100
 19 ms 6108 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], subt[_N];
vector<int> roots;
ll X;
void dfs(int x) {
	vis[x] = 1;
	subt[x] = 1;
	for(int i: g[x]) {
		if(!vis[i]) {
			par[i] = x;
			dep[i] = dep[x]+1;
			dfs(i);
			subt[x] += subt[i];
		}
	}
	if(dep[x]%_B==0 && subt[x] >= _B) {
		roots.push_back(x);
	}
}
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;
int _subt[__N];
void _dfs(int x, vector<int>& vis, vector<vector<int>>& g, vector<int>& par, vector<int>& dep) {
	vis[x] = 1;
	_subt[x] = 1;
	for(int i: g[x]) {
		if(!vis[i]) {
			par[i] = x;
			dep[i] = dep[x]+1;
			_dfs(i, vis, g, par, dep);
			_subt[x] += _subt[i];
		}
	}
}
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 || _subt[P] < bits) {
		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 1792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1800 KB Output is correct
2 Correct 2 ms 1544 KB Output is correct
3 Correct 2 ms 1780 KB Output is correct
4 Correct 5 ms 2324 KB Output is correct
5 Correct 4 ms 2460 KB Output is correct
6 Correct 4 ms 2244 KB Output is correct
7 Correct 4 ms 2396 KB Output is correct
8 Correct 4 ms 2256 KB Output is correct
9 Correct 18 ms 5820 KB Output is correct
10 Correct 19 ms 5976 KB Output is correct
11 Correct 19 ms 6108 KB Output is correct
12 Correct 2 ms 1448 KB Output is correct
13 Correct 2 ms 1672 KB Output is correct
14 Correct 2 ms 1740 KB Output is correct
15 Correct 2 ms 1684 KB Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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