Submission #158255

#	Time	Username	Problem	Language	Result	Execution time	Memory
158255		TadijaSebez	Snowy Roads (JOI16_snowy)	C++11	100 / 100	27 ms	2044 KiB

Anya

#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
namespace _Anya
{
	const int M=505;
	vector<pair<int,int>> E[M];
	int nod[M],dep[M],n;
	int mark[M],csz;
	vector<int> marked;
	int DFS(int u, int p)
	{
		int mx=0;
		for(auto e:E[u]) if(e.first!=p)
		{
			nod[e.second]=e.first;
			int now=DFS(e.first,u);
			mx=max(mx,now);
		}
		mx++;
		if(mx>=11)
		{
			mx=0;
			mark[u]=++csz;
			marked.pb(u);
		}
		return mx;
	}
	void InitAnya(int N, int A[], int B[])
	{
		n=N;
		for(int i=0;i<n;i++) E[i].clear();
		for(int i=0;i<n;i++) mark[i]=0;
		csz=0;marked.clear();
		for(int i=0;i<n-1;i++)
		{
			E[A[i]].pb({B[i],i});
			E[B[i]].pb({A[i],i});
		}
		DFS(0,-1);
	}
	void Pull(int u, int p)
	{
		for(auto e:E[u]) if(e.first!=p)
		{
			dep[e.first]+=dep[u];
			Pull(e.first,u);
		}
	}
	void Anya(int C[])
	{
		for(int i=0;i<n;i++) dep[i]=0;
		for(int i=0;i<n-1;i++) dep[nod[i]]=C[i];
		for(int i=0;i<n;i++) Save(i,dep[i]);
		Pull(0,-1);
		for(int i:marked)
		{
			for(int j=0;j<9;j++) Save(500+(mark[i]-1)*9+j,(dep[i]>>j)&1);
		}
	}
}
void InitAnya(int N, int A[], int B[])
{
	_Anya::InitAnya(N,A,B);
}
void Anya(int C[])
{
	_Anya::Anya(C);
}

Boris

#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
namespace _Boris
{
	const int M=505;
	vector<pair<int,int>> E[M];
	int nod[M],dep[M],n,par[M];
	int mark[M],csz;
	vector<int> marked;
	int DFS(int u, int p)
	{
		int mx=0;
		for(auto e:E[u]) if(e.first!=p)
		{
			nod[e.second]=e.first;
			par[e.first]=u;
			int now=DFS(e.first,u);
			mx=max(mx,now);
		}
		mx++;
		if(mx>=11)
		{
			mx=0;
			mark[u]=++csz;
			marked.pb(u);
		}
		return mx;
	}
	void InitBoris(int N, int A[], int B[])
	{
		n=N;
		for(int i=0;i<n;i++) E[i].clear();
		for(int i=0;i<n;i++) mark[i]=0;
		csz=0;marked.clear();
		for(int i=0;i<n-1;i++)
		{
			E[A[i]].pb({B[i],i});
			E[B[i]].pb({A[i],i});
		}
		DFS(0,-1);
	}
	int Boris(int city)
	{
		int ans=0;
		while(city!=0 && mark[city]==0)
		{
			ans+=Ask(city);
			city=par[city];
		}
		if(mark[city])
		{
			for(int i=0;i<9;i++) ans+=Ask(500+(mark[city]-1)*9+i)<<i;
		}
		return ans;
	}
}
void InitBoris(int N, int A[], int B[])
{
	_Boris::InitBoris(N,A,B);
}
int Boris(int city)
{
	return _Boris::Boris(city);
}

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