Submission #64541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
64541	2018-08-04T20:33:38 Z	zadrga	City (JOI17_city)	C++14	8 / 100	196 ms	42224 KB

Encoder

#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 270

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

int first_over[maxn], 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 < maxn; 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

#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 270
 
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(la <= lb && rb <= ra)
		return 1;

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

	return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14336 KB	Output is correct
2	Correct	10 ms	14336 KB	Output is correct
3	Correct	11 ms	14592 KB	Output is correct
4	Correct	10 ms	14336 KB	Output is correct
5	Correct	10 ms	14592 KB	Output is correct
6	Correct	10 ms	14592 KB	Output is correct
7	Correct	10 ms	14336 KB	Output is correct
8	Correct	10 ms	14592 KB	Output is correct
9	Correct	10 ms	14336 KB	Output is correct
10	Correct	10 ms	14432 KB	Output is correct
11	Correct	10 ms	14336 KB	Output is correct
12	Correct	10 ms	14336 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	21576 KB	Output is correct - L = 105011656
2	Correct	172 ms	21544 KB	Output is correct - L = 106011767
3	Correct	172 ms	21488 KB	Output is correct - L = 104011545
4	Correct	172 ms	21488 KB	Output is correct - L = 105011656
5	Incorrect	196 ms	42224 KB	Wrong Answer [3]
6	Halted	0 ms	0 KB	-