Submission #32173

#	Time	Username	Problem	Language	Result	Execution time	Memory
32173		Diuven	Snowy Roads (JOI16_snowy)	C++11	55 / 100	19 ms	2484 KiB

Anya

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

namespace AS{
	struct edge{
		int to=-1, idx=-1;
		edge(int to, int idx): to(to), idx(idx){};
		edge(){};
	} P[500]; // 올라가는 간선
	vector<edge> G[500];
	vector<int> V;
	int N, S[500], now, dep[500], C[500], X;
	void idfs(int v, int p){
		dep[v]=now++;
		if(dep[v]%10==0)	V.push_back(v);
		for(edge e:G[v])
			if(e.to!=p){
				P[e.to]={v, e.idx};
				idfs(e.to, v);
			}
		now--;
	}
	void dfs(int v, int p, int d){
		S[v]=d;
		for(edge e:G[v])
			if(e.to!=p)
				dfs(e.to, v, d+C[e.idx]);
	}
}

using namespace AS;

void InitAnya(int _N, int A[], int B[]){
	N=_N;
	for(int i=0; i<=N-2; i++){
		G[A[i]].push_back({B[i], i});
		G[B[i]].push_back({A[i], i});
	}
	idfs(0,-1);
	X=(int)V.size()*9;
}

void Anya(int _C[]){
	fill(S, S+N, 0);
	for(int i=0; i<=N-2; i++)
		C[i]=_C[i];
	dfs(0, -1, 0);
	for(int i=0; i<(int)V.size(); i++)
		for(int k=0; k<9; k++)
			Save(9*i+k, !!(S[V[i]]&(1<<k)));
	for(int i=0; i<=N-2; i++)
		Save(X+i, C[i]);
}

Boris

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

namespace BS{
	struct edge{
		int to=-1, idx=-1;
		edge(int to, int idx): to(to), idx(idx){};
		edge(){};
	} P[500];
	vector<edge> G[500];
	int N, dep[500], now, X, bck, pos[500];
	void idfs(int v, int p){
		dep[v]=now++;
		if(dep[v]%10==0)	pos[v]=bck++;
		for(edge e:G[v])
			if(e.to!=p){
				P[e.to]={v, e.idx};
				idfs(e.to, v);
			}
		now--;
	}
}

using namespace BS;

void InitBoris(int _N, int A[], int B[]){
	N=_N;
	for(int i=0; i<=N-2; i++){
		G[A[i]].push_back({B[i], i});
		G[B[i]].push_back({A[i], i});
	}
	idfs(0,-1);
	X=bck*9;
}
int Boris(int city){
	int ans=0;
	while(dep[city]%10!=0){
		ans+=Ask(X+P[city].idx);
		city=P[city].to;
	}
	for(int k=0; k<9; k++)
		ans+=(Ask(pos[city]*9+k)<<k);
	return ans;
}

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