Submission #64555

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
64555	2018-08-04T20:57:58 Z	zadrga	City (JOI17_city)	C++14	100 / 100	594 ms	63968 KB

Encoder

/*
Idea:
- https://codeforces.com/blog/entry/51010 (city)
*/

#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxm 1000111
#define maxn 250111
#define maxk 252

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int first_over[maxm], a[maxk];
int l[maxn], len[maxn], cnt;
vector<int> adj[maxn];

void init(){
	cnt = 0;
	for(int i = 0; i < maxn; i++)
		adj[i].clear();

	a[1] = 1;
	for(int i = 2; i < maxk; i++){
		a[i] = (double) a[i - 1] * 1.05;
		a[i] = max(a[i], a[i - 1] + 1);
	}

	int ind = 1;
	for(int i = 1; i <= a[maxk - 1]; i++){
		while(a[ind] < i)
			ind++;

		first_over[i] = ind;
	}
}

void DFS(int x, int p){
	l[x] = ++cnt;
	for(int v : adj[x]){
		if(v == p)
			continue;

		DFS(v, x);
	}
	int num = first_over[cnt - l[x] + 1];
	cnt = l[x] + a[num] - 1;
	len[x] = num; 
}

void Encode(int N, int A[], int B[]){
	init();

	for(int i = 0; i < N - 1; i++){
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}

	DFS(0, -1);

	for(int i = 0; i < N; i++)
		Code(i, 1LL * len[i] * maxm + l[i]);
}

Device

/*
Idea:
- https://codeforces.com/blog/entry/51010 (city)
*/

#include "Device.h"
#include <bits/stdc++.h>

using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxm 1000111
#define maxn 250111
#define maxk 252
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int a1[maxk];

void InitDevice(){
	a1[1] = 1;
	for(int i = 2; i < maxk; i++){
		a1[i] = (double) a1[i - 1] * 1.05;
		a1[i] = max(a1[i], a1[i - 1] + 1);
	}
}

void decode(ll x, int &l, int &d){
	l = x % maxm;
	d = l + a1[x / maxm] - 1; 
}

int Answer(long long S, long long T){
	int la, ra; decode(S, la, ra);
	int lb, rb; decode(T, lb, rb);
	if(lb <= la && ra <= rb)
		return 0;

	if(la <= lb && rb <= ra)
		return 1;

	return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	19712 KB	Output is correct
2	Correct	13 ms	19712 KB	Output is correct
3	Correct	12 ms	19712 KB	Output is correct
4	Correct	14 ms	19864 KB	Output is correct
5	Correct	13 ms	19712 KB	Output is correct
6	Correct	12 ms	19712 KB	Output is correct
7	Correct	31 ms	19624 KB	Output is correct
8	Correct	12 ms	19664 KB	Output is correct
9	Correct	12 ms	19656 KB	Output is correct
10	Correct	12 ms	19712 KB	Output is correct
11	Correct	13 ms	19656 KB	Output is correct
12	Correct	13 ms	19712 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	26608 KB	Output is correct - L = 105011656
2	Correct	174 ms	26856 KB	Output is correct - L = 106011767
3	Correct	229 ms	26888 KB	Output is correct - L = 104011545
4	Correct	166 ms	26952 KB	Output is correct - L = 105011656
5	Correct	498 ms	62432 KB	Output is correct - L = 228025309
6	Correct	501 ms	62616 KB	Output is correct - L = 229025420
7	Correct	500 ms	62576 KB	Output is correct - L = 229025420
8	Correct	504 ms	62024 KB	Output is correct - L = 231025642
9	Correct	427 ms	63944 KB	Output is correct - L = 239026530
10	Correct	414 ms	63912 KB	Output is correct - L = 241026752
11	Correct	416 ms	63808 KB	Output is correct - L = 242026863
12	Correct	405 ms	63968 KB	Output is correct - L = 242026863
13	Correct	451 ms	63160 KB	Output is correct - L = 234025975
14	Correct	479 ms	62992 KB	Output is correct - L = 231025642
15	Correct	170 ms	26608 KB	Output is correct - L = 105011656
16	Correct	169 ms	26864 KB	Output is correct - L = 105011656
17	Correct	170 ms	26824 KB	Output is correct - L = 105011656
18	Correct	468 ms	62824 KB	Output is correct - L = 241026752
19	Correct	484 ms	62824 KB	Output is correct - L = 241026752
20	Correct	594 ms	63184 KB	Output is correct - L = 241026752
21	Correct	465 ms	63016 KB	Output is correct - L = 240026641
22	Correct	495 ms	62952 KB	Output is correct - L = 240026641
23	Correct	458 ms	62752 KB	Output is correct - L = 240026641
24	Correct	490 ms	62816 KB	Output is correct - L = 239026530
25	Correct	477 ms	62768 KB	Output is correct - L = 238026419
26	Correct	497 ms	62624 KB	Output is correct - L = 237026308
27	Correct	512 ms	62448 KB	Output is correct - L = 236026197