oj.uz

답안 #39809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39809 2018-01-19T08:39:11 Z aome Snowy Roads (JOI16_snowy) C++14
0 / 100
 15 ms 4212 KB 
#include <bits/stdc++.h>
#include "Anyalib.h"

using namespace std;

namespace A {
	const int N = 505;

	typedef pair<int, int> ii;

	int n;
	int par[N];
	int dis[N];
	int high[N];
	int edge[N];
	int start[N];
	vector<ii> G[N];
	vector<int> v[N];

	void dfs(int u) {
		v[high[u] % 10].push_back(u);
		for (auto v : G[u]) {
			if (v.first == par[u]) continue;
			high[v.first] = high[u] + 1, par[v.first] = u;
			edge[v.second] = v.first, dfs(v.first);
		}
	}

	void dfs2(int u) {
		for (auto v : G[u]) {
			if (v.first == par[u]) continue;
			dis[v.first] = dis[u] + 1, dfs2(v.first);
		}
	}

	void init(int _n, int A[], int B[]) {
		n = _n;
		for (int i = 0; i < (n - 1); ++i) {
			G[A[i]].push_back(ii(B[i], i)), G[B[i]].push_back(ii(A[i], i));
		}
		dfs(0);
	}

	void solve(int C[]) {
		for (int i = 0; i < (n - 1); ++i) dis[edge[i]] = C[i], Save(edge[i], C[i]);
		dfs2(0);
		int mn = 0;
		for (int i = 1; i < 10; ++i) {
			if (v[mn].size() > v[i].size()) mn = i;
		}
		int id = n;
		for (auto i : v[mn]) {
			start[i] = id;
			for (int j = 0; j < 9; ++j) {
				Save(id++, dis[i] >> j & 1);
			}
		} 
	}
}

void InitAnya(int N , int A[] , int B[]) { A::init(N, A, B); }

void Anya(int C[]) { A::solve(C); }

#include "Borislib.h"
#include <bits/stdc++.h>

using namespace std;

namespace B {
	const int N = 505;

	int n;
	int par[N];
	int high[N];
	int start[N];
	vector<int> G[N];
	vector<int> v[N];

	void dfs(int u) {
		v[high[u] % 10].push_back(u);
		for (auto v : G[u]) {
			if (v == par[u]) continue;
			high[v] = high[u] + 1, par[v] = u, dfs(v);
		}
	}

	void init(int _n, int A[], int B[]) {
		n = _n;
		for (int i = 0; i < (n - 1); ++i) {
			G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]);
		}
		dfs(0);
		int mn = 0;
		for (int i = 1; i < 10; ++i) {
			if (v[mn].size() > v[i].size()) mn = i;
		}
		int id = n;
		for (auto i : v[mn]) {
			start[i] = id, id += 9;
		} 
	}

	int query(int x) {
		int res = 0;
		while (!start[x] && x) {
			res += Ask(x), x = par[x];
		}
		if (start[x]) {
			for (int i = 0; i < 9; ++i) res += Ask(start[x] + i) << i;
		}
		return res;
	}
}

void InitBoris(int N , int A[] , int B[]) { B::init(N, A, B); }

int Boris(int x) { return B::query(x); }

Subtask #1
0 / 15.0

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

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4212 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 4212 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 4212 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -