oj.uz

답안 #564233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564233 2022-05-18T19:24:05 Z blue City (JOI17_city) C++17
8 / 100
 402 ms 71032 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.004;
	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, 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 = 700'000;
 
	vll getsizes()
	{
		double base = 1.004;
		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)
{
	// 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 + s_st <= t_ind + t_st)
	{
		// if(flag)cerr << "case : 0\n";
		return 0;
	}
	else if(s_ind <= t_ind && t_ind + t_st <= 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 20 ms 39388 KB Output is correct
2 Correct 17 ms 39452 KB Output is correct
3 Correct 18 ms 39460 KB Output is correct
4 Correct 18 ms 39472 KB Output is correct
5 Correct 18 ms 39392 KB Output is correct
6 Correct 18 ms 39364 KB Output is correct
7 Correct 19 ms 39396 KB Output is correct
8 Correct 18 ms 39392 KB Output is correct
9 Correct 18 ms 39392 KB Output is correct
10 Correct 19 ms 39368 KB Output is correct
11 Correct 19 ms 39368 KB Output is correct
12 Correct 19 ms 39352 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 47740 KB Output is correct - L = 132907008
2 Correct 168 ms 47768 KB Output is correct - L = 132907008
3 Correct 179 ms 47808 KB Output is correct - L = 132907008
4 Correct 163 ms 47848 KB Output is correct - L = 132907008
5 Partially correct 402 ms 69896 KB Output is partially correct - L = 519569408
6 Partially correct 388 ms 69816 KB Output is partially correct - L = 519569408
7 Partially correct 400 ms 69880 KB Output is partially correct - L = 519569408
8 Partially correct 399 ms 69716 KB Output is partially correct - L = 519569408
9 Partially correct 334 ms 70352 KB Output is partially correct - L = 520617984
10 Partially correct 324 ms 70404 KB Output is partially correct - L = 522715136
11 Incorrect 328 ms 71032 KB Wrong Answer [6]
12 Halted 0 ms 0 KB -