oj.uz

답안 #563975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563975 2022-05-18T10:14:17 Z blue City (JOI17_city) C++17
83 / 100
 2474 ms 74908 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;
	res.insert(1);
 
	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];
	}

	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();
	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);
 
 
	// 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;
		res.insert(1);
 
		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 22 ms 39356 KB Output is correct
2 Correct 19 ms 39412 KB Output is correct
3 Correct 19 ms 39536 KB Output is correct
4 Correct 19 ms 39524 KB Output is correct
5 Correct 19 ms 39500 KB Output is correct
6 Correct 19 ms 39592 KB Output is correct
7 Correct 19 ms 39476 KB Output is correct
8 Correct 21 ms 39480 KB Output is correct
9 Correct 18 ms 39568 KB Output is correct
10 Correct 21 ms 39428 KB Output is correct
11 Correct 20 ms 39496 KB Output is correct
12 Correct 18 ms 39496 KB Output is correct

Subtask #2
75.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 47948 KB Output is correct - L = 168296448
2 Correct 174 ms 47816 KB Output is correct - L = 167772160
3 Correct 174 ms 47972 KB Output is correct - L = 168034304
4 Correct 176 ms 47888 KB Output is correct - L = 168034304
5 Partially correct 2157 ms 74036 KB Output is partially correct - L = 839647232
6 Partially correct 2191 ms 74120 KB Output is partially correct - L = 839647232
7 Partially correct 2194 ms 74024 KB Output is partially correct - L = 839385088
8 Partially correct 2173 ms 73912 KB Output is partially correct - L = 839385088
9 Partially correct 2067 ms 74604 KB Output is partially correct - L = 841482240
10 Partially correct 2081 ms 74908 KB Output is partially correct - L = 842006528
11 Partially correct 2095 ms 74716 KB Output is partially correct - L = 843055104
12 Partially correct 2088 ms 74904 KB Output is partially correct - L = 843317248
13 Partially correct 2090 ms 74380 KB Output is partially correct - L = 840433664
14 Partially correct 2133 ms 74160 KB Output is partially correct - L = 839647232
15 Correct 202 ms 47948 KB Output is correct - L = 168034304
16 Correct 187 ms 47836 KB Output is correct - L = 168034304
17 Correct 189 ms 47836 KB Output is correct - L = 168034304
18 Partially correct 2127 ms 74132 KB Output is partially correct - L = 843055104
19 Partially correct 2181 ms 74196 KB Output is partially correct - L = 843055104
20 Partially correct 2138 ms 74144 KB Output is partially correct - L = 843055104
21 Partially correct 2392 ms 74312 KB Output is partially correct - L = 841482240
22 Partially correct 2474 ms 74148 KB Output is partially correct - L = 842792960
23 Partially correct 2347 ms 74124 KB Output is partially correct - L = 842792960
24 Partially correct 2363 ms 73988 KB Output is partially correct - L = 842530816
25 Partially correct 2421 ms 74144 KB Output is partially correct - L = 842268672
26 Partially correct 2463 ms 73928 KB Output is partially correct - L = 842006528
27 Partially correct 2396 ms 73900 KB Output is partially correct - L = 841744384