Submission #32174

#	Time	Username	Problem	Language	Result	Execution time	Memory
32174		Diuven	Snowy Roads (JOI16_snowy)	C++11	100 / 100	26 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, rem, cnt[10];
	void idfs(int v, int p){
		dep[v]=now++;
		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[]){
	V.clear();
	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);
	for(int i=0; i<N; i++)
		cnt[dep[i]%10]++;
	int mn=N;
	for(int i=0; i<=9; i++)
		if(mn>cnt[i])
			mn=cnt[i], rem=i;
	for(int i=0; i<N; i++)
		if(dep[i]%10==rem)
			V.push_back(i);
	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], cnt[10], rem;
	void idfs(int v, int p){
		dep[v]=now++;
		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[]){
	bck=0;
	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);
	for(int i=0; i<N; i++)
		cnt[dep[i]%10]++;
	int mn=N;
	for(int i=0; i<10; i++)
		if(mn>cnt[i])
			mn=cnt[i], rem=i;
	for(int i=0; i<N; i++)
		if(dep[i]%10==rem)
			pos[i]=bck++;
	X=bck*9;
}
int Boris(int city){
	int ans=0;
	while(city>0&&dep[city]%10!=rem){
		ans+=Ask(X+P[city].idx);
		city=P[city].to;
	}
	if(dep[city]%10!=rem)	return ans;
	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: 45 / 45