Submission #26230

#	Time	Username	Problem	Language	Result	Execution time	Memory
26230		youngyojun	Snowy Roads (JOI16_snowy)	C++11	100 / 100	25 ms	4776 KiB

Anya

#include "Anyalib.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <tuple>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (6974)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
static void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }

static vector<int> G[MAXN];
static vector<pii> EV;
static int A[MAXN], B[MAXN], P[MAXN], dep[MAXN];
static int C[MAXN], D[MAXN], S[MAXN];
static int N;

static int wl;
static void write(int num) {
	for(int i = 0; i < 10; i++) Save(wl++, (num & (1<<i)) ? 1 : 0);
}
static void dfs(int idx, int depth) {
	dep[idx] = depth; EV.pb({idx, 1});
	for(int v : G[idx]) if(!dep[v]) dfs(v, depth+1);
	EV.pb({idx, -1});
}
void InitAnya(int _N , int _A[] , int _B[]) {
	N = _N; for(int i = 0; i+1 < N; i++) { A[i+1] = _A[i]; B[i+1] = _B[i]; }
	for(int i = 1; i < N; i++) if(A[i] > B[i]) swap(A[i], B[i]);
	for(int i = 1; i < N; i++) P[i] = i;
	sort(P+1, P+N, [&](int a, int b) { return (pii){A[a], B[a]} < (pii){A[b], B[b]}; });
	for(int i = 1; i < N; i++) fg(G, A[P[i]], B[P[i]]);
	dfs(0, 1); for(int i = 0; i < 2*N; i++) if(1 == EV[i].second) C[EV[i].first] = i;
	for(int i = 1; i < N; i++) if(dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
}
void Anya(int _D[]) {
	for(int i = 0; i+1 < N; i++) D[B[i+1]] = _D[i];
	for(int i = 1; i < N; i++) Save(i-1, D[i]); wl = N-1;
	for(int i = 1; i < 2*N; i++) S[i] = S[i-1] + D[EV[i].first] * EV[i].second;
	for(int i = 20; i < 2*N; i += 20) write(S[i]);
	write(S[2*N-1]);
}

Boris

#include "Borislib.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <tuple>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (6974)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
static void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
static int myabs(int n) { return n < 0 ? -n : n; }

static vector<int> G[MAXN];
static vector<pii> EV;
static int A[MAXN], B[MAXN], P[MAXN], dep[MAXN];
static int C[MAXN];
static int N;

static int read(int pos) {
	int ret = 0; for(int i = 0; i < 10; i++) ret += Ask(pos+i) ? (1<<i) : 0;
	return ret;
}
static void dfs(int idx, int depth) {
	dep[idx] = depth; EV.pb({idx, 1});
	for(int v : G[idx]) if(!dep[v]) dfs(v, depth+1);
	EV.pb({idx, -1});
}
void InitBoris(int _N , int _A[] , int _B[]) {
	N = _N; for(int i = 0; i+1 < N; i++) { A[i+1] = _A[i]; B[i+1] = _B[i]; }
	for(int i = 1; i < N; i++) if(A[i] > B[i]) swap(A[i], B[i]);
	for(int i = 1; i < N; i++) P[i] = i;
	sort(P+1, P+N, [&](int a, int b) { return (pii){A[a], B[a]} < (pii){A[b], B[b]}; });
	for(int i = 1; i < N; i++) fg(G, A[P[i]], B[P[i]]);
	dfs(0, 1); for(int i = 0; i < 2*N; i++) if(1 == EV[i].second) C[EV[i].first] = i;
	for(int i = 1; i < N; i++) if(dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
}
int Boris(int city) {
	int hubo = 0, huboi = 0, hd = C[city];
	for(int i = 20; i < 2*N; i += 20) {
		int ret = myabs(C[city] - i);
		if(hd > ret) { hd = ret; hubo = i / 20; huboi = i; }
	}
	{
		int ret = myabs(C[city] - (2*N-1));
		if(hd > ret) { hd = ret; hubo = (2*N-1) / 20 + 1; huboi = 2*N-1; }
	}
	int ret = hubo ? read(N-1 + (hubo-1) * 10) : 0;
	if(huboi <= C[city]) {
		for(int i = huboi+1; i <= C[city]; i++)
			ret += (EV[i].first ? Ask(EV[i].first-1) : 0) * EV[i].second;
	} else {
		for(int i = huboi; C[city] < i; i--)
			ret -= (EV[i].first ? Ask(EV[i].first-1) : 0) * EV[i].second;
	}
	return ret;
}

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