#include "Encoder.h"
#include <vector>
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll x[552525],ki[552525],ka[552525],sz,dep[552525],te;
vector<ll> v[552525];
void dfs(ll aa,ll bb)
{
ll ii,sz=0;
vector<ll> tem;
priority_queue<pair<ll,ll> > pq;
for(ii=0;ii<v[aa].size();ii++)
if(v[aa][ii]!=bb)
{
dfs(v[aa][ii],aa);
sz++;
pq.push(mp(-dep[v[aa][ii]],v[aa][ii]));
}
while(sz>2)
{
ll xa=pq.top().se;
pq.pop();
ll xb=pq.top().se;
pq.pop();
te++;
dep[te]=max(dep[xa],dep[xb])+1;
ki[te]=xa;
ka[te]=xb;
pq.push(mp(-dep[te],te));
sz--;
}
if(sz==2)
{
ll xa=pq.top().se;
pq.pop();
ll xb=pq.top().se;
pq.pop();
dep[aa]=max(dep[xa],dep[xb])+1;
ki[aa]=xa;
ka[aa]=xb;
}
else
if(sz==1)
{
ll xa=pq.top().se;
pq.pop();
dep[aa]=dep[xa]+1;
ki[aa]=xa;
}
else
dep[aa]=1;
}
void dfs2(ll aa,ll cc)
{
if(aa==-1)return;
x[aa]=cc;
dfs2(ki[aa],cc*2+1);
dfs2(ka[aa],cc*2+2);
}
void Encode(int N, std::vector<int> A, std::vector<int> B)
{
int i;
for(i=0;i<(N-1);i++)
{
v[A[i]].pb(B[i]);
v[B[i]].pb(A[i]);
}
te=N;
memset(ki,-1,sizeof(ki));
memset(ka,-1,sizeof(ka));
dfs(0,0);
dfs2(0,0);
for(i=0;i<N;i++)
{
// cout<<i<<"->"<<x[i]<<"\n";
assignCode(i, x[i]);
}
}
#include "device.h"
void InitDevice() {
}
int Answer(long long S, long long T) {
if(S<T)
{
while(T>S)
{
T--;
T/=2;
}
if(T==S)return 1;
return 2;
}
else
{
while(S>T)
{
S--;
S/=2;
}
if(S==T)return 0;
return 2;
}
}
Compilation message
Encoder.cpp: In function 'void dfs(ll, ll)':
Encoder.cpp:19:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
Encoder.cpp: In function 'void Encode(int, std::vector<int>, std::vector<int>)':
Encoder.cpp:83:4: error: 'assignCode' was not declared in this scope
assignCode(i, x[i]);
^~~~~~~~~~
Encoder.cpp:83:4: note: suggested alternative: 'sigignore'
assignCode(i, x[i]);
^~~~~~~~~~
sigignore
Device.cpp:1:10: fatal error: device.h: No such file or directory
#include "device.h"
^~~~~~~~~~
compilation terminated.
