oj.uz

Submission #67138

# Submission time Handle Problem Language Result Execution time Memory
67138 2018-08-13T11:30:35 Z reality None (JOI16_snowy) C++17
100 / 100
 30 ms 38200 KB 
#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);
	}
}

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 876 KB Output is correct
2 Correct 5 ms 1036 KB Output is correct
3 Correct 7 ms 1480 KB Output is correct
4 Correct 7 ms 1704 KB Output is correct
5 Correct 15 ms 2000 KB Output is correct
6 Correct 10 ms 2032 KB Output is correct
7 Correct 10 ms 2352 KB Output is correct
8 Correct 14 ms 2352 KB Output is correct
9 Correct 10 ms 2352 KB Output is correct
10 Correct 11 ms 2352 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2352 KB Output is correct
2 Correct 12 ms 2416 KB Output is correct
3 Correct 13 ms 2456 KB Output is correct
4 Correct 13 ms 2552 KB Output is correct
5 Correct 13 ms 2664 KB Output is correct
6 Correct 12 ms 2776 KB Output is correct
7 Correct 19 ms 2888 KB Output is correct
8 Correct 13 ms 3012 KB Output is correct
9 Correct 14 ms 3352 KB Output is correct
10 Correct 16 ms 3352 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3352 KB Output is correct
2 Correct 20 ms 3856 KB Output is correct
3 Correct 19 ms 4368 KB Output is correct
4 Correct 19 ms 4992 KB Output is correct
5 Correct 20 ms 5392 KB Output is correct
6 Correct 21 ms 5912 KB Output is correct
7 Correct 21 ms 6416 KB Output is correct
8 Correct 19 ms 6928 KB Output is correct
9 Correct 21 ms 7440 KB Output is correct
10 Correct 20 ms 8056 KB Output is correct
11 Correct 21 ms 8720 KB Output is correct
12 Correct 19 ms 9048 KB Output is correct
13 Correct 19 ms 9416 KB Output is correct
14 Correct 22 ms 10000 KB Output is correct
15 Correct 20 ms 10632 KB Output is correct
16 Correct 19 ms 11256 KB Output is correct
17 Correct 28 ms 11632 KB Output is correct
18 Correct 23 ms 12128 KB Output is correct
19 Correct 27 ms 12576 KB Output is correct
20 Correct 20 ms 13168 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13264 KB Output is correct
2 Correct 20 ms 13744 KB Output is correct
3 Correct 24 ms 14096 KB Output is correct
4 Correct 18 ms 14608 KB Output is correct
5 Correct 20 ms 15120 KB Output is correct
6 Correct 22 ms 15668 KB Output is correct
7 Correct 19 ms 16032 KB Output is correct
8 Correct 20 ms 16656 KB Output is correct
9 Correct 22 ms 17168 KB Output is correct
10 Correct 21 ms 17680 KB Output is correct
11 Correct 24 ms 18192 KB Output is correct
12 Correct 20 ms 18704 KB Output is correct
13 Correct 22 ms 19216 KB Output is correct
14 Correct 23 ms 19772 KB Output is correct
15 Correct 22 ms 20240 KB Output is correct
16 Correct 23 ms 20552 KB Output is correct
17 Correct 23 ms 21224 KB Output is correct
18 Correct 25 ms 21744 KB Output is correct
19 Correct 24 ms 22256 KB Output is correct
20 Correct 20 ms 22768 KB Output is correct
21 Correct 19 ms 23280 KB Output is correct
22 Correct 19 ms 23792 KB Output is correct
23 Correct 18 ms 24304 KB Output is correct
24 Correct 20 ms 24824 KB Output is correct
25 Correct 19 ms 25328 KB Output is correct
26 Correct 20 ms 25840 KB Output is correct
27 Correct 20 ms 26352 KB Output is correct
28 Correct 24 ms 26920 KB Output is correct
29 Correct 20 ms 27376 KB Output is correct
30 Correct 22 ms 27888 KB Output is correct
31 Correct 20 ms 28400 KB Output is correct
32 Correct 19 ms 28904 KB Output is correct
33 Correct 23 ms 29424 KB Output is correct
34 Correct 30 ms 29936 KB Output is correct
35 Correct 25 ms 30448 KB Output is correct
36 Correct 27 ms 30960 KB Output is correct
37 Correct 20 ms 31472 KB Output is correct
38 Correct 20 ms 31984 KB Output is correct
39 Correct 21 ms 32496 KB Output is correct
40 Correct 21 ms 33008 KB Output is correct
41 Correct 20 ms 33584 KB Output is correct
42 Correct 20 ms 34096 KB Output is correct
43 Correct 29 ms 34712 KB Output is correct
44 Correct 23 ms 35120 KB Output is correct
45 Correct 20 ms 35536 KB Output is correct
46 Correct 23 ms 36032 KB Output is correct
47 Correct 22 ms 36664 KB Output is correct
48 Correct 23 ms 37176 KB Output is correct
49 Correct 26 ms 37728 KB Output is correct
50 Correct 23 ms 38200 KB Output is correct