답안 #26229 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26229	2017-06-28T12:30:05 Z	youngyojun	Snowy Roads (JOI16_snowy)	C++11	55 / 100	19 ms	4196 KB

Anya
Boris

#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 (505)
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]);
}

#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 (505)
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.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4196 KB	Output is correct
2	Correct	0 ms	4196 KB	Output is correct
3	Correct	0 ms	4196 KB	Output is correct
4	Correct	0 ms	4196 KB	Output is correct
5	Correct	6 ms	4196 KB	Output is correct
6	Correct	3 ms	4196 KB	Output is correct
7	Correct	3 ms	4196 KB	Output is correct
8	Correct	0 ms	4196 KB	Output is correct
9	Correct	3 ms	4196 KB	Output is correct
10	Correct	6 ms	4196 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4196 KB	Output is correct
2	Correct	6 ms	4196 KB	Output is correct
3	Correct	9 ms	4196 KB	Output is correct
4	Correct	9 ms	4196 KB	Output is correct
5	Correct	6 ms	4196 KB	Output is correct
6	Correct	9 ms	4196 KB	Output is correct
7	Correct	3 ms	4196 KB	Output is correct
8	Correct	9 ms	4196 KB	Output is correct
9	Correct	6 ms	4196 KB	Output is correct
10	Correct	3 ms	4196 KB	Output is correct

Subtask #3
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	4196 KB	Output is correct
2	Correct	12 ms	4196 KB	Output is correct
3	Correct	16 ms	4196 KB	Output is correct
4	Correct	12 ms	4196 KB	Output is correct
5	Correct	19 ms	4196 KB	Output is correct
6	Correct	9 ms	4196 KB	Output is correct
7	Correct	16 ms	4196 KB	Output is correct
8	Correct	13 ms	4196 KB	Output is correct
9	Correct	12 ms	4196 KB	Output is correct
10	Correct	12 ms	4196 KB	Output is correct
11	Correct	16 ms	4196 KB	Output is correct
12	Correct	12 ms	4196 KB	Output is correct
13	Correct	9 ms	4196 KB	Output is correct
14	Correct	12 ms	4196 KB	Output is correct
15	Correct	16 ms	4196 KB	Output is correct
16	Correct	15 ms	4196 KB	Output is correct
17	Correct	12 ms	4196 KB	Output is correct
18	Correct	9 ms	4196 KB	Output is correct
19	Correct	15 ms	4196 KB	Output is correct
20	Correct	15 ms	4196 KB	Output is correct

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	9 ms	4196 KB	Wrong Answer [4]
2	Halted	0 ms	0 KB	-

답안 #26229

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 5.0 / 5.0

Subtask #3 35.0 / 35.0

Subtask #4 0 / 45.0

Subtask #1
15.0 / 15.0

Subtask #2
5.0 / 5.0

Subtask #3
35.0 / 35.0

Subtask #4
0 / 45.0