Submission #100970

#	Time	Username	Problem	Language	Result	Execution time	Memory
100970		autumn_eel	Snowy Roads (JOI16_snowy)	C++14	100 / 100	66 ms	2032 KiB

Anya

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;

#include "Anyalib.h"

static vector<int>E[600];
static int dep[600];
static int a[600],b[600];

static map<int,int>mp,edge;
int n;

static void dfs(int v,int p,int d){
	dep[v]=d;
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v,d+1);
	}
}
static int mod;
void InitAnya(int N , int A[] , int B[]) {
	n=N;
	rep(i,n-1){
		a[i]=A[i];b[i]=B[i];
		E[a[i]].push_back(b[i]);
		E[b[i]].push_back(a[i]);
	}
	dfs(0,-1,0);
	int MP[12]{};
	for(int i=1;i<n;i++){
		MP[dep[i]%12]++;
	}
	mod=min_element(MP,MP+12)-MP;
	int cnt=0;
	for(int i=1;i<n;i++){
		if(dep[i]%12==mod){
			mp[i]=cnt;
			cnt+=9;
		}
	}
	rep(i,n-1){
		if(dep[a[i]]>dep[b[i]])swap(a[i],b[i]);
		edge[b[i]]=cnt++;
	}
	assert(cnt<=1000);
}

static int dist[600];
static int c[600];

static void dfs2(int v,int p,int d){
	dist[v]=d;
	for(int u:E[v]){
		if(u==p)continue;
		dfs2(u,v,d+c[u]);
	}
}

void Anya(int C[]) {
	rep(i,n-1){
		if(C[i])c[b[i]]=1;
		else c[b[i]]=0;
	}
	dfs2(0,-1,0);
	for(int i=1;i<n;i++){
		if(dep[i]%12==mod){
			int st=mp[i];
			rep(j,9){
				Save(st+j,dist[i]>>j&1);
			}
		}
		Save(edge[i],c[i]);
	}
}

Boris

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

#include "Borislib.h"


static vector<int>E[600];
static int dep[600];
static int a[600],b[600];

static map<int,int>mp,edge;
static int par[600];
static int n;

static void dfs(int v,int p,int d){
	dep[v]=d;
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v,d+1);
	}
}
static int mod;
void InitBoris(int N , int A[] , int B[]) {
	n=N;
	rep(i,N-1){
		a[i]=A[i];b[i]=B[i];
		E[a[i]].push_back(b[i]);
		E[b[i]].push_back(a[i]);
	}
	dfs(0,-1,0);
	int MP[12]{};
	for(int i=1;i<n;i++){
		MP[dep[i]%12]++;
	}
	mod=min_element(MP,MP+12)-MP;
	int cnt=0;
	for(int i=1;i<N;i++){
		if(dep[i]%12==mod){
			mp[i]=cnt;
			cnt+=9;
		}
	}
	rep(i,N-1){
		if(dep[a[i]]>dep[b[i]])swap(a[i],b[i]);
		edge[b[i]]=cnt++;
		par[b[i]]=a[i];
	}
}

int Boris(int city) {
	int cnt=0;
	while(1){
		if(city==0)break;
		if(dep[city]%12==mod){
			int st=mp[city];
			rep(i,9){
				cnt+=(Ask(st+i)<<i);
			}
			break;
		}
		cnt+=Ask(edge[city]);
		city=par[city];
	}
	return cnt;
}

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