Submission #39810

#	Time	Username	Problem	Language	Result	Execution time	Memory
39810		aome	Snowy Roads (JOI16_snowy)	C++14	100 / 100	24 ms	4212 KiB

Anya

#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], 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); }

Boris

#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: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45