Submission #218086

#	Time	Username	Problem	Language	Result	Execution time	Memory
218086		patrikpavic2	City (JOI17_city)	C++17	8 / 100	254 ms	43504 KiB

Encoder

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

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

using namespace std;

typedef long long ll;

const int N = 3e5 + 500;

vector < int > v[N];
ll tko[N];

void dfs(int x, int lst,int dulj){
	int lg = 1, cnt = 0;
	for(;(1 << lg) < (int)v[x].size() - (x != lst);lg++);
	for(int y : v[x]){
		if(y == lst) continue;
		tko[y] = tko[x] + (1LL << dulj) * (ll)(cnt++);
		dfs(y, x, dulj + lg);
	}
	//printf("x = %d tko = %lld dulj = %d\n", x, tko[x] + (1 << dulj), dulj);
	Code(x, tko[x] + (1LL << dulj));
}

void Encode(int n, int u1[], int u2[]){
	for(int i = 0;i + 1 < n;i++)
		v[u1[i]].PB(u2[i]),
		v[u2[i]].PB(u1[i]);
	dfs(0, 0, 0);
}

Device

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

typedef long long ll;

void InitDevice(){
	return;
}

bool dijete(ll A, ll B){
	int dulj_A = 0, dulj_B = 0;
	for(;(1LL << dulj_A) <= A;dulj_A++);
	for(;(1LL << dulj_B) <= B;dulj_B++);
	if(dulj_A > dulj_B) return 0;
	//printf("dulj_A = %d dulj_B = %d\n", dulj_A, dulj_B);
	//printf("Je li B %lld dijete od A %lld\n", B, A);
	for(int i = 0;i + 1 < dulj_A;i++){
		if((A & (1 << i)) != (B & (1 << i)))
			return 0;
	}
	//printf("DA\n");
	return 1;
}

int Answer(ll A, ll B)
{
	if(dijete(B, A)) 
		return 0;
	if(dijete(A, B)) 
		return 1;
	return 2;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92