| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 941228 |
2024-03-08T10:45:31 Z |
ibm2006 |
Saveit (IOI10_saveit) |
C++17 |
|
0 ms |
0 KB |
#include"encoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],h[1100000],dp[1100000],par[1100000],m,c[1100000],ii;
queue<ll> q;
vector<ll> v[1100000];
void f(ll x,ll y)
{
c[x]=1;
par[x]=y;
ll i;
for(i=0;i<h[x];i++)
{
if(c[v[x][i]]==0)
{
f(v[x][i],x);
}
}
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
n=nv;
k=nh;
m=ne;
for(i=0;i<m;i++)
{
x=v1[i];
y=v2[i];
v[x].push_back(y);
v[y].push_back(x);
h[y]++;
h[x]++;
}
f(0,0);
for(i=0;i<n;i++)
{
x=par[i];
for(j=0;j<10;j++)
{
encode_bit(x&1);
x/=2;
}
}
for(i=0;i<k;i++)
{
for(j=0;j<n;j++)
{dp[j]=1000000;
c[j]=0;
}
dp[i]=0;
q.push(i);
c[i]=1;
while(!q.empty())
{
x=q.front();
q.pop();
for(j=0;j<h[x];j++)
{
if(c[v[x][j]]==0)
{
c[v[x][j]]=1;
dp[v[x][j]]=dp[x]+1;
q.push(v[x][j]);
}
}
}
for(ii=1;ii<n;ii++)
{
b[ii]=dp[ii]-dp[par[ii]]+1;
}
/*for(ii=0;ii<n;ii++)
printf("%d ",dp[ii]);
printf("\n");*/
for(ii=0;ii<n;ii+=5)
{
x=b[ii]*81+b[ii+1]*27+b[ii+2]*9+b[ii+3]*3+b[ii+4];
for(j=0;j<8;j++)
{
encode_bit(x&1);
x/=2;
}
}
}
}
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],h[1100000],dp[1100000],par[1100000],m,c[1100000],ii;
queue<ll> q;
vector<ll> v[1100000];
void g(ll x,ll y)
{
ll i;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
b[v[x][i]]+=b[x];
g(v[x][i],x);
}
}
void decode(int nv, int nh) {
n=nv;
for(i=0;i<n;i++)
{
h[i]=0;
v[i].clear();
}
k=nh;
for(i=0;i<n;i++)
{
y=0;
x=1;
for(j=0;j<10;j++)
{
y=y+x*decode_bit();
x*=2;
}
if(i>0)
{par[i]=y;
v[i].push_back(y);
v[y].push_back(i);
h[i]++;
h[y]++;}
}
par[0]=0;
//printf("!");
/*for(i=0;i<n;i++)
printf("%d ",par[i]);
printf("\n");*/
//for(i=0;i<n;i++)
for(j=0;j<k;j++)
{
for(i=0;i<n;i+=5)
{
x=0;
y=1;
for(l=0;l<8;l++)
{
x=x+y*decode_bit();
y*=2;
}
b[i+4]=x%3;
x/=3;
b[i+3]=x%3;
x/=3;
b[i+2]=x%3;
x/=3;
b[i+1]=x%3;
x/=3;
b[i]=3;
b[i]--;
b[i+1]--;
b[i+2]--;
b[i+3]--;
b[i+4]--;
}
/*for(i=0;i<n;i++)
printf("%d ",b[i]);
printf("\n");*/
g(0,0);
x=-b[j];
for(i=0;i<n;i++)
b[i]+=x;
/*for(i=0;i<n;i++)
printf("%d ",b[i]);
printf("\n");*/
for(i=0;i<n;i++)
hops(j,i,b[i]);
}
}
Compilation message
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:40:13: error: 'encode_bit' was not declared in this scope; did you mean 'encode'?
40 | encode_bit(x&1);
| ^~~~~~~~~~
| encode
encoder.cpp:79:17: error: 'encode_bit' was not declared in this scope; did you mean 'encode'?
79 | encode_bit(x&1);
| ^~~~~~~~~~
| encode
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:33:19: error: 'decode_bit' was not declared in this scope; did you mean 'femode_t'?
33 | y=y+x*decode_bit();
| ^~~~~~~~~~
| femode_t
decoder.cpp:57:23: error: 'decode_bit' was not declared in this scope; did you mean 'femode_t'?
57 | x=x+y*decode_bit();
| ^~~~~~~~~~
| femode_t
decoder.cpp:86:13: error: 'hops' was not declared in this scope
86 | hops(j,i,b[i]);
| ^~~~
