| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 566801 | Uzouf | Saveit (IOI10_saveit) | C++14 | 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 <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "encoder.h"
void encode(int n,int h,int p,int a[],int b[]) {
vector<vector<int> > v(n+5);
int dis[n+5][n+5];
for (int i=0;i<n+5;i++) {
for (int j=0;j<n+5;j++) {
dis[i][j]=2000;
}
dis[i][i]=0;
}
for (int i=0;i<p;i++) {
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
dis[a[i]][b[i]]=dis[b[i]][a[i]]=1;
}
int par[n+5];
for (int i=0;i<n+5;i++) par[i]=i;
queue<int> q;
q.push(0); par[0]=-1;
while (!q.empty()) {
int i=q.front();
q.pop();
for (int j:v[i]) {
if (par[j]==j) {
par[j]=i; q.push(j);
}
}
}
//tree:
for (int i=0;i<n;i++) {
if (par[i]==-1) par[i]=i;
for (int pp=0;pp<10;pp++) {
if (((1<<pp)&par[i])==0) encode_bit(0);
else encode_bit(1);
}
}
for (int hub=1;hub<h;hub++) {
//cout<<hub<<":"<<endl;
int dis[n+5];
bool vis[n+5];
for (int i=0;i<n+5;i++) {
vis[i]=false;
}
queue<int> q;
q.push(hub); dis[hub]=0; vis[hub]=true;
while (!q.empty()) {
int i=q.front();
q.pop();
for (int j:v[i]) {
if (!vis[j]) {
vis[j]=true; dis[j]=dis[i]+1; q.push(j);
}
}
}
string ss;
for (int i=0;i<n;i++) {
int nm=dis[i]-dis[par[i]];
if (nm==0) ss+='0';
else if (nm==1) ss+='1';
else ss+='2';
if (ss.size()==3) {
int lol=((ss[0]-'0')*9)+((ss[1]-'0')*3)+(ss[2]-'0');
//if (hub==1) cout<<ss<<' '<<lol<<endl;
for (int j=4;j>=0;j--) {
int bb=1;
if ((lol&(1<<j))==0) bb=0;
//if (hub==1) cout<<bb<<' ';
encode_bit(bb);
}
ss=""; //cout<<endl;
}
}
if (ss.size()==0) continue;
int lol=(ss[0]-'0');
if (ss.size()==2) lol+=((ss[1]-'0')*3);
//if (hub==1) cout<<ss<<' '<<lol<<endl;
for (int j=4;j>=0;j--) {
int bb=1;
if ((lol&(1<<j))==0) bb=0;
//if (hub==1) cout<<bb<<' ';
encode_bit(bb);
}//cout<<endl<<endl;
}
}
void decode(int n,int h) {
vector<vector<int> > v(n+5);
bool done[n+5][n+5];
int par[n+5];
for (int i=0;i<n;i++) {
int tmp=0;
for (int p=0;p<10;p++) {
tmp+=(decode_bit()*(1<<p));
}
par[i]=tmp;
v[i].push_back(tmp); v[tmp].push_back(i);
}
for (int hub=0;hub<h;hub++) {
int dis[n+5][n+5];
memset(done,false,sizeof done);
if (hub>0) {
string ss;
int tt=n/3;
if (n%3!=0) tt++;
int i=-1;
while (tt--) {
for (int i5=0;i5<5;i5++) ss+=(decode_bit()+'0');
i+=3;
int dec=0,ii=0;
for (int j=4;j>=0;j--) {
int rn=ss[ii]-'0';
int cl=rn*(1<<j);
dec+=cl; ii++;
}
//if (hub==1) cout<<ss<<' '<<dec<<endl;
int l[3];
l[0]=0; l[1]=0; l[2]=0;
if (dec-9>=0) {dec-=9; l[0]=1; if (dec-9>=0) {dec-=9; l[0]=2;} }
if (dec-3>=0) {dec-=3; l[1]=1; if (dec-3>=0) {dec-=3; l[1]=2;} }
if (dec-1>=0) {dec-=1; l[2]=1; if (dec-1>=0) {dec-=9; l[2]=2;} }
//if (hub==2) cout<<l[0]<<' '<<l[1]<<' '<<l[2]<<endl;
int indx=2;
for (int j=min(i,n-1);j>=i-2;j--) {
if (done[j][par[j]]) continue;
done[j][par[j]]=true; done[par[j]][j]=true;
if (l[indx]==0) {
dis[j][par[j]]=0; dis[par[j]][j]=0;
}
else if (l[indx]==1) {
dis[par[j]][j]=1; dis[j][par[j]]=-1;
}
else {
dis[j][par[j]]=1; dis[par[j]][j]=-1;
}
//if (hub==1) cout<<j<<' '<<par[j]<<' '<<dis[j][par[j]]<<' '<<dis[par[j]][j]<<endl;
indx--;
}
ss="";
}
}
else {
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) dis[i][j]=1;
}
}
queue<int> q;
int ans[n+5];
bool vis[n+5];
memset(vis,false,sizeof vis);
ans[hub]=0; q.push(hub); vis[hub]=true;
while (!q.empty()) {
int i=q.front();
q.pop();
hops(hub,i,ans[i]);
for (int j:v[i]) {
if (!vis[j]) {
q.push(j); ans[j]=ans[i]+dis[i][j]; vis[j]=true;
}
}
}
}
}