oj.uz

Submission #26229

# Submission time Handle Problem Language Result Execution time Memory
26229 2017-06-28T12:30:05 Z youngyojun None (JOI16_snowy) C++11
55 / 100
 19 ms 4196 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4196 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -