oj.uz

Submission #564266

# Submission time Handle Problem Language Result Execution time Memory
564266 2022-05-18T19:44:49 Z blue City (JOI17_city) C++17
93 / 100
 525 ms 141796 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 = 2'000'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.0050;
	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 = 2'000'000;
 
	vll getsizes()
	{
		double base = 1.0050;
		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 55 ms 110580 KB Output is correct
2 Correct 49 ms 110596 KB Output is correct
3 Correct 50 ms 110576 KB Output is correct
4 Correct 51 ms 110656 KB Output is correct
5 Correct 50 ms 110336 KB Output is correct
6 Correct 50 ms 110292 KB Output is correct
7 Correct 49 ms 110660 KB Output is correct
8 Correct 48 ms 110408 KB Output is correct
9 Correct 48 ms 110380 KB Output is correct
10 Correct 49 ms 110464 KB Output is correct
11 Correct 50 ms 110532 KB Output is correct
12 Correct 51 ms 110664 KB Output is correct

Subtask #2
85.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 119056 KB Output is correct - L = 117964800
2 Correct 207 ms 119040 KB Output is correct - L = 118226944
3 Correct 208 ms 119012 KB Output is correct - L = 117964800
4 Correct 211 ms 118956 KB Output is correct - L = 118226944
5 Partially correct 430 ms 141096 KB Output is partially correct - L = 427556864
6 Partially correct 431 ms 140912 KB Output is partially correct - L = 427819008
7 Partially correct 429 ms 140916 KB Output is partially correct - L = 427556864
8 Partially correct 448 ms 140668 KB Output is partially correct - L = 427556864
9 Partially correct 370 ms 141652 KB Output is partially correct - L = 429129728
10 Partially correct 366 ms 141796 KB Output is partially correct - L = 430964736
11 Partially correct 377 ms 141768 KB Output is partially correct - L = 431226880
12 Partially correct 374 ms 141684 KB Output is partially correct - L = 431489024
13 Partially correct 403 ms 141280 KB Output is partially correct - L = 429129728
14 Partially correct 420 ms 141184 KB Output is partially correct - L = 428343296
15 Correct 205 ms 119000 KB Output is correct - L = 117964800
16 Correct 206 ms 119208 KB Output is correct - L = 118226944
17 Correct 236 ms 118940 KB Output is correct - L = 117964800
18 Partially correct 414 ms 141192 KB Output is partially correct - L = 431226880
19 Partially correct 406 ms 141188 KB Output is partially correct - L = 431226880
20 Partially correct 450 ms 141240 KB Output is partially correct - L = 431226880
21 Partially correct 422 ms 141176 KB Output is partially correct - L = 430178304
22 Partially correct 454 ms 141152 KB Output is partially correct - L = 430964736
23 Partially correct 481 ms 141268 KB Output is partially correct - L = 430964736
24 Partially correct 482 ms 141104 KB Output is partially correct - L = 430702592
25 Partially correct 507 ms 141152 KB Output is partially correct - L = 430440448
26 Partially correct 525 ms 140900 KB Output is partially correct - L = 430440448
27 Partially correct 510 ms 140872 KB Output is partially correct - L = 429916160