Submission #506200

#	Time	Username	Problem	Language	Result	Execution time	Memory
506200		jerzyk	Saveit (IOI10_saveit)	C++17	0 / 100	267 ms	10696 KiB

encoder

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

typedef long long ll;
using namespace std;
const int N = 1000 + 7;
vector<int>ed[N];
int tab[38][1000 + 7], wsk[N];

ll Return3(int v, int h)
{
    ll w = 0LL, m;
    for(int i = 1; i <= h; ++i)
    {
        m = 0LL;
        if(tab[i][v] == tab[i][wsk[i]])
            m = 1;
        if(tab[i][v] > tab[i][wsk[i]])
            m = 2;
        w += m * pow(3LL, (ll)i - 1);
    }
    return w;
}

void PrintBits(ll x, int l)
{
    for(int i = 1; i <= l; ++i)
    {
        encode_bit(x % 2LL);
        x /= 2LL;
    }
}

void DFS(int v)
{
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(wsk[ed[v][i]] == 0)
        {
            wsk[ed[v][i]] = v;
            DFS(ed[v][i]);
        }
    }
}

void BFS(int n, int s)
{
    int v;
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        tab[s][i] = N * 2;
    tab[s][s] = 0;
    q.push(s);
    while(q.size() > 0)
    {
        v = q.front();
        q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(tab[s][ed[v][i]] > tab[s][v] + 1)
            {
                tab[s][ed[v][i]] = tab[s][v] + 1;
                q.push(ed[v][i]);
            }
        }
    }
}

void encode(int n, int h, int m, int* a, int* b)
{
    for(int i = 0; i < m; ++i)
    {
        ed[a[i] + 1].push_back(b[i] + 1);
        ed[b[i] + 1].push_back(a[i] + 1);
    }
    for(int i = 1; i <= h; ++i)
        BFS(n, i);
    wsk[1] = 1;
    DFS(1);
    for(int i = 2; i <= h; ++i)
        PrintBits(tab[i][1], 10);
    for(int i = 2; i <= n; ++i)
    {
        PrintBits(wsk[i], 10);       
        PrintBits(Return3(i, h), 58);
    }
}

decoder

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

using namespace std;
typedef long long ll;
const int N = 1000 + 7;
int odl[37][N], dod[37][N], wsk[N];
vector<int>ed[N];

void DFS(int v, int h)
{
    for(int i = 1; i <= h; ++i)
        odl[i][v] = dod[i][v] + odl[i][wsk[v]];
    for(int i = 0; i < (int)ed[v].size(); ++i)
        DFS(ed[v][i], h);
}

void Dod(ll l, int v, int h)
{
    for(int i = 1; i <= h; ++i)
    {
        if(l % 3LL == 0)
            dod[i][v] = -1;
        if(l % 3LL == 2)
            dod[i][v] = 1;
        l /= 3;
    }
}

ll ReadBits(int n)
{
    int b;
    ll w = 0LL;
    for(int i = 0; i < n; ++i)
    {
        b = decode_bit();
        w += pow(2LL, (ll)i) * b;
    }
    return w;
}

void decode(int n, int h)
{
    for(int i = 2; i <= h; ++i)
        odl[i][1] = ReadBits(10);
    for(int i = 2; i <= n; ++i)
    {
        wsk[i] = ReadBits(10);
        ed[wsk[i]].push_back(i);
        Dod(ReadBits(58), i, h);
    }
    DFS(1, h);
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= n; ++j)
            hops(i - 1, j - 1, odl[i][j]);
}

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