Submission #26112

#	Time	Username	Problem	Language	Result	Execution time	Memory
26112		khsoo01	Snowy Roads (JOI16_snowy)	C++11	100 / 100	19 ms	4184 KiB

Anya

#include "Anyalib.h"
#include<bits/stdc++.h>
using namespace std;

static int n, sum[1005], par[505], idx[505], val[505];

static vector<int> adj[505], arr;

static void calc (int C, int P) {
	par[C] = P;
	arr.push_back(C);
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
	arr.push_back(-C);
}

static void write (int S, int L, int V) {
	for(int i=0;i<L;i++) {
		Save(S+i, V%2);
		V /= 2;
	}
}

void InitAnya(int N, int A[] , int B[]) {
	n = N;
	for(int i=0;i<N-1;i++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	arr.push_back(0);
	calc(0, 0);
	for(int i=0;i<N-1;i++) {
		idx[i] = (par[A[i]] == B[i] ? A[i] : B[i]);
	}
}

void Anya(int C[]) {
	for(int i=0;i<n-1;i++) val[idx[i]] = C[i];
	for(int i=1;i<=2*n;i++) {
		sum[i] = sum[i-1] + (arr[i] < 0 ? -val[-arr[i]] : val[arr[i]]);
	}
	for(int i=0;20*i+1<=2*n;i++) write(10*i, 10, sum[20*(i+1)]);
	for(int i=0;i<n;i++) Save(500+i, val[i]);
}

Boris

#include "Borislib.h"
#include<bits/stdc++.h>
using namespace std;

static int n, inv[505];

static vector<int> adj[505], arr;

static void calc (int C, int P) {
	inv[C] = arr.size();
	arr.push_back(C);
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
	arr.push_back(-C);
}

static int read (int S, int L) {
	int R = 0;
	for(int i=0;i<L;i++) {
		R += (1<<i) * Ask(S+i);
	}
	return R;
}

static int getval (int P) {
	if(arr[P] < 0) return -Ask(500-arr[P]);
	else return Ask(500+arr[P]);
}

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

int Boris (int C) {
	int V = 0, I = inv[C];
	if(I % 20 <= 10) {
		I -= I%20;
		V = (I ? read(I/2-10, 10) : 0);
		for(int i=I+1;i<=inv[C];i++) {
			V += getval(i);
		}
	}
	else {
		I -= I%20 - 20;
		V = (I ? read(I/2-10, 10) : 0);
		for(int i=I;i>inv[C];i--) {
			V -= getval(i);
		}
	}
	return V;
}

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