Submission #67138

#	Time	Username	Problem	Language	Result	Execution time	Memory
67138		reality	Snowy Roads (JOI16_snowy)	C++17	100 / 100	30 ms	38200 KiB

Anya

#include "Anyalib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

static const int N = 1024;

static int n;

static vector < pii > g[N];

static int P[N][N];

static int fr[N];

static int coef[N];

static int lf[N];

static int rg[N];

static vii e;

static int Time = 0;

static const int B = 10;

static void dfs(int node = 0,int index = 0) {
	++Time;
	lf[index] = Time;
	fr[node] = Time;
	coef[Time] = 1;
	for (auto it : g[node])
		if (it.se != index)
			dfs(it.fi,it.se);
	++Time;
	rg[index] = Time;
	coef[Time] = -1;
}

void InitAnya(int NN, int A[] , int B[]) {
	n = NN;
	for (int i = 0;i < n - 1;++i) {
		g[A[i]].pb(mp(B[i],i + 1));
		g[B[i]].pb(mp(A[i],i + 1));
		P[A[i]][B[i]] = P[B[i]][A[i]] = i + 1;
	}
	dfs();
}

static int sum[N];

void Anya(int C[]) {
	for (int i = 0;i <= n + n;++i)
		sum[i] = 0;
	for (int i = 1;i < n;++i) {
		sum[lf[i]] = C[i - 1];
		sum[rg[i]] = -C[i - 1];
	}
	for (int i = 1;i <= n + n;++i)
		sum[i] += sum[i - 1];
	for (int i = 0;i < n - 1;++i)
		Save(i,C[i]);
	for (int i = 0;i * 2 * B < n + n;++i) {
		int ed = min(n + n,(i + 1) * 2 * B);
		for (int t = 0;t < B;++t)
			Save(n - 1 + t + i * B,(sum[ed] >> t) & 1);
	}
}

Boris

#include "Borislib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

static const int N = 1024;

static int n;

static vector < pii > g[N];

static int P[N][N];

static int fr[N];

static int coef[N];

static int lf[N];

static int rg[N];

static int ac[N];

static vii e;

static int Time = 0;

static const int B = 10;

static void dfs(int node = 0,int index = 0) {
	++Time;
	lf[index] = Time;
	ac[Time] = index - 1;
	fr[node] = Time;
	coef[Time] = 1;
	for (auto it : g[node])
		if (it.se != index)
			dfs(it.fi,it.se);
	++Time;
	ac[Time] = index - 1;
	rg[index] = Time;
	coef[Time] = -1;
}

void InitBoris(int NN , int A[] , int B[]) {
  	n = NN;
	for (int i = 0;i < n - 1;++i) {
		g[A[i]].pb(mp(B[i],i + 1));
		g[B[i]].pb(mp(A[i],i + 1));
		P[A[i]][B[i]] = P[B[i]][A[i]] = i + 1;
	}
	dfs();
}

int Boris(int node) {
	int need = fr[node];
	int pos = -1,beg;
	for (int i = 0;i * 2 * B < n + n;++i) {
		int ed = min(n + n,(i + 1) * 2 * B);
		if (abs(need - ed) <= B) {
			pos = ed;
			beg = i * B + n - 1;
			break;
		}
	}
	assert(abs(pos - need) <= B);
	int ans = 0;
	if (pos >= 0)
	for (int i = 0;i < B;++i)
		assert(0 <= beg + i && beg + i < 1000),ans += Ask(beg + i) * (1 << i);
	while (pos < need) {
		++pos;
		if (ac[pos] >= 0)
			ans += Ask(ac[pos]) * coef[pos];
	}
	while (pos > need) {
		if (ac[pos] >= 0)
			ans -= Ask(ac[pos]) * coef[pos];
		--pos;
	}
	return ans;
}

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