oj.uz

답안 #67509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67509 2018-08-14T12:12:33 Z reality City (JOI17_city) C++17
100 / 100
 539 ms 88040 KB 
#include "Encoder.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 = 1e6;

static const db w = 1.05;

static int len[N];

static int wh[N];

vi g[N + 69];

static int T = -1;

void dfs(int node = 0,int prev = -1) {
	int beg = ++T;
	for (auto it : g[node])
		if (it != prev)
			dfs(it,node);
	int cnt = lower_bound(len,len + 256,T - beg + 1) - len;
	T = beg + len[cnt] - 1;
	Code(node,1ll * cnt * N + beg);
}

void Encode(int NN, int A[], int B[]) {
	int n = NN;
	for (int i = 0;i + 1 < n;++i) {
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	len[0] = 1;
	for (int i = 1;i < 256;++i)
		len[i] = max(len[i - 1] + 1,(int)(w * len[i - 1]));
	dfs();
}

#include "Device.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 = 1e6;

static const db w = 1.05;

static int len[N];


void InitDevice() {
	len[0] = 1;
	for (int i = 1;i < 256;++i)
		len[i] = max(len[i - 1] + 1,(int)(w * len[i - 1]));
}

int Answer(ll S,ll T) {
	int a = S % N;
	int b = a + len[(S / N)] - 1;
	int c = T % N;
	int d = c + len[(T / N)] - 1;
	if (c <= a && b <= d)
		return 0;
	if (a <= c && d <= b)
		return 1;
	return 2;
}

Compilation message

Encoder.cpp:27:12: warning: 'wh' defined but not used [-Wunused-variable]
 static int wh[N];
            ^~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47616 KB Output is correct
2 Correct 24 ms 47560 KB Output is correct
3 Correct 24 ms 47688 KB Output is correct
4 Correct 25 ms 47608 KB Output is correct
5 Correct 23 ms 47616 KB Output is correct
6 Correct 26 ms 47560 KB Output is correct
7 Correct 23 ms 47616 KB Output is correct
8 Correct 23 ms 47712 KB Output is correct
9 Correct 24 ms 47616 KB Output is correct
10 Correct 27 ms 47616 KB Output is correct
11 Correct 23 ms 47616 KB Output is correct
12 Correct 24 ms 47600 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 54640 KB Output is correct - L = 104000000
2 Correct 179 ms 54712 KB Output is correct - L = 105000000
3 Correct 188 ms 54856 KB Output is correct - L = 103000000
4 Correct 183 ms 54768 KB Output is correct - L = 104000000
5 Correct 511 ms 86592 KB Output is correct - L = 227000000
6 Correct 506 ms 86456 KB Output is correct - L = 228000000
7 Correct 530 ms 86552 KB Output is correct - L = 228000000
8 Correct 504 ms 86216 KB Output is correct - L = 230000000
9 Correct 445 ms 87800 KB Output is correct - L = 238000000
10 Correct 415 ms 88040 KB Output is correct - L = 240000000
11 Correct 433 ms 88024 KB Output is correct - L = 241000000
12 Correct 442 ms 87912 KB Output is correct - L = 241000000
13 Correct 468 ms 87272 KB Output is correct - L = 233000000
14 Correct 510 ms 87160 KB Output is correct - L = 230000000
15 Correct 185 ms 54696 KB Output is correct - L = 104000000
16 Correct 189 ms 54632 KB Output is correct - L = 104000000
17 Correct 185 ms 54760 KB Output is correct - L = 104000000
18 Correct 500 ms 87056 KB Output is correct - L = 240000000
19 Correct 486 ms 86952 KB Output is correct - L = 240000000
20 Correct 493 ms 86936 KB Output is correct - L = 240000000
21 Correct 496 ms 87056 KB Output is correct - L = 239000000
22 Correct 527 ms 87104 KB Output is correct - L = 239000000
23 Correct 508 ms 86856 KB Output is correct - L = 239000000
24 Correct 529 ms 86600 KB Output is correct - L = 238000000
25 Correct 511 ms 87096 KB Output is correct - L = 237000000
26 Correct 538 ms 86792 KB Output is correct - L = 236000000
27 Correct 539 ms 86560 KB Output is correct - L = 235000000