oj.uz

Submission #61047

# Submission time Handle Problem Language Result Execution time Memory
61047 2018-07-25T06:47:09 Z 윤교준(#1762) City (JOI17_city) C++11
100 / 100
 530 ms 56784 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#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)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

static const int MAXN = 250005;

static vector<int> G[MAXN];
static vector<int> V;

static int O[MAXN], C[MAXN];
static int A[MAXN], B[MAXN];

static int N;

static void dfs(int i, int &c) {
	c++; O[i] = c; C[i] = 1;
	for(int v : G[i]) if(!O[v]) {
		dfs(v, c);
		C[i] += C[v];
	}
	C[i] = *lower_bound(allv(V), C[i]);
	c = O[i] + C[i] - 1;
}

void Encode(int N, int A[], int B[]) {
	V.eb(1);
	for(int i = 2; i < (1<<20); i <<= 1) {
		V.eb(i);
		for(int j = i+1; j < (1<<20); j <<= 1)
			V.eb(j);
	}
	for(int i = 250000; 1 < i; i >>= 1) {
		V.eb(i);
		for(int j = i-1; 1 < j; j >>= 1)
			V.eb(j);
	}
	sorv(V); univ(V);

	::N = N;
	for(int i = 0; i < N-1; i++) {
		::A[i] = A[i];
		::B[i] = B[i];
		fg(G, A[i], B[i]);
	}

	{ int t = 0; dfs(0, t); }

	for(int i = 0; i < N; i++) {
		ll key = O[i]-1;
		key <<= 8;

		key |= int(lower_bound(allv(V), C[i]) - V.begin());

		Code(i, key);
	}
}

#include "Device.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#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)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

static vector<int> V;

void InitDevice() {
	V.eb(1);
	for(int i = 2; i < (1<<20); i <<= 1) {
		V.eb(i);
		for(int j = i+1; j < (1<<20); j <<= 1)
			V.eb(j);
	}
	for(int i = 250000; 1 < i; i >>= 1) {
		V.eb(i);
		for(int j = i-1; 1 < j; j >>= 1)
			V.eb(j);
	}
	sorv(V); univ(V);
}

int Answer(long long S, long long T) {
	int si = (S>>8), sc = S&((1<<8)-1);
	int ti = (T>>8), tc = T&((1<<8)-1);
	sc = V[sc]; tc = V[tc];

	if(ti < si && si < ti+tc) return 0;
	if(si < ti && ti < si+sc) return 1;
	return 2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12544 KB Output is correct
2 Correct 8 ms 12544 KB Output is correct
3 Correct 8 ms 12544 KB Output is correct
4 Correct 9 ms 12544 KB Output is correct
5 Correct 9 ms 12544 KB Output is correct
6 Correct 9 ms 12544 KB Output is correct
7 Correct 9 ms 12544 KB Output is correct
8 Correct 9 ms 12312 KB Output is correct
9 Correct 9 ms 12312 KB Output is correct
10 Correct 11 ms 12288 KB Output is correct
11 Correct 9 ms 12544 KB Output is correct
12 Correct 8 ms 12544 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 19640 KB Output is correct - L = 238592
2 Correct 174 ms 19616 KB Output is correct - L = 276992
3 Correct 170 ms 19464 KB Output is correct - L = 248832
4 Correct 169 ms 19640 KB Output is correct - L = 199424
5 Correct 477 ms 55256 KB Output is correct - L = 116818432
6 Correct 494 ms 55272 KB Output is correct - L = 135443200
7 Correct 496 ms 55248 KB Output is correct - L = 125610240
8 Correct 513 ms 54664 KB Output is correct - L = 127399168
9 Correct 425 ms 56568 KB Output is correct - L = 152798208
10 Correct 418 ms 56784 KB Output is correct - L = 134268416
11 Correct 424 ms 56680 KB Output is correct - L = 134217984
12 Correct 454 ms 56584 KB Output is correct - L = 75499264
13 Correct 478 ms 56312 KB Output is correct - L = 172424960
14 Correct 474 ms 55632 KB Output is correct - L = 160193536
15 Correct 168 ms 19392 KB Output is correct - L = 227584
16 Correct 169 ms 19568 KB Output is correct - L = 278528
17 Correct 166 ms 19440 KB Output is correct - L = 211200
18 Correct 465 ms 55728 KB Output is correct - L = 83886848
19 Correct 480 ms 55664 KB Output is correct - L = 63999744
20 Correct 478 ms 55768 KB Output is correct - L = 63999744
21 Correct 494 ms 55512 KB Output is correct - L = 136316416
22 Correct 473 ms 55496 KB Output is correct - L = 69997312
23 Correct 513 ms 55696 KB Output is correct - L = 70170112
24 Correct 506 ms 55488 KB Output is correct - L = 66139648
25 Correct 519 ms 55416 KB Output is correct - L = 73142016
26 Correct 530 ms 55136 KB Output is correct - L = 69539328
27 Correct 526 ms 55248 KB Output is correct - L = 78555392