oj.uz

Submission #564258

# Submission time Handle Problem Language Result Execution time Memory
564258 2022-05-18T19:41:15 Z blue City (JOI17_city) C++17
93 / 100
 490 ms 70504 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.005;
	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++)
		if(sz(res) < 1024)
			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 = 700'000;
 
	vll getsizes()
	{
		double base = 1.005;
		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++)
		if(sz(res) < 1024)
			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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39248 KB Output is correct
2 Correct 19 ms 39292 KB Output is correct
3 Correct 22 ms 39276 KB Output is correct
4 Correct 23 ms 39196 KB Output is correct
5 Correct 23 ms 39192 KB Output is correct
6 Correct 20 ms 39260 KB Output is correct
7 Correct 19 ms 39240 KB Output is correct
8 Correct 24 ms 39312 KB Output is correct
9 Correct 20 ms 39312 KB Output is correct
10 Correct 19 ms 39264 KB Output is correct
11 Correct 19 ms 39260 KB Output is correct
12 Correct 19 ms 39260 KB Output is correct

Subtask #2
85.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 47684 KB Output is correct - L = 117964800
2 Correct 173 ms 47644 KB Output is correct - L = 118226944
3 Correct 217 ms 47612 KB Output is correct - L = 117964800
4 Correct 178 ms 47744 KB Output is correct - L = 118226944
5 Partially correct 431 ms 69860 KB Output is partially correct - L = 427556864
6 Partially correct 446 ms 69796 KB Output is partially correct - L = 427819008
7 Partially correct 474 ms 69880 KB Output is partially correct - L = 427556864
8 Partially correct 454 ms 69476 KB Output is partially correct - L = 427556864
9 Partially correct 346 ms 70420 KB Output is partially correct - L = 429129728
10 Partially correct 380 ms 70504 KB Output is partially correct - L = 430964736
11 Partially correct 362 ms 70404 KB Output is partially correct - L = 431226880
12 Partially correct 360 ms 70392 KB Output is partially correct - L = 431489024
13 Partially correct 438 ms 69980 KB Output is partially correct - L = 429129728
14 Partially correct 408 ms 69960 KB Output is partially correct - L = 428343296
15 Correct 193 ms 47784 KB Output is correct - L = 117964800
16 Correct 186 ms 47748 KB Output is correct - L = 118226944
17 Correct 204 ms 47732 KB Output is correct - L = 117964800
18 Partially correct 386 ms 69976 KB Output is partially correct - L = 431226880
19 Partially correct 435 ms 69856 KB Output is partially correct - L = 431226880
20 Partially correct 425 ms 69836 KB Output is partially correct - L = 431226880
21 Partially correct 385 ms 69892 KB Output is partially correct - L = 430178304
22 Partially correct 429 ms 69964 KB Output is partially correct - L = 430964736
23 Partially correct 434 ms 69984 KB Output is partially correct - L = 430964736
24 Partially correct 406 ms 69832 KB Output is partially correct - L = 430702592
25 Partially correct 442 ms 69756 KB Output is partially correct - L = 430440448
26 Partially correct 490 ms 69764 KB Output is partially correct - L = 430440448
27 Partially correct 455 ms 69728 KB Output is partially correct - L = 429916160