Submission #925673

#	Time	Username	Problem	Language	Result	Execution time	Memory
925673		daoquanglinh2007	Snowy Roads (JOI16_snowy)	C++17	100 / 100	23 ms	2224 KiB

Anya

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

#define isz(a) (int)(a).size()

const int NM = 500, D = 10;

int N, A[NM+5], B[NM+5];
bool snow[NM+5];
vector <int> adj[NM+5], arr;
int parent[NM+5], dep[NM+5], f[NM+5], g[NM+5], dp[NM+5];

void dfs(int u, int p){
	parent[u] = p;
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	f[u] = g[u] = dp[u] = 0;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		dp[u] += dp[v];
		if (f[v]+1 > f[u]){
			g[u] = f[u];
			f[u] = f[v]+1;
		}
		else if (f[v]+1 > g[u]){
			g[u] = f[v]+1;
		}
	}
	if (f[u]+g[u] > D){
		dp[u]++;
		arr.push_back(u);
		f[u] = g[u] = 0;
	}
}

void InitAnya(int _N, int _A[], int _B[]){
	N = _N;
	for (int i = 0; i < N-1; i++){
		A[i] = _A[i], B[i] = _B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	arr.clear();
	dfs(0, -1);
	for (int i = 0; i < N-1; i++)
		if (dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
}

void Anya(int C[]){
	memset(snow, 0, sizeof(snow));
	for (int i = 0; i < N-1; i++)
		if (C[i]){
			snow[B[i]] = 1;
			Save(B[i], 1);
		}
	for (int i = 0; i < isz(arr); i++){
		int v = arr[i], cnt = 0;
		for (int u = v; u > 0; u = parent[u])
			if (snow[u]) cnt++;
		for (int j = 0; j <= 8; j++)
			Save(N+9*i+j, (cnt>>j)&1);
	}
}

Boris

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

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 500, LOG = 10, D = 10;

int N, A[NM+5], B[NM+5];
vector <int> adj[NM+5], arr;
int parent[NM+5], dep[NM+5], f[NM+5], g[NM+5], dp[NM+5];
int ecnt = 0, ap[NM+5];
pii sp[LOG+5][2*NM+5];

void dfs(int u, int p){
	parent[u] = p;
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	ap[u] = ++ecnt;
	sp[0][ap[u]] = mp(dep[u], u);
	f[u] = g[u] = dp[u] = 0;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		sp[0][++ecnt] = mp(dep[u], u);
		dp[u] += dp[v];
		if (f[v]+1 > f[u]){
			g[u] = f[u];
			f[u] = f[v]+1;
		}
		else if (f[v]+1 > g[u]){
			g[u] = f[v]+1;
		}
	}
	if (f[u]+g[u] > D || (p == -1 && dp[u] == 0)){
		dp[u]++;
		arr.push_back(u);
		f[u] = g[u] = 0;
	}
}

void build_sparse(){
	for (int i = 1; i <= LOG; i++)
		for (int j = 1; j+(1<<i)-1 <= ecnt; j++)
			sp[i][j] = min(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
}

void InitBoris(int _N, int _A[], int _B[]){
	N = _N;
	for (int i = 0; i < N-1; i++){
		A[i] = _A[i], B[i] = _B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	arr.clear();
	dfs(0, -1);
	for (int i = 0; i < N-1; i++)
		if (dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
	build_sparse();
}

int lca(int u, int v){
	int l = ap[u], r = ap[v];
	if (l > r) swap(l, r);
	int i = __lg(r-l+1);
	return min(sp[i][l], sp[i][r-(1<<i)+1]).se;
}

int dist(int u, int v){
	return dep[u]+dep[v]-2*dep[lca(u, v)];
}

int Boris(int v){
	int best = 0;
	for (int i = 1; i < isz(arr); i++){
		if (dist(v, arr[i]) < dist(v, arr[best])) best = i;
	}
	int ans = 0;
	for (int i = 0; i <= 8; i++)
		if (Ask(N+9*best+i)) ans += (1<<i);
		
	int u = arr[best], l = lca(u, v);
	while (u != l){
		if (Ask(u)) ans--;
		u = parent[u];
	}
	while (v != l){
		if (Ask(v)) ans++;
		v = parent[v];
	}
	return ans;
}

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