Submission #1298359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298359		denislav	Saveit (IOI10_saveit)	C++20	100 / 100	47 ms	5952 KiB

encoder

#include "grader.h"
#include "encoder.h"
# include <iostream>
# include <vector>
# include <algorithm>
# include <queue>
using namespace std;

const int MAX=1e3+11,INF=1e9;
const int B=10,K=58;

int n,m,H;
vector<int> adj[MAX];
int dist[MAX][MAX];
int up[MAX];

void bfs(int start)
{
    for(int i=0;i<n;i++)
    {
        dist[start][i]=INF;
        up[i]=-1;
    }

    dist[start][start]=0;
    up[start]=-1;
    queue<int> q;
    q.push(start);
    while(q.size()>0)
    {
        int curr=q.front();
        q.pop();
        for(int nxt: adj[curr])
        {
            if(dist[start][nxt]>dist[start][curr]+1)
            {
                dist[start][nxt]=dist[start][curr]+1;
                up[nxt]=curr;
                q.push(nxt);
            }
        }
    }
}

void encode_num(long long x, int cnt)
{
    vector<int> v;
    for(int i=0;i<cnt;i++)
    {
        v.push_back(x%2);
        x/=2;
    }
    reverse(v.begin(),v.end());
    for(int b: v) encode_bit(b);
}

void reset()
{
    for(int i=0;i<n;i++)
    {
        adj[i].clear();
    }
}

void encode(int N, int _H, int P, int *a, int *b)
{
    n=N;m=P;H=_H;
    reset();
    for(int i=0;i<m;i++)
    {
        int u=a[i],v=b[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=0;i<H;i++) bfs(i);
    bfs(0);

    for(int i=1;i<n;i++) encode_num(up[i],B);
    for(int i=0;i<H;i++) encode_num(dist[i][0],B);
    for(int i=1;i<n;i++)
    {
        long long x=0;
        for(int j=H-1;j>=0;j--)
        {
            x*=3;
            long long delta=dist[j][i]-dist[j][up[i]]+1;
            x+=delta;
        }
        encode_num(x,K);
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <iostream>
#include <vector>
# include <algorithm>
using namespace std;

//namespace nz
//{
const int MAX=1e3+11;
const int B=10,K=58;

int n,H;
vector<int> adj[MAX];
int dist[MAX][MAX];

long long decode_num(int cnt)
{
    long long x=0;
    for(int i=0;i<cnt;i++)
    {
        x*=2;
        x+=decode_bit();
    }
    return x;
}

void dfs(int curr, int par)
{
    if(par!=-1)
    {
        for(int j=0;j<H;j++) dist[j][curr]+=dist[j][par];
    }
    for(int j=0;j<H;j++) hops(j,curr,dist[j][curr]);

    for(int nxt: adj[curr]) dfs(nxt,curr);
}

void reset()
{
    for(int i=0;i<n;i++)
    {
        adj[i].clear();
        for(int j=0;j<H;j++) dist[j][i]=0;
    }
}

void decode(int _n, int _H)
{
    n=_n;H=_H;
    reset();
    for(int i=1;i<n;i++)
    {
        int x=decode_num(B);
        adj[x].push_back(i);
    }
    for(int i=0;i<H;i++) dist[i][0]=decode_num(B);

    for(int i=1;i<n;i++)
    {
        long long x=decode_num(K);
        for(int j=0;j<H;j++)
        {
            long long delta=x%3-1;
            x/=3;
            dist[j][i]=delta;
        }
    }

    dfs(0,-1);
}

//}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25