Submission #218130

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218130	2020-04-01T09:54:40 Z	patrikpavic2	City (JOI17_city)	C++17	8 / 100	573 ms	77760 KB

Encoder

#include "Encoder.h"
#include <vector>
#include <cstdio>
#include <set>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

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

const int N = 5e5 + 500;

int L[N], R[N], cur = 0, n;
vector < int > v[N];

void dfs(int x,int lst){
	L[x] = cur++;
	for(int y : v[x])
		if(y != lst)
			dfs(y, x);
	R[x] = cur;
}


void Encode(int nn, int u1[], int u2[]){
	n = nn;
	for(int i = 0;i + 1 < n;i++)
		v[u1[i]].PB(u2[i]),
		v[u2[i]].PB(u1[i]);
	dfs(0, 0);
	for(int i = 0;i < n;i++){
		//printf("i = %d kod = %lld\n", i, (ll)R[i] * (R[i] - 1) / 2LL + L[i]);
		Code(i, (ll)R[i] * (R[i] - 1) / 2LL + L[i]);
	}
}

Device

#include "Device.h"
#include <cstdio>

typedef long long ll;

void InitDevice(){
	return;
}

inline int get_R(ll X){
	ll ret = 0;
	for(int i = 18;i >= 0;i--){
		ret += (1 << i);
		if(ret * (ret - 1) / 2LL > X)
			ret -= (1 << i);
	}
	return ret;
}


int Answer(ll A, ll B){
	//printf("A = %lld B = %lld\n", A, B);
	int R_A = get_R(A);
	int R_B = get_R(B);
	int L_A = A - R_A * (R_A - 1) / 2LL;
	int L_B = B - R_B * (R_B - 1) / 2LL;
	//printf("L_A = %d R_A = %d\n", L_A, R_A);
	//printf("L_B = %d R_B = %d\n", L_B, R_B);
	if(L_B <= L_A && L_A < R_B)
		return 0;
	if(L_A <= L_B && L_B < R_A)
		return 1;
	return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	24320 KB	Output is correct
2	Correct	16 ms	24064 KB	Output is correct
3	Correct	16 ms	24064 KB	Output is correct
4	Correct	16 ms	24320 KB	Output is correct
5	Correct	15 ms	24320 KB	Output is correct
6	Correct	15 ms	24064 KB	Output is correct
7	Correct	15 ms	24320 KB	Output is correct
8	Correct	15 ms	24064 KB	Output is correct
9	Correct	17 ms	24064 KB	Output is correct
10	Correct	15 ms	24064 KB	Output is correct
11	Correct	16 ms	24320 KB	Output is correct
12	Correct	17 ms	24064 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	37616 KB	Output is correct - L = 245349
2	Correct	262 ms	35824 KB	Output is correct - L = 244649
3	Correct	264 ms	37360 KB	Output is correct - L = 245349
4	Correct	252 ms	36848 KB	Output is correct - L = 245349
5	Incorrect	573 ms	77760 KB	Wrong Answer [6]
6	Halted	0 ms	0 KB	-