Submission #257507

#	Time	Username	Problem	Language	Result	Execution time	Memory
257507		songc	Snowy Roads (JOI16_snowy)	C++14	100 / 100	55 ms	4400 KiB

Anya

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

static int N, D[550], S[550], P[550];
static int A[550], B[550], C[550][550];
static vector<int> adj[550], V;

static void dfs(int u, int p, int c){
	D[u] = 1, P[u] = c;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u, c+C[u][v]);
		D[u] += D[v];
	}
	if (D[u] >= 11 || u==0) D[u]=0, V.push_back(u);
}

void InitAnya(int n, int a[], int b[]) {
	N=n;
	for (int i=0; i<N; i++) adj[i].clear();
	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]);
	}
}

void Anya(int c[]) {
	memset(C, 0, sizeof C);
	for (int i=0; i<N-1; i++) C[A[i]][B[i]] = C[B[i]][A[i]] = c[i], Save(i, c[i]);
	V.clear();
	dfs(0, -1, 0);
	for (int i=0; i<V.size(); i++) for (int j=0; j<9; j++) Save(N-1+i*9+j, !!(P[V[i]]&(1<<j)));
}

Boris

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

static int N, D[550], S[550], P[550], X[550], num;
static int A[550], B[550], C[550][550];
static vector<int> adj[550];

static void dfs(int u, int p){
	D[u] = 1, P[u] = p;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		D[u] += D[v];
	}
	if (D[u] >= 11 || u==0) D[u]=0, X[u]=++num;
}

void InitBoris(int n, int a[], int b[]) {
	N=n, num=0;
	memset(S, 0, sizeof S);
	memset(X, 0, sizeof X);
	for (int i=0; i<N; i++) adj[i].clear();
	for (int i=0; i<N-1; i++){
		A[i] = a[i], B[i] = b[i];
		C[A[i]][B[i]] = C[B[i]][A[i]] = i;
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0, -1);
}

int Boris(int u){
	int ans=0;
	while (!X[u]){
		ans += Ask(C[u][P[u]]);
		u = P[u];
	}
	for (int i=0; i<9; i++) if (Ask(N-1+(X[u]-1)*9+i)) ans += (1<<i);
	return ans;
}

Compilation message (stderr)

Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<V.size(); i++) for (int j=0; j<9; j++) Save(N-1+i*9+j, !!(P[V[i]]&(1<<j)));
                ~^~~~~~~~~
Anya.cpp: At global scope:
Anya.cpp:5:23: warning: 'S' defined but not used [-Wunused-variable]
 static int N, D[550], S[550], P[550];
                       ^

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