Submission #895735

#	Time	Username	Problem	Language	Result	Execution time	Memory
895735		abcvuitunggio	Saveit (IOI10_saveit)	C++17	100 / 100	151 ms	16700 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
static vector <int> ke[1000];
static int p[1000],vis[1000],d[1000];
static void dfs(int u){
    vis[u]=1;
    for (int v:ke[u])
        if (!vis[v]){
            p[v]=u;
            dfs(v);
        }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
    for (int i=0;i<ne;i++){
        ke[v1[i]].push_back(v2[i]);
        ke[v2[i]].push_back(v1[i]);
    }
    dfs(0);
    for (int i=1;i<nv;i++)
        for (int j=9;j>=0;j--)
            encode_bit((p[i]>>j)&1);
    queue <int> q;
    for (int i=0;i<nh;i++){
        fill(d,d+nv,-1);
        q.push(i);
        d[i]=0;
        while (!q.empty()){
            int u=q.front();
            q.pop();
            for (int v:ke[u])
                if (d[v]==-1){
                    d[v]=d[u]+1;
                    q.push(v);
                }
        }
        for (int j=0;j*10<nv;j++){
            int val=0;
            for (int k=min(j*10+9,nv-1);k>=j*10;k--)
                val=val*3+d[k]-d[p[k]]+1;
            for (int j=15;j>=0;j--)
                encode_bit((val>>j)&1);
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
static int p[1000],d[1000];
static vector <int> ke[1000];
static int get(int i){
    int val=0;
    while (i--)
        val=val*2+decode_bit();
    return val;
}
static void dfs(int u, int par, int hub, int dist){
    hops(hub,u,dist);
    for (int v:ke[u])
        if (v!=par)
            dfs(v,u,hub,dist+d[v]);
    if (u&&p[u]!=par)
        dfs(p[u],u,hub,dist-d[u]);
}
void decode(int nv, int nh){
    for (int i=1;i<nv;i++){
        p[i]=get(10);
        ke[p[i]].push_back(i);
    }
    for (int i=0;i<nh;i++){
        for (int j=0;j*10<nv;j++){
            int val=get(16);
            for (int k=j*10;k<min(j*10+10,nv);k++,val/=3)
                d[k]=val%3-1;
        }
        dfs(i,i,i,0);
    }
}

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