Submission #1242006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242006		PenguinsAreCute	Snowy Roads (JOI16_snowy)	C++17	55 / 100	13 ms	584 KiB

Anya

#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;
namespace {int H[505], X[505], ord[505], A[505], B[505], N;}

void InitAnya(int N , int A[] , int B[]) {
	::N = N;
	memcpy(::A,A,sizeof(int) * (N-1));
	memcpy(::B,B,sizeof(int) * (N-1));
	int D[N];
	memset(D,0,sizeof(D));
	for(int i=0;i<N-1;i++) {
		D[A[i]]++;
		D[B[i]]++;
		X[A[i]]^=B[i];
		X[B[i]]^=A[i];
	}
	int cnt = 0;
	D[0] = -1;
	for(int i=0;i<N;i++)
		for(int j=i;D[j]==1;j=X[j]) {
			D[j]--;
			D[X[j]]--;
			X[X[j]] ^= j;
			ord[cnt++] = j;
		}
	while(cnt--)
		H[ord[cnt]] = H[X[ord[cnt]]] + 1;
	int resid[10];
	memset(resid,0,sizeof(resid));
	for(int i=0;i<10;i++)
		resid[H[i] % 10]++;
	int mn = min_element(resid,resid+10) - resid;
	for(int i=0;i<N;i++)
		H[i] = (H[i] % 10 == mn);
}

void Anya(int C[]) {
	int W[N], D[N];
	for(int i=0;i<N-1;i++) {
		Save((X[A[i]]==B[i]?A[i]:B[i]),C[i]);
		W[(X[A[i]]==B[i]?A[i]:B[i])] = C[i];
	}
	D[0] = 0;
	for(int i=N-1;i--;)
		D[ord[i]] = D[X[ord[i]]] + W[ord[i]];
	int cnt = N;
	for(int i=0;i<N;i++)
		if(H[i]) {
			for(int j=0;j<10;j++)
				Save(cnt++, !!(D[i] & (1 << j)));
		}
}

Boris

#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;
namespace {int H[505], X[505], ord[505], A[505], B[505], N;}

void InitBoris(int N , int A[] , int B[]) {
	::N = N;
	memcpy(::A,A,sizeof(int) * (N-1));
	memcpy(::B,B,sizeof(int) * (N-1));
	int D[N];
	memset(D,0,sizeof(D));
	for(int i=0;i<N-1;i++) {
		D[A[i]]++;
		D[B[i]]++;
		X[A[i]]^=B[i];
		X[B[i]]^=A[i];
	}
	int cnt = 0;
	D[0] = -1;
	for(int i=0;i<N;i++)
		for(int j=i;D[j]==1;j=X[j]) {
			D[j]--;
			D[X[j]]--;
			X[X[j]] ^= j;
			ord[cnt++] = j;
		}
	while(cnt--)
		H[ord[cnt]] = H[X[ord[cnt]]] + 1;
	int resid[10];
	memset(resid,0,sizeof(resid));
	for(int i=0;i<10;i++)
		resid[H[i] % 10]++;
	int mn = min_element(resid,resid+10) - resid;
	for(int i=0;i<N;i++)
		H[i] = (H[i] % 10 == mn);
}

int Boris(int city) {
	int cur = city;
	while(cur && !H[cur])
		cur = X[cur];
	int weight = 0;
	if(cur) {
		int pos = accumulate(H, H+cur, 0) * 10 + N;
		for(int i=pos;i<pos+9;i++)
			weight |= (Ask(i) << (i - pos));
	}
	while(city != cur)
		weight += Ask(exchange(city, X[city]));
	return weight;
}

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