oj.uz

Submission #564227

# Submission time Handle Problem Language Result Execution time Memory
564227 2022-05-18T19:22:02 Z blue City (JOI17_city) C++17
83 / 100
 417 ms 84340 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.0023;
	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.0023;
		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 39520 KB Output is correct
2 Correct 18 ms 39520 KB Output is correct
3 Correct 19 ms 39492 KB Output is correct
4 Correct 19 ms 39436 KB Output is correct
5 Correct 18 ms 39536 KB Output is correct
6 Correct 19 ms 39528 KB Output is correct
7 Correct 18 ms 39500 KB Output is correct
8 Correct 18 ms 39496 KB Output is correct
9 Correct 18 ms 39516 KB Output is correct
10 Correct 19 ms 39476 KB Output is correct
11 Correct 20 ms 39516 KB Output is correct
12 Correct 18 ms 39516 KB Output is correct

Subtask #2
75.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 47924 KB Output is correct - L = 168296448
2 Correct 169 ms 47852 KB Output is correct - L = 167772160
3 Correct 167 ms 47892 KB Output is correct - L = 168034304
4 Correct 180 ms 47980 KB Output is correct - L = 168034304
5 Partially correct 391 ms 69816 KB Output is partially correct - L = 839647232
6 Partially correct 403 ms 83308 KB Output is partially correct - L = 839647232
7 Partially correct 404 ms 83220 KB Output is partially correct - L = 839385088
8 Partially correct 402 ms 83104 KB Output is partially correct - L = 839385088
9 Partially correct 349 ms 84180 KB Output is partially correct - L = 841482240
10 Partially correct 361 ms 84240 KB Output is partially correct - L = 842006528
11 Partially correct 344 ms 84340 KB Output is partially correct - L = 843055104
12 Partially correct 333 ms 84272 KB Output is partially correct - L = 843317248
13 Partially correct 376 ms 83920 KB Output is partially correct - L = 840433664
14 Partially correct 417 ms 83388 KB Output is partially correct - L = 839647232
15 Correct 170 ms 54808 KB Output is correct - L = 168034304
16 Correct 173 ms 54780 KB Output is correct - L = 168034304
17 Correct 173 ms 54792 KB Output is correct - L = 168034304
18 Partially correct 402 ms 83320 KB Output is partially correct - L = 843055104
19 Partially correct 384 ms 83432 KB Output is partially correct - L = 843055104
20 Partially correct 388 ms 83500 KB Output is partially correct - L = 843055104
21 Partially correct 404 ms 83464 KB Output is partially correct - L = 841482240
22 Partially correct 390 ms 83412 KB Output is partially correct - L = 842792960
23 Partially correct 397 ms 83416 KB Output is partially correct - L = 842792960
24 Partially correct 399 ms 83444 KB Output is partially correct - L = 842530816
25 Partially correct 409 ms 83256 KB Output is partially correct - L = 842268672
26 Partially correct 415 ms 83324 KB Output is partially correct - L = 842006528
27 Partially correct 416 ms 83356 KB Output is partially correct - L = 841744384