oj.uz

Submission #564229

# Submission time Handle Problem Language Result Execution time Memory
564229 2022-05-18T19:22:47 Z blue City (JOI17_city) C++17
86 / 100
 422 ms 71212 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.003;
	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.003;
		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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39524 KB Output is correct
2 Correct 20 ms 39516 KB Output is correct
3 Correct 21 ms 39524 KB Output is correct
4 Correct 20 ms 39472 KB Output is correct
5 Correct 20 ms 39500 KB Output is correct
6 Correct 20 ms 39524 KB Output is correct
7 Correct 21 ms 39508 KB Output is correct
8 Correct 20 ms 39504 KB Output is correct
9 Correct 21 ms 39524 KB Output is correct
10 Correct 20 ms 39520 KB Output is correct
11 Correct 21 ms 39436 KB Output is correct
12 Correct 20 ms 39488 KB Output is correct

Subtask #2
78.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 48160 KB Output is correct - L = 152043520
2 Correct 177 ms 48212 KB Output is correct - L = 152043520
3 Correct 183 ms 48120 KB Output is correct - L = 152043520
4 Correct 174 ms 48036 KB Output is correct - L = 152043520
5 Partially correct 401 ms 70068 KB Output is partially correct - L = 667156480
6 Partially correct 410 ms 70428 KB Output is partially correct - L = 667418624
7 Partially correct 406 ms 70420 KB Output is partially correct - L = 667156480
8 Partially correct 406 ms 70140 KB Output is partially correct - L = 667680768
9 Partially correct 344 ms 70960 KB Output is partially correct - L = 668991488
10 Partially correct 335 ms 71096 KB Output is partially correct - L = 670040064
11 Partially correct 344 ms 71212 KB Output is partially correct - L = 670826496
12 Partially correct 335 ms 71064 KB Output is partially correct - L = 671088640
13 Partially correct 379 ms 71024 KB Output is partially correct - L = 668467200
14 Partially correct 392 ms 70536 KB Output is partially correct - L = 668205056
15 Correct 169 ms 48304 KB Output is correct - L = 152305664
16 Correct 172 ms 48536 KB Output is correct - L = 152305664
17 Correct 174 ms 48432 KB Output is correct - L = 152305664
18 Partially correct 379 ms 70448 KB Output is partially correct - L = 670826496
19 Partially correct 383 ms 70672 KB Output is partially correct - L = 670826496
20 Partially correct 389 ms 70468 KB Output is partially correct - L = 670826496
21 Partially correct 384 ms 70528 KB Output is partially correct - L = 669253632
22 Partially correct 397 ms 70444 KB Output is partially correct - L = 670564352
23 Partially correct 402 ms 70388 KB Output is partially correct - L = 670564352
24 Partially correct 399 ms 70376 KB Output is partially correct - L = 670302208
25 Partially correct 399 ms 70384 KB Output is partially correct - L = 670040064
26 Partially correct 421 ms 70428 KB Output is partially correct - L = 669777920
27 Partially correct 422 ms 70284 KB Output is partially correct - L = 669515776