Submission #73122

#	Time	Username	Problem	Language	Result	Execution time	Memory
73122		IvanC	Snowy Roads (JOI16_snowy)	C++17	100 / 100	31 ms	26228 KiB

Anya

#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1010;

static vector<int> grafo[MAXN],lista; 
static int N,distancia[MAXN],pai[MAXN],custo[MAXN],lastPtr,resposta[MAXN];
static int e1[MAXN],e2[MAXN],ini[MAXN],fim[MAXN],especial[MAXN],marcado[MAXN],jafoi[MAXN];

static void doSpecial(int v){

	if(marcado[v]) return;

	for(int passo = 1;passo <= 11;passo++){
		if(especial[v]) return;
		marcado[v] = 1;
		int i = pai[v];
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		v = u;
	}

	marcado[v] = 1;
	especial[v] = 1;

}

static void bfs(){

	queue<int> fila;
	fila.push(0);
	jafoi[0] = 1;
	marcado[0] = 1;
	especial[0] = 1;

	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int i : grafo[v]){
			int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
			if(!jafoi[u]){
				jafoi[u] = 1;
				pai[u] = i;
				fila.push(u);
			}
		}
	}

	for(vector<int>::reverse_iterator it = lista.rbegin();it != lista.rend();it++){
		doSpecial(*it);
	}

}


void InitAnya(int n , int A[] , int B[]) {
 
 	N = n;
	
	for(int i = 0;i<N-1;i++){
		grafo[A[i]].push_back(i);
		grafo[B[i]].push_back(i);
		e1[i] = A[i];
		e2[i] = B[i];
	}

	lastPtr = N-1;

	bfs();
	especial[0] = 0;

	for(int i = 0;i<N;i++){
		if(!especial[i]) continue;
		ini[i] = lastPtr;
		fim[i] = lastPtr + 8;
		lastPtr += 9;
	}

}
 
void Anya(int C[]){
	 
	 memset(resposta,0,sizeof(resposta));

	 for(int i = 0;i<N-1;i++){
	 	custo[i] = C[i];
	 	resposta[i] = C[i];
	 }

	for(int v : lista){
		if(v == 0){
			distancia[v] = 0;
			continue;
		}
		int i = pai[v];
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		distancia[v] = distancia[u] + custo[i];
	}

	for(int v : lista){
		if(v == 0) continue;
		if(!especial[v]) continue;
		for(int i = ini[v],j = 0;i <= fim[v];i++,j++){
			if(distancia[v] & (1 << j)) resposta[i] = 1;
			else resposta[i] = 0;
		}
	}

	for(int i = 0 ; i < 1000 ; i++){
		Save(i , resposta[i]);
	}
 
}

Boris

#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1010;

static vector<int> grafo[MAXN],lista; 
static int N,pai[MAXN],lastPtr;
static int e1[MAXN],e2[MAXN],ini[MAXN],fim[MAXN],especial[MAXN],marcado[MAXN],jafoi[MAXN];

static void doSpecial(int v){

	if(marcado[v]) return;

	for(int passo = 1;passo <= 11;passo++){
		if(especial[v]) return;
		marcado[v] = 1;
		int i = pai[v];
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		v = u;
	}

	marcado[v] = 1;
	especial[v] = 1;

}

static void bfs(){

	queue<int> fila;
	fila.push(0);
	jafoi[0] = 1;
	marcado[0] = 1;
	especial[0] = 1;

	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int i : grafo[v]){
			int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
			if(!jafoi[u]){
				jafoi[u] = 1;
				pai[u] = i;
				fila.push(u);
			}
		}
	}

	for(vector<int>::reverse_iterator it = lista.rbegin();it != lista.rend();it++){
		doSpecial(*it);
	}

}


void InitBoris(int n , int A[] , int B[]) {
 
 	N = n;
	
	for(int i = 0;i<N-1;i++){
		grafo[A[i]].push_back(i);
		grafo[B[i]].push_back(i);
		e1[i] = A[i];
		e2[i] = B[i];
	}

	lastPtr = N-1;

	bfs();
	especial[0] = 0;

	for(int i = 0;i<N;i++){
		if(!especial[i]) continue;
		ini[i] = lastPtr;
		fim[i] = lastPtr + 8;
		lastPtr += 9;
	}

}

static int doQuery(int v){
	if(v == 0) return 0;
	if(especial[v]){
		int numero = 0;
		for(int i = ini[v],j = 0;i <= fim[v];i++,j++){
			if(Ask(i)) numero += (1 << j);
		}
		return numero;
	}
	else{
		int i = pai[v];
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		return doQuery(u) + Ask(i);
	}
}
 
int Boris(int city) {
	return doQuery(city);
}

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