| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 114247 | faustaadp | City (JOI17_city) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
}