Submission #427346

#	Time	Username	Problem	Language	Result	Execution time	Memory
427346		kai824	City (JOI17_city)	C++17	8 / 100	396 ms	18324 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> adjl[250005];

void dfs(int node,ll bits,int p=-1){
	Code(node,bits);
	int sz=adjl[node].size();
	if(p!=-1)sz--;
	int j=1;
	if(sz>1 or true){//if sz=1, then don't bother encoding it in...
		while((1ll<<j)<sz)j++;
		bits<<=(j);
	}
	for(int x:adjl[node]){
		if(x==p)continue;
		dfs(x,bits,node);
		bits++;
	}
}

void Encode(int n, int a[], int b[]){
	for(int i=0;i+1<n;i++){
		adjl[a[i]].push_back(b[i]);
		adjl[b[i]].push_back(a[i]);
	}
	dfs(0,1ll,-1);
	//Code(i, 0LL): node, label...
}

Device

#include "Device.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void InitDevice(){}

int Answer(long long s, long long t){
	vector<int> v1,v2;
	while(s>0){
		v1.push_back(s&1);
		s/=2;
	}
	while(t>0){
		v2.push_back(t&1);
		t/=2;
	}
	reverse(v1.begin(),v1.end());
	reverse(v2.begin(),v2.end());
	//for(int x:v1)cout<<x;cout<<'\n';
	//for(int x:v2)cout<<x;cout<<'\n';

	for(int i=0;i<v1.size() && i<v2.size();i++){//ensure they have common prefix...
		if(v1[i]!=v2[i])return 2;
	}
	if(v1.size()<v2.size())return 1;
	else return 0;
}

Compilation message (stderr)

Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0;i<v1.size() && i<v2.size();i++){//ensure they have common prefix...
      |              ~^~~~~~~~~~
Device.cpp:23:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0;i<v1.size() && i<v2.size();i++){//ensure they have common prefix...
      |                             ~^~~~~~~~~~

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