oj.uz

답안 #563964

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563964 2022-05-18T10:05:48 Z blue City (JOI17_city) C++17
83 / 100
 436 ms 70740 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 = 700'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.0023;
	set<ll> res;
 
	double curr = 1;
	while(res.empty() || *res.rbegin() < mx)
	{
		curr *= base;
		res.insert(curr);
	}
 
	vll resvec;
	for(ll k : res)
		resvec.push_back(k);
 
	return resvec;
}
 
 
vll sizes;
 
 
 
void dfs(int u, int p)
{
	// cerr << "dfs " << u << '\n';
	dfsind[u] = ++ct;
	for(int v : edge[u])
	{
		if(v == p) continue;
		dfs(v, u);
		subtree[u] += subtree[v];
	}
	auto z = lower_bound(sizes.begin(), sizes.end(), (ll) subtree[u]);
	assert(z != sizes.end() && *z >= subtree[u]);
	subtree[u] = *z;
	fakesubtree[u] = z - sizes.begin();
}
 
 
 
 
 
 
 
	}
 
 
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);
 
 
	// 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 = 700'000;
 
	vll getsizes()
	{
		double base = 1.0023;
		set<ll> res;
 
		double curr = 1;
		while(res.empty() || *res.rbegin() < mx)
		{
			curr *= base;
			res.insert(curr);
		}
 
		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)
{
	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);
 
	// cerr << S << ' ' << T << " : " << s_ind << ' ' << s_st << " | " << t_ind << ' ' << t_st << "\n";
 
	if(t_ind <= s_ind && s_ind + s_st <= t_ind + t_st)
		return 0;
	else if(s_ind <= t_ind && t_ind + t_st <= s_ind + s_st)
		return 1;
	else
		return 2;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 39572 KB Output is correct
2 Correct 19 ms 39492 KB Output is correct
3 Correct 20 ms 39516 KB Output is correct
4 Correct 21 ms 39372 KB Output is correct
5 Correct 25 ms 39520 KB Output is correct
6 Correct 20 ms 39516 KB Output is correct
7 Correct 20 ms 39544 KB Output is correct
8 Correct 18 ms 39516 KB Output is correct
9 Correct 19 ms 39448 KB Output is correct
10 Correct 20 ms 39344 KB Output is correct
11 Correct 19 ms 39496 KB Output is correct
12 Correct 19 ms 39528 KB Output is correct

Subtask #2
75.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 48012 KB Output is correct - L = 168296448
2 Correct 175 ms 47888 KB Output is correct - L = 167772160
3 Correct 181 ms 48176 KB Output is correct - L = 168034304
4 Correct 180 ms 47912 KB Output is correct - L = 168034304
5 Partially correct 433 ms 69804 KB Output is partially correct - L = 839647232
6 Partially correct 436 ms 69928 KB Output is partially correct - L = 839647232
7 Partially correct 417 ms 69828 KB Output is partially correct - L = 839385088
8 Partially correct 421 ms 69608 KB Output is partially correct - L = 839385088
9 Partially correct 340 ms 70532 KB Output is partially correct - L = 841482240
10 Partially correct 346 ms 70524 KB Output is partially correct - L = 842006528
11 Partially correct 333 ms 70544 KB Output is partially correct - L = 843055104
12 Partially correct 337 ms 70740 KB Output is partially correct - L = 843317248
13 Partially correct 371 ms 70208 KB Output is partially correct - L = 840433664
14 Partially correct 392 ms 70100 KB Output is partially correct - L = 839647232
15 Correct 181 ms 47924 KB Output is correct - L = 168034304
16 Correct 176 ms 47828 KB Output is correct - L = 168034304
17 Correct 185 ms 47892 KB Output is correct - L = 168034304
18 Partially correct 375 ms 70160 KB Output is partially correct - L = 843055104
19 Partially correct 383 ms 70056 KB Output is partially correct - L = 843055104
20 Partially correct 375 ms 70068 KB Output is partially correct - L = 843055104
21 Partially correct 383 ms 70144 KB Output is partially correct - L = 841482240
22 Partially correct 386 ms 70016 KB Output is partially correct - L = 842792960
23 Partially correct 400 ms 70088 KB Output is partially correct - L = 842792960
24 Partially correct 396 ms 69964 KB Output is partially correct - L = 842530816
25 Partially correct 390 ms 70004 KB Output is partially correct - L = 842268672
26 Partially correct 407 ms 70028 KB Output is partially correct - L = 842006528
27 Partially correct 435 ms 69904 KB Output is partially correct - L = 841744384