oj.uz

답안 #564271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564271 2022-05-18T19:49:18 Z blue City (JOI17_city) C++17
89 / 100
 458 ms 141716 KB 
#include "Encoder.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cassert>
using namespace std;
 
	namespace{
using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
 
 
const int mx = 2'000'000;
using ll = long long;
using vll = vector<ll>;
 
int N;
vi edge[mx];
 
vll code(mx, 0);
 
vll dfsind(mx, 0);
vll subtree(mx, 1);
vll fakesubtree(mx, 1);
 
// int ct = -1;
 
 
 
 
 
 
 
vll getsizes()
{
	double base = 1.0055;
	set<ll> res;
	res.insert(1);
 
	double curr = 1;
	while(res.empty() || *res.rbegin() < mx)
	{
		curr *= base;
		res.insert(curr);
	}
 
	for(int i = 1; i <= mx; i = (double(i) + double(i / 100)) + 1)
		if(sz(res) < 4096)
			res.insert(i);
 
	vll resvec;
	for(ll k : res)
		resvec.push_back(k);
 
	return resvec;
}
 
 
vll sizes;
 
 
 
void dfs(int u, int p, int firstind)
{
	// cerr << "dfs " << u << '\n';
	dfsind[u] = firstind;
	firstind++;
	for(int v : edge[u])
	{
		if(v == p) continue;
		dfs(v, u, firstind);
		subtree[u] += subtree[v];
		firstind += subtree[v];
	}
 
	// if(dfsind[u] == 366)
		// cerr << u << " : " << subtree[u] << " -> ";
 
	auto z = lower_bound(sizes.begin(), sizes.end(), (ll) subtree[u]);
	assert(z != sizes.end() && *z >= subtree[u]);
	subtree[u] = *z;
	assert(subtree[u] <= mx);
	fakesubtree[u] = z - sizes.begin();
	
	// if(dfsind[u] == 366)
		// cerr << subtree[u] << '\n';
}
 
 
 
 
 
 
 
	}
 
 
void Encode(int N_, int A[], int B[])
{
	N = N_;
	sizes = getsizes();
 
	cerr << sz(sizes) << '\n';
 
	// for(int z : sizes)
	// 	cerr << z << ' ';
	// cerr << '\n';
 
 
 
	for(int e = 0; e < N-1; e++)
	{
		edge[A[e]].push_back(B[e]);
		edge[B[e]].push_back(A[e]);
	}
 
	// cerr << "done\n";
 
	dfs(0, -1, 0);
 
 
	// cerr << "done2\n";
 
	for(int i = 0; i < N; i++)
	{
		// cerr << i << " : " << dfsind[i] << ' ' << subtree[i] << ' ' << ((dfsind[i]<<18) | subtree[i]) << '\n';
		Code(i, (fakesubtree[i] << 18) | dfsind[i]);
	}
}
#include "Device.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
 
namespace
{
	using vi = vector<int>;
	using vvi = vector<vi>;
	using ll = long long;
	using vll = vector<ll>;
	#define sz(x) int(x.size())
 
	const int mx = 2'000'000;
 
	vll getsizes()
	{
		double base = 1.0055;
		set<ll> res;
		res.insert(1);
	 
		double curr = 1;
		while(res.empty() || *res.rbegin() < mx)
		{
			curr *= base;
			res.insert(curr);
		}
 
		for(int i = 1; i <= mx; i = (double(i) + double(i / 100)) + 1)
			if(sz(res) < 4096)
				res.insert(i);
	 
		vll resvec;
		for(ll k : res)
			resvec.push_back(k);
	 
		return resvec;
	}
 
 
	vll sizes;
 
}
 
void InitDevice()
{
	sizes = getsizes();
}
 
int Answer(long long S, long long T)
{
	// cerr << "query : " << S << ' ' << T << '\n';
// 
	// bool flag = 1;
	ll s_st = sizes[S>>18];
	ll s_ind = S & ((1<<18) - 1);
 
	ll t_st = sizes[T>>18];
	ll t_ind = T & ((1<<18) - 1);
 
 	// if(flag)
 	// {
 	// 	cerr << "bad query\n";
 	// 	cerr << "\n\n";
		// cerr << S << ' ' << T << " : " << s_ind << ' ' << s_st << " | " << t_ind << ' ' << t_st << "\n";
		// cerr << (T>>18) << '\n';
 	// }
 	
	if(t_ind <= s_ind && s_ind < t_ind + t_st)
	{
		// if(flag)cerr << "case : 0\n";
		return 0;
	}
	else if(s_ind <= t_ind && t_ind < s_ind + s_st)
	{
		// if(flag)cerr << "case : 1\n";
		return 1;
	}
	else
	{
		// if(flag)cerr << "case : 2\n";
		return 2;
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 110504 KB Output is correct
2 Correct 47 ms 110828 KB Output is correct
3 Correct 46 ms 110644 KB Output is correct
4 Correct 47 ms 110568 KB Output is correct
5 Correct 50 ms 110520 KB Output is correct
6 Correct 46 ms 110856 KB Output is correct
7 Correct 49 ms 110744 KB Output is correct
8 Correct 48 ms 110940 KB Output is correct
9 Correct 50 ms 110504 KB Output is correct
10 Correct 48 ms 110768 KB Output is correct
11 Correct 48 ms 110844 KB Output is correct
12 Correct 46 ms 110780 KB Output is correct

Subtask #2
81.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 119164 KB Output is correct - L = 127139840
2 Correct 212 ms 119076 KB Output is correct - L = 127139840
3 Correct 213 ms 119108 KB Output is correct - L = 127139840
4 Correct 200 ms 119136 KB Output is correct - L = 127139840
5 Partially correct 430 ms 141028 KB Output is partially correct - L = 556007424
6 Partially correct 427 ms 141024 KB Output is partially correct - L = 556007424
7 Partially correct 437 ms 141012 KB Output is partially correct - L = 556007424
8 Partially correct 431 ms 140724 KB Output is partially correct - L = 556531712
9 Partially correct 375 ms 141548 KB Output is partially correct - L = 558104576
10 Partially correct 377 ms 141716 KB Output is partially correct - L = 559153152
11 Partially correct 364 ms 141696 KB Output is partially correct - L = 559415296
12 Partially correct 422 ms 141668 KB Output is partially correct - L = 559677440
13 Partially correct 398 ms 141356 KB Output is partially correct - L = 557318144
14 Partially correct 414 ms 141372 KB Output is partially correct - L = 556531712
15 Correct 208 ms 119080 KB Output is correct - L = 127139840
16 Correct 200 ms 119056 KB Output is correct - L = 127139840
17 Correct 204 ms 119072 KB Output is correct - L = 127139840
18 Partially correct 410 ms 141216 KB Output is partially correct - L = 559415296
19 Partially correct 418 ms 141348 KB Output is partially correct - L = 559415296
20 Partially correct 432 ms 141328 KB Output is partially correct - L = 559415296
21 Partially correct 414 ms 141212 KB Output is partially correct - L = 558366720
22 Partially correct 433 ms 141140 KB Output is partially correct - L = 559153152
23 Partially correct 423 ms 141184 KB Output is partially correct - L = 559153152
24 Partially correct 449 ms 141172 KB Output is partially correct - L = 558891008
25 Partially correct 418 ms 141216 KB Output is partially correct - L = 558628864
26 Partially correct 441 ms 140960 KB Output is partially correct - L = 558366720
27 Partially correct 458 ms 141168 KB Output is partially correct - L = 557842432