oj.uz

Submission #564249

# Submission time Handle Problem Language Result Execution time Memory
564249 2022-05-18T19:38:02 Z blue City (JOI17_city) C++17
87 / 100
 523 ms 70676 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.004;
	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 < 1000; i++)
		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.004;
		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 < 1000; i++)
			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 22 ms 39388 KB Output is correct
2 Correct 24 ms 39452 KB Output is correct
3 Correct 21 ms 39492 KB Output is correct
4 Correct 21 ms 39496 KB Output is correct
5 Correct 21 ms 39496 KB Output is correct
6 Correct 23 ms 39456 KB Output is correct
7 Correct 20 ms 39472 KB Output is correct
8 Correct 20 ms 39408 KB Output is correct
9 Correct 21 ms 39424 KB Output is correct
10 Correct 20 ms 39448 KB Output is correct
11 Correct 20 ms 39428 KB Output is correct
12 Correct 22 ms 39500 KB Output is correct

Subtask #2
79.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 47872 KB Output is correct - L = 183238656
2 Correct 194 ms 47792 KB Output is correct - L = 182976512
3 Correct 224 ms 47752 KB Output is correct - L = 183238656
4 Correct 198 ms 47776 KB Output is correct - L = 183238656
5 Partially correct 523 ms 69844 KB Output is partially correct - L = 624951296
6 Partially correct 515 ms 69688 KB Output is partially correct - L = 625213440
7 Partially correct 510 ms 69732 KB Output is partially correct - L = 624951296
8 Partially correct 474 ms 69528 KB Output is partially correct - L = 625213440
9 Partially correct 407 ms 70340 KB Output is partially correct - L = 626262016
10 Partially correct 393 ms 70424 KB Output is partially correct - L = 628359168
11 Partially correct 432 ms 70676 KB Output is partially correct - L = 628883456
12 Partially correct 420 ms 70412 KB Output is partially correct - L = 628883456
13 Partially correct 436 ms 70156 KB Output is partially correct - L = 625999872
14 Partially correct 404 ms 69984 KB Output is partially correct - L = 625737728
15 Correct 188 ms 47872 KB Output is correct - L = 183238656
16 Correct 177 ms 47884 KB Output is correct - L = 183238656
17 Correct 182 ms 47744 KB Output is correct - L = 183238656
18 Partially correct 403 ms 69996 KB Output is partially correct - L = 628621312
19 Partially correct 409 ms 70040 KB Output is partially correct - L = 628621312
20 Partially correct 457 ms 70024 KB Output is partially correct - L = 628621312
21 Partially correct 433 ms 70032 KB Output is partially correct - L = 627572736
22 Partially correct 453 ms 70156 KB Output is partially correct - L = 628359168
23 Partially correct 432 ms 69940 KB Output is partially correct - L = 628359168
24 Partially correct 433 ms 69884 KB Output is partially correct - L = 628097024
25 Partially correct 413 ms 69760 KB Output is partially correct - L = 628097024
26 Partially correct 472 ms 69776 KB Output is partially correct - L = 627834880
27 Partially correct 449 ms 69744 KB Output is partially correct - L = 627572736