Submission #266401

#	Time	Username	Problem	Language	Result	Execution time	Memory
266401		Alexa2001	Saveit (IOI10_saveit)	C++17	0 / 100	240 ms	12016 KiB

encoder

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

using namespace std;

vector<vector<int>> v;
vector<int> t;
vector<bool> used;

int n;


void bfs(int node, vector<int> &dist)
{
    dist.resize(n, 1e9);
    dist[node] = 0;

    queue<int> q;
    q.push(node);

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : v[node])
            if(dist[node] + 1 < dist[it])
            {
                dist[it] = dist[node] + 1;
                q.push(it);
            }
    }
}

void dfs(int node)
{
    used[node] = 1;

    for(auto it : v[node])
        if(!used[it])
        {
            t[it] = node;
            dfs(it);
        }
}

void print(int x)
{
    if(x == 0) encode_bit(0);
        else if(x == 1) encode_bit(1), encode_bit(0);
            else if(x == 2) encode_bit(1), encode_bit(1);
                else assert(0);
}

void encode(int N, int H, int P, int *v1, int *v2)
{
    vector<vector<int>> dist(H);

    n = N;
    v.resize(n);

    int i, j;
    for(i=0; i<P; ++i)
    {
        v[v1[i]].push_back(v2[i]);
        v[v2[i]].push_back(v1[i]);
    }

    for(i=0; i<H; ++i)
        bfs(i, dist[i]);

    used.resize(n, 0);
    t.resize(n);
    dfs(0);

    for(i=1; i<n; ++i)
    {
        int b = 10;
        while(b--)
            encode_bit((t[i] >> b) & 1);
    }

    for(i=0; i<H; ++i)
        for(j=9; j>=0; --j)
            encode_bit((dist[i][0]>>j) & 1);

    vector<vector<int>> tip(n);
    for(auto &it : tip) it.resize(H);
    map<int, int> cnt;

    for(i=1; i<n; ++i)
        for(j=0; j<H; ++j)
        {
            tip[i][j] = dist[j][i] - dist[j][t[i]];
            ++cnt[tip[i][j]];
        }

    if(cnt[-1] >= cnt[0] && cnt[-1] >= cnt[1]) cnt[-1] = 0, cnt[0] = 1, cnt[1] = 2;
        else if(cnt[0] >= cnt[-1] && cnt[0] >= cnt[1]) cnt[0] = 0, cnt[-1] = 1, cnt[1] = 2;
            else cnt[1] = 0, cnt[0] = 1, cnt[-1] = 2;

    print(cnt[-1]);
    print(cnt[0]);
    print(cnt[1]);

    for(i=1; i<n; ++i)
        for(j=0; j<H; ++j)
            print(cnt[tip[i][j]]);
}

decoder

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

using namespace std;

void read(int &x)
{
    if(decode_bit() == 0) x = 0;
        else if(decode_bit() == 0) x = 1;
            else x = 2;
}

void decode(int n, int h)
{
    int i, j;
    vector<bool> marked(n, 0);
    vector<int> t(n);

    for(i=1; i<n; ++i)
    {
        int b = 10;
        int x = 0;
        while(b--)
            x = x * 2 + decode_bit();
        t[i] = x;
    }

    vector<vector<int>> dist(h);
    for(auto &it : dist) it.resize(n);

    for(i=0; i<h; ++i)
    {
        int x = 0;
        for(j=0; j<10; ++j)
            x = x * 2 + decode_bit();
        dist[i][0] = x;
    }

    map<int, int> cnt;

    read(cnt[-1]);
    read(cnt[0]);
    read(cnt[1]);

    for(i=1; i<n; ++i)
        for(j=0; j<h; ++j)
        {
            int x;
            read(x);

            for(int k=-1; k<=1; ++k)
                if(cnt[k] == x)
                    dist[j][i] = dist[j][t[i]] + k;
        }

    for(i=0; i<n; ++i)
        for(j=0; j<h; ++j)
            hops(j, i, dist[j][i]);
}

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