Submission #558425

#	Time	Username	Problem	Language	Result	Execution time	Memory
558425		fatemetmhr	City (JOI17_city)	C++17	8 / 100	459 ms	49852 KiB

Encoder

// Be name khoda //

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

using namespace std;

typedef long long ll;

#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define pb          push_back


const int maxn5 = 5e5 + 10;
const int maxnt = 4e5 + 10;

static ll code[maxn5], sz[maxn5], av[maxn5];
static vector <int> adj[maxn5];

static bool cmp(int v, int u){
	return sz[v] > sz[u];
}


static void dfs_det(int v, int par){
	sz[v] = 1;
	for(auto u : adj[v]) if(u != par){
		dfs_det(u, v);
		sz[v] += sz[u];
	}
	return;
}

static void dfs_code(int v, int par, int pt){
	code[v] = av[v] + (1LL << pt);
	if(adj[v].size() == 1 && v)
		return;
	sort(all(adj[v]), cmp);
	int done = 0;
	for(auto u : adj[v]) if(u != par){
		done++;
		if(done == adj[v].size() - 1 + (v == 0)){
			if(done == 1){
				av[u] = av[v];
				dfs_code(u, v, pt + 1);
				break;
			}
			av[u] = av[v];
			dfs_code(u, v, pt);
			break;
		}
		av[u] = av[v] + (1LL << pt);
		pt++;
		dfs_code(u, v, pt);
	}
	return;
}

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

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

	dfs_det(0, -1);
	dfs_code(0, -1, 0);

	for (int i = 0; i < N; ++i) {
		Code(i, code[i]);
	}
}

Device

// Be name khoda //

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

using namespace std;

typedef long long ll;


#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define pb          push_back


const int maxn5 = 4e3 + 10;
const int maxnt = 4e5 + 10;

void InitDevice()
{
	return;
}

int Answer(long long S, long long T)
{
	int h1 = 0, h2 = 0;
	for(int i = 60; i >= 0; i--) if((S >> i)&1){
		h1 = i;
		break;
	}
	for(int i = 60; i >= 0; i--) if((T >> i)&1){
		h2 = i;
		break;
	}
	if(h1 == h2)
		return 2;
	if(h1 < h2){
		for(int i = 0; i < h1; i++) if(((S >> i)&1) != ((T >> i)&1))
			return 2;
		return 1;
	}
	for(int i = 0; i < h2; i++) if(((S >> i)&1) != ((T >> i)&1))
		return 2;
	return 0;
}

Compilation message (stderr)

Encoder.cpp: In function 'void dfs_code(int, int, int)':
Encoder.cpp:44:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(done == adj[v].size() - 1 + (v == 0)){
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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