oj.uz

Submission #564235

# Submission time Handle Problem Language Result Execution time Memory
564235 2022-05-18T19:26:39 Z blue City (JOI17_city) C++17
87 / 100
 553 ms 71064 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.0032;
	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.0032;
		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 19 ms 39524 KB Output is correct
2 Correct 18 ms 39520 KB Output is correct
3 Correct 18 ms 39480 KB Output is correct
4 Correct 20 ms 39508 KB Output is correct
5 Correct 20 ms 39532 KB Output is correct
6 Correct 19 ms 39396 KB Output is correct
7 Correct 18 ms 39524 KB Output is correct
8 Correct 22 ms 39292 KB Output is correct
9 Correct 20 ms 39344 KB Output is correct
10 Correct 20 ms 39412 KB Output is correct
11 Correct 19 ms 39392 KB Output is correct
12 Correct 19 ms 39492 KB Output is correct

Subtask #2
79.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 47792 KB Output is correct - L = 147849216
2 Correct 178 ms 47996 KB Output is correct - L = 147849216
3 Correct 178 ms 47840 KB Output is correct - L = 147849216
4 Correct 169 ms 47824 KB Output is correct - L = 147849216
5 Partially correct 421 ms 69812 KB Output is partially correct - L = 630980608
6 Partially correct 422 ms 69880 KB Output is partially correct - L = 630980608
7 Partially correct 431 ms 69952 KB Output is partially correct - L = 630718464
8 Partially correct 460 ms 69580 KB Output is partially correct - L = 630456320
9 Partially correct 361 ms 70408 KB Output is partially correct - L = 632553472
10 Partially correct 356 ms 70464 KB Output is partially correct - L = 633864192
11 Partially correct 395 ms 70472 KB Output is partially correct - L = 634388480
12 Partially correct 416 ms 70916 KB Output is partially correct - L = 634650624
13 Partially correct 462 ms 70816 KB Output is partially correct - L = 631767040
14 Partially correct 441 ms 70980 KB Output is partially correct - L = 631504896
15 Correct 216 ms 48888 KB Output is correct - L = 147849216
16 Correct 210 ms 48868 KB Output is correct - L = 147849216
17 Correct 229 ms 48816 KB Output is correct - L = 147849216
18 Partially correct 486 ms 70932 KB Output is partially correct - L = 634388480
19 Partially correct 483 ms 71012 KB Output is partially correct - L = 634388480
20 Partially correct 427 ms 71064 KB Output is partially correct - L = 634388480
21 Partially correct 418 ms 71028 KB Output is partially correct - L = 632815616
22 Partially correct 484 ms 70888 KB Output is partially correct - L = 634126336
23 Partially correct 473 ms 71004 KB Output is partially correct - L = 634126336
24 Partially correct 483 ms 70888 KB Output is partially correct - L = 633864192
25 Partially correct 521 ms 70956 KB Output is partially correct - L = 633602048
26 Partially correct 544 ms 70800 KB Output is partially correct - L = 633602048
27 Partially correct 553 ms 70772 KB Output is partially correct - L = 633077760