Submission #26198

#	Time	Username	Problem	Language	Result	Execution time	Memory
26198		kdh9949	Snowy Roads (JOI16_snowy)	C++14	100 / 100	22 ms	2508 KiB

Anya

#include "Anyalib.h"
#include <vector>
#include <algorithm>
using namespace std;

struct E{ int x, i; };

static int n, c[500], s[500];
static vector<int> sv;
static vector<E> e[500], t[500];

static int g(int x, int p){
	int ret = 0;
	for(auto &i : e[x]){
		if(i.x == p) continue;
		t[x].push_back(i);
		ret = max(ret, g(i.x, x) + 1);
	}
	if(ret >= 10){
		sv.push_back(x);
		ret = 0;
	}
	return ret;
}

static void f(int x, int d){
	s[x] = d;
	for(auto &i : t[x]){
		f(i.x, d + c[i.i]);
	}
}

void InitAnya(int N, int A[], int B[]){ 
	n = N;
	for(int i = 0; i < n - 1; i++){
		e[A[i]].push_back({B[i], i});
		e[B[i]].push_back({A[i], i});
	}
	g(0, 0);
}

void Anya(int C[]) {
	for(int i = 0; i < n - 1; i++){
		c[i] = C[i];
		Save(i, c[i]);
	}
	f(0, 0);
	for(int i = 0; i < sv.size(); i++){
		for(int j = 0; j < 10; j++){
			Save(n + 10 * i + j, !!(s[sv[i]] & (1 << j)));
		}
	}
}

Boris

#include "Borislib.h"
#include <vector>
#include <algorithm>
using namespace std;

struct F{ int x, i; };

static int n, s[500], sn[500];
static F par[500];
static vector<int> sv;
static vector<F> e[500], t[500];

static int g(int x, int p){
	int ret = 0;
	for(auto &i : e[x]){
		if(i.x == p) continue;
		par[i.x] = {x, i.i};
		t[x].push_back(i);
		ret = max(ret, g(i.x, x) + 1);
	}
	if(ret >= 10){
		sn[x] = int(sv.size() + 1);
		sv.push_back(x);
		ret = 0;
	}
	return ret;
}

static int f(int x){
	if(!x) return 0;
	if(sn[x]){
		int ret = 0;
		for(int i = 0; i < 10; i++) ret += Ask(n + (sn[x] - 1) * 10 + i) << i;
		return ret;
	}
	return f(par[x].x) + Ask(par[x].i);
}

void InitBoris(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n - 1; i++){
		e[A[i]].push_back({B[i], i});
		e[B[i]].push_back({A[i], i});
	}
	g(0, 0);
}

int Boris(int x){
	return f(x);
}

Compilation message (stderr)

Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < sv.size(); i++){
                   ^

Boris.cpp:8:15: warning: 's' defined but not used [-Wunused-variable]
 static int n, s[500], sn[500];
               ^

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45