oj.uz

Submission #564279

# Submission time Handle Problem Language Result Execution time Memory
564279 2022-05-18T19:55:34 Z blue City (JOI17_city) C++17
93 / 100
 470 ms 54052 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 = 400'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 = 400'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 13 ms 22796 KB Output is correct
2 Correct 12 ms 22816 KB Output is correct
3 Correct 12 ms 22844 KB Output is correct
4 Correct 11 ms 22844 KB Output is correct
5 Correct 12 ms 22856 KB Output is correct
6 Correct 12 ms 22844 KB Output is correct
7 Correct 15 ms 22832 KB Output is correct
8 Correct 16 ms 22832 KB Output is correct
9 Correct 12 ms 22848 KB Output is correct
10 Correct 11 ms 22852 KB Output is correct
11 Correct 13 ms 22868 KB Output is correct
12 Correct 12 ms 22824 KB Output is correct

Subtask #2
85.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 31340 KB Output is correct - L = 117964800
2 Correct 173 ms 31360 KB Output is correct - L = 118226944
3 Correct 168 ms 31488 KB Output is correct - L = 117964800
4 Correct 180 ms 31244 KB Output is correct - L = 118226944
5 Partially correct 412 ms 53292 KB Output is partially correct - L = 427556864
6 Partially correct 438 ms 53308 KB Output is partially correct - L = 427819008
7 Partially correct 466 ms 53296 KB Output is partially correct - L = 427556864
8 Partially correct 410 ms 53020 KB Output is partially correct - L = 427556864
9 Partially correct 363 ms 53940 KB Output is partially correct - L = 429129728
10 Partially correct 335 ms 53960 KB Output is partially correct - L = 430964736
11 Partially correct 357 ms 54052 KB Output is partially correct - L = 431226880
12 Partially correct 402 ms 53980 KB Output is partially correct - L = 431489024
13 Partially correct 381 ms 53640 KB Output is partially correct - L = 429129728
14 Partially correct 409 ms 53368 KB Output is partially correct - L = 428343296
15 Correct 202 ms 31404 KB Output is correct - L = 117964800
16 Correct 197 ms 31216 KB Output is correct - L = 118226944
17 Correct 196 ms 31316 KB Output is correct - L = 117964800
18 Partially correct 418 ms 53600 KB Output is partially correct - L = 431226880
19 Partially correct 399 ms 53676 KB Output is partially correct - L = 431226880
20 Partially correct 430 ms 53508 KB Output is partially correct - L = 431226880
21 Partially correct 435 ms 53512 KB Output is partially correct - L = 430178304
22 Partially correct 400 ms 53484 KB Output is partially correct - L = 430964736
23 Partially correct 420 ms 53408 KB Output is partially correct - L = 430964736
24 Partially correct 464 ms 53356 KB Output is partially correct - L = 430702592
25 Partially correct 399 ms 53428 KB Output is partially correct - L = 430440448
26 Partially correct 439 ms 53264 KB Output is partially correct - L = 430440448
27 Partially correct 470 ms 53272 KB Output is partially correct - L = 429916160