oj.uz

Submission #564284

# Submission time Handle Problem Language Result Execution time Memory
564284 2022-05-18T19:59:39 Z blue City (JOI17_city) C++17
8 / 100
 412 ms 54060 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.0048;
	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.0048;
		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 11 ms 22844 KB Output is correct
2 Correct 12 ms 22772 KB Output is correct
3 Correct 12 ms 22844 KB Output is correct
4 Correct 11 ms 22832 KB Output is correct
5 Correct 12 ms 22824 KB Output is correct
6 Correct 12 ms 22844 KB Output is correct
7 Correct 12 ms 22852 KB Output is correct
8 Correct 12 ms 22824 KB Output is correct
9 Correct 12 ms 22844 KB Output is correct
10 Correct 12 ms 22852 KB Output is correct
11 Correct 13 ms 22856 KB Output is correct
12 Correct 12 ms 22788 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 31256 KB Output is correct - L = 143130624
2 Correct 164 ms 31148 KB Output is correct - L = 142868480
3 Correct 167 ms 31376 KB Output is correct - L = 142868480
4 Correct 175 ms 31248 KB Output is correct - L = 143130624
5 Partially correct 400 ms 53284 KB Output is partially correct - L = 474480640
6 Partially correct 396 ms 53272 KB Output is partially correct - L = 474742784
7 Partially correct 412 ms 53252 KB Output is partially correct - L = 474742784
8 Partially correct 391 ms 53132 KB Output is partially correct - L = 475267072
9 Partially correct 331 ms 53924 KB Output is partially correct - L = 476315648
10 Partially correct 328 ms 54060 KB Output is partially correct - L = 477888512
11 Partially correct 343 ms 53928 KB Output is partially correct - L = 478412800
12 Partially correct 331 ms 53996 KB Output is partially correct - L = 478412800
13 Partially correct 377 ms 53556 KB Output is partially correct - L = 476053504
14 Partially correct 384 ms 53500 KB Output is partially correct - L = 475004928
15 Correct 169 ms 31320 KB Output is correct - L = 143130624
16 Correct 168 ms 31356 KB Output is correct - L = 143130624
17 Correct 170 ms 31312 KB Output is correct - L = 142868480
18 Partially correct 376 ms 53560 KB Output is partially correct - L = 478150656
19 Partially correct 376 ms 53576 KB Output is partially correct - L = 478150656
20 Partially correct 375 ms 53476 KB Output is partially correct - L = 478150656
21 Incorrect 371 ms 53612 KB Wrong Answer [6]
22 Halted 0 ms 0 KB -