Submission #894860

#	Time	Username	Problem	Language	Result	Execution time	Memory
894860		12345678	Saveit (IOI10_saveit)	C++17	100 / 100	135 ms	16444 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;
int n, hub, m, pa[nx], vs[nx], dp[nx], res[nx];
vector<int> d[nx], tree[nx];

void send_number(int x)
{
    for (int i=0; i<10; i++) encode_bit((x&(1<<i)?1:0));
}

void send_value(int x)
{
    for (int i=0; i<8; i++) encode_bit((x&(1<<i)?1:0));
}

void build()
{
    queue<int> q;
    q.push(0);
    vs[0]=1;
    while (!q.empty())
    {
        auto u=q.front();
        q.pop();
        for (auto v:d[u]) if (!vs[v]) pa[v]=u, q.push(v), vs[v]=1;
    }
    for (int i=1; i<n; i++) send_number(pa[i]);
    for (int i=1; i<n; i++) tree[pa[i]].push_back(i);
}

void dfsdp(int u)
{
    for (auto v:tree[u]) res[v]=dp[v]-dp[u], dfsdp(v);
}

void bfs(int x)
{
    for (int i=0; i<n; i++) dp[i]=-1;
    queue<int> q;
    q.push(x);
    dp[x]=0;
    while (!q.empty())
    {
        auto u=q.front();
        q.pop();
        for (auto v:d[u]) if (dp[v]==-1) dp[v]=dp[u]+1, q.push(v);
    }
    dfsdp(0);
    for (int i=1; i<=1000; i+=5) 
    {
        int tmp=0;
        for (int j=i+4; j>=i; j--) tmp=3*tmp+res[j]+1;
        //printf("%d %d %d\n", x, i, tmp);
        send_value(tmp);
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n=nv;
    hub=nh;
    m=ne;
    for (int i=0; i<m; i++) d[v1[i]].push_back(v2[i]), d[v2[i]].push_back(v1[i]);
    build();
    for (int i=1; i<hub; i++) bfs(i);
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

int N, H, vl[1005], ans[1005], mn;
vector<int> t[1005];

void dfsans(int u)
{
    for (auto v:t[u]) ans[v]=ans[u]+vl[v], dfsans(v);
    mn=min(mn, ans[u]);
}

void solve(int x)
{
    mn=INT_MAX;
    if (x==0) for (int i=1; i<N; i++) vl[i]=1;
    else
    {
        for (int i=1; i<=1000; i+=5)
        {
            int res=0;
            for (int k=0; k<8; k++) if (decode_bit()) res|=(1<<k);
            for (int j=i; j<i+5; j++) vl[j]=res%3-1, res/=3;
            //printf("read %d %d %d\n", x, i, vl[i]);
        }
    }
    ans[0]=0;
    dfsans(0);
    for (int i=0; i<N; i++) ans[i]=ans[i]-mn;
    //printf("min %d\n", mn);
    for (int i=0; i<N; i++) hops(x, i, ans[i]);
}

void decode(int nv, int nh) {
    N=nv;
    H=nh;
    for (int i=1; i<N; i++)
    {
        int res=0;
        for (int k=0; k<10; k++) if (decode_bit()) res|=(1<<k);
        t[res].push_back(i);
    }
    for (int i=0; i<H; i++) solve(i);
}

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