oj.uz

Submission #564282

# Submission time Handle Problem Language Result Execution time Memory
564282 2022-05-18T19:58:38 Z blue City (JOI17_city) C++17
72 / 100
 482 ms 54568 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 = 400'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.001;
	set<ll> res;
	res.insert(1);

	while(res.empty() || *res.rbegin() < mx)
	{
		ll curr = *res.rbegin();
		res.insert(max(curr+1, ll(curr*base)));
	}
 
	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 = 400'000;
 
	vll getsizes()
	{
		double base = 1.001;
		set<ll> res;
		res.insert(1);

		while(res.empty() || *res.rbegin() < mx)
		{
			ll curr = *res.rbegin();
			res.insert(max(curr+1, ll(curr*base)));
		}
	 
		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 14 ms 23616 KB Output is correct
2 Correct 14 ms 23620 KB Output is correct
3 Correct 14 ms 23616 KB Output is correct
4 Correct 14 ms 23604 KB Output is correct
5 Correct 15 ms 23604 KB Output is correct
6 Correct 14 ms 23496 KB Output is correct
7 Correct 14 ms 23620 KB Output is correct
8 Correct 13 ms 23624 KB Output is correct
9 Correct 14 ms 23620 KB Output is correct
10 Correct 14 ms 23568 KB Output is correct
11 Correct 14 ms 23612 KB Output is correct
12 Correct 14 ms 23616 KB Output is correct

Subtask #2
64.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 32032 KB Output is correct - L = 183238656
2 Correct 187 ms 31904 KB Output is correct - L = 182976512
3 Correct 171 ms 31988 KB Output is correct - L = 183238656
4 Correct 188 ms 31940 KB Output is correct - L = 183238656
5 Partially correct 432 ms 53712 KB Output is partially correct - L = 1861484544
6 Partially correct 393 ms 53664 KB Output is partially correct - L = 1861484544
7 Partially correct 425 ms 53748 KB Output is partially correct - L = 1861484544
8 Partially correct 482 ms 53604 KB Output is partially correct - L = 1861746688
9 Partially correct 358 ms 54508 KB Output is partially correct - L = 1863057408
10 Partially correct 357 ms 54568 KB Output is partially correct - L = 1864105984
11 Partially correct 362 ms 54328 KB Output is partially correct - L = 1865154560
12 Partially correct 343 ms 54468 KB Output is partially correct - L = 1865416704
13 Partially correct 415 ms 54108 KB Output is partially correct - L = 1862533120
14 Partially correct 389 ms 53764 KB Output is partially correct - L = 1862270976
15 Correct 194 ms 31996 KB Output is correct - L = 183238656
16 Correct 172 ms 31936 KB Output is correct - L = 183238656
17 Correct 164 ms 31900 KB Output is correct - L = 183238656
18 Partially correct 448 ms 53936 KB Output is partially correct - L = 1865154560
19 Partially correct 368 ms 54044 KB Output is partially correct - L = 1865154560
20 Partially correct 397 ms 54068 KB Output is partially correct - L = 1865154560
21 Partially correct 441 ms 53916 KB Output is partially correct - L = 1863581696
22 Partially correct 384 ms 53872 KB Output is partially correct - L = 1864892416
23 Partially correct 470 ms 53848 KB Output is partially correct - L = 1864892416
24 Partially correct 394 ms 53712 KB Output is partially correct - L = 1864630272
25 Partially correct 426 ms 53824 KB Output is partially correct - L = 1864368128
26 Partially correct 420 ms 53788 KB Output is partially correct - L = 1864368128
27 Partially correct 430 ms 53720 KB Output is partially correct - L = 1863843840