oj.uz

답안 #563966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563966 2022-05-18T10:06:29 Z blue City (JOI17_city) C++17
8 / 100
 462 ms 70788 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.0028;
	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.0028;
		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 20 ms 39436 KB Output is correct
2 Correct 19 ms 39280 KB Output is correct
3 Correct 24 ms 39508 KB Output is correct
4 Correct 20 ms 39500 KB Output is correct
5 Correct 21 ms 39516 KB Output is correct
6 Correct 19 ms 39332 KB Output is correct
7 Correct 21 ms 39484 KB Output is correct
8 Correct 32 ms 39496 KB Output is correct
9 Correct 19 ms 39520 KB Output is correct
10 Correct 20 ms 39524 KB Output is correct
11 Correct 19 ms 39516 KB Output is correct
12 Correct 19 ms 39444 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 47868 KB Output is correct - L = 156237824
2 Correct 223 ms 47764 KB Output is correct - L = 156499968
3 Correct 188 ms 47944 KB Output is correct - L = 156237824
4 Correct 186 ms 47900 KB Output is correct - L = 156499968
5 Partially correct 462 ms 69944 KB Output is partially correct - L = 708050944
6 Partially correct 452 ms 69992 KB Output is partially correct - L = 708313088
7 Partially correct 395 ms 69900 KB Output is partially correct - L = 708050944
8 Partially correct 412 ms 69640 KB Output is partially correct - L = 708050944
9 Partially correct 353 ms 70756 KB Output is partially correct - L = 709623808
10 Partially correct 355 ms 70500 KB Output is partially correct - L = 710934528
11 Partially correct 345 ms 70788 KB Output is partially correct - L = 711720960
12 Partially correct 333 ms 70632 KB Output is partially correct - L = 711983104
13 Partially correct 408 ms 70168 KB Output is partially correct - L = 709361664
14 Partially correct 449 ms 69876 KB Output is partially correct - L = 708575232
15 Correct 199 ms 47944 KB Output is correct - L = 156499968
16 Incorrect 195 ms 47884 KB Wrong Answer [6]
17 Halted 0 ms 0 KB -