oj.uz

답안 #72700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72700 2018-08-26T16:09:17 Z IvanC City (JOI17_city) C++11
100 / 100
 542 ms 56728 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250010;

typedef long long ll;
typedef pair<int,int> ii;

static vector<int> grafo[MAXN],sequencia;
static int ini[MAXN],idx[MAXN],dfsCount;

static void build_sequence(){

	const long double factor = 1.055645;

	sequencia.push_back(0);
	sequencia.push_back(1);

	for(int i = 2;i<256;i++){
		int x = int( factor*sequencia.back() );
		if(x == sequencia.back()) x += 1;
		sequencia.push_back(x);
	}

}

static void dfs(int v,int p){

	ini[v] = ++dfsCount;

	for(int u : grafo[v]){
		if(u == p) continue;
		dfs(u,v);
	}

	int lo = 0, hi = 255, mid, ans = -1;

	while(lo <= hi){
		mid = (lo + hi)/2;
		if(ini[v] + sequencia[mid] >= dfsCount){
			ans = mid;
			hi = mid - 1;
		}
		else{
			lo = mid + 1;
		}
	}

	idx[v] = ans;
	dfsCount = ini[v] + sequencia[ans];

}

static long long coding(int A,int B){

	long long davez = A;
	davez += (1LL << 20)*ll(B);

	return davez;

}

void Encode(int N, int A[], int B[]){

	build_sequence();

	for(int i = 0;i<N-1;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}

	dfs(0,-1);

	for(int i = 0;i<N;i++){
		ini[i]--;
	}

	for (int i = 0; i < N; ++i) {
		Code(i, coding(ini[i],idx[i]) );
	}

}


#include "Device.h"
#include <bits/stdc++.h>
using namespace std;

static vector<int> sequencia;

static void build_sequence(){

	const long double factor = 1.055645;

	sequencia.push_back(0);
	sequencia.push_back(1);

	for(int i = 2;i<256;i++){
		int x = int( factor*sequencia.back() );
		if(x == sequencia.back()) x += 1;
		sequencia.push_back(x);
	}

}

void InitDevice(){
	
	build_sequence();

}

static void Magic(long long X, int &ini, int& fim ){

	ini = 0;
	fim = 0;

	long long temp = (X >> 20);
	fim = sequencia[temp];

	X -= (temp)*(1 << 20);
	ini += X;
	fim += ini;

}

int Answer(long long S, long long T){

	if(S == T) return 2;

	int inia,fima,inib,fimb;

	Magic(S,inia,fima);
	Magic(T,inib,fimb);

	if(inia <= inib && inib <= fima) return 1;
	if(inib <= inia && inia <= fimb) return 0;

	return 2;

}

Subtask #1
8.0 / 8.0

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

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 19368 KB Output is correct - L = 101711872
2 Correct 168 ms 19440 KB Output is correct - L = 101711872
3 Correct 167 ms 19440 KB Output is correct - L = 100663296
4 Correct 169 ms 19440 KB Output is correct - L = 101711872
5 Correct 469 ms 55104 KB Output is correct - L = 218103808
6 Correct 500 ms 55208 KB Output is correct - L = 218103808
7 Correct 542 ms 55144 KB Output is correct - L = 219152384
8 Correct 493 ms 54768 KB Output is correct - L = 218103808
9 Correct 428 ms 56408 KB Output is correct - L = 229638144
10 Correct 418 ms 56536 KB Output is correct - L = 231735296
11 Correct 429 ms 56728 KB Output is correct - L = 231735296
12 Correct 439 ms 56552 KB Output is correct - L = 231735296
13 Correct 480 ms 56032 KB Output is correct - L = 223346688
14 Correct 526 ms 55704 KB Output is correct - L = 220200960
15 Correct 170 ms 19952 KB Output is correct - L = 101711872
16 Correct 169 ms 19440 KB Output is correct - L = 101711872
17 Correct 172 ms 19440 KB Output is correct - L = 100663296
18 Correct 500 ms 55568 KB Output is correct - L = 230686720
19 Correct 492 ms 55952 KB Output is correct - L = 230686720
20 Correct 495 ms 55544 KB Output is correct - L = 230686720
21 Correct 479 ms 55520 KB Output is correct - L = 230686720
22 Correct 528 ms 55528 KB Output is correct - L = 230686720
23 Correct 536 ms 55600 KB Output is correct - L = 230686720
24 Correct 502 ms 55416 KB Output is correct - L = 229638144
25 Correct 518 ms 55432 KB Output is correct - L = 228589568
26 Correct 503 ms 55312 KB Output is correct - L = 227540992
27 Correct 534 ms 55064 KB Output is correct - L = 226492416