oj.uz

Submission #563962

# Submission time Handle Problem Language Result Execution time Memory
563962 2022-05-18T10:05:16 Z blue City (JOI17_city) C++17
8 / 100
 512 ms 70556 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.0030;
	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.0030;
		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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39480 KB Output is correct
2 Correct 21 ms 39540 KB Output is correct
3 Correct 19 ms 39488 KB Output is correct
4 Correct 20 ms 39472 KB Output is correct
5 Correct 21 ms 39404 KB Output is correct
6 Correct 26 ms 39436 KB Output is correct
7 Correct 20 ms 39484 KB Output is correct
8 Correct 22 ms 39460 KB Output is correct
9 Correct 22 ms 39288 KB Output is correct
10 Correct 22 ms 39476 KB Output is correct
11 Correct 21 ms 39524 KB Output is correct
12 Correct 23 ms 39416 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 47852 KB Output is correct - L = 152043520
2 Correct 192 ms 47756 KB Output is correct - L = 152043520
3 Correct 195 ms 47844 KB Output is correct - L = 152043520
4 Correct 206 ms 47812 KB Output is correct - L = 152043520
5 Partially correct 444 ms 69820 KB Output is partially correct - L = 667156480
6 Partially correct 512 ms 69724 KB Output is partially correct - L = 667418624
7 Partially correct 437 ms 69868 KB Output is partially correct - L = 667156480
8 Partially correct 404 ms 69628 KB Output is partially correct - L = 667680768
9 Partially correct 371 ms 70440 KB Output is partially correct - L = 668991488
10 Partially correct 357 ms 70396 KB Output is partially correct - L = 670040064
11 Partially correct 330 ms 70556 KB Output is partially correct - L = 670826496
12 Partially correct 344 ms 70444 KB Output is partially correct - L = 671088640
13 Partially correct 375 ms 70200 KB Output is partially correct - L = 668467200
14 Partially correct 399 ms 69892 KB Output is partially correct - L = 668205056
15 Correct 178 ms 47952 KB Output is correct - L = 152305664
16 Incorrect 184 ms 47976 KB Wrong Answer [6]
17 Halted 0 ms 0 KB -