oj.uz

Submission #564290

# Submission time Handle Problem Language Result Execution time Memory
564290 2022-05-18T20:04:33 Z blue City (JOI17_city) C++17
8 / 100
 438 ms 75808 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 = 800'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.007;
	set<ll> res;
	res.insert(1);
 
	while(res.empty() || *res.rbegin() < mx)
	{
		ll curr = *res.rbegin();
		res.insert(max(curr+1, ll(curr*base)));
	}
 
	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 = 800'000;
 
	vll getsizes()
	{
		double base = 1.007;
		set<ll> res;
		res.insert(1);
 
		while(res.empty() || *res.rbegin() < mx)
		{
			ll curr = *res.rbegin();
			res.insert(max(curr+1, ll(curr*base)));
		}
	 
		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 20 ms 44752 KB Output is correct
2 Correct 23 ms 44720 KB Output is correct
3 Correct 21 ms 44752 KB Output is correct
4 Correct 25 ms 44752 KB Output is correct
5 Correct 22 ms 44728 KB Output is correct
6 Correct 23 ms 44680 KB Output is correct
7 Correct 21 ms 44748 KB Output is correct
8 Correct 21 ms 44784 KB Output is correct
9 Correct 23 ms 44752 KB Output is correct
10 Correct 22 ms 44772 KB Output is correct
11 Correct 21 ms 44784 KB Output is correct
12 Correct 21 ms 44760 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 53040 KB Output is correct - L = 114556928
2 Correct 177 ms 53200 KB Output is correct - L = 114819072
3 Correct 180 ms 53152 KB Output is correct - L = 114556928
4 Correct 186 ms 53120 KB Output is correct - L = 114556928
5 Partially correct 413 ms 75200 KB Output is partially correct - L = 340525056
6 Partially correct 395 ms 75268 KB Output is partially correct - L = 340262912
7 Partially correct 438 ms 75112 KB Output is partially correct - L = 340262912
8 Partially correct 437 ms 74944 KB Output is partially correct - L = 340262912
9 Incorrect 361 ms 75808 KB Wrong Answer [6]
10 Halted 0 ms 0 KB -