Submission #254279

#	Time	Username	Problem	Language	Result	Execution time	Memory
254279		MKopchev	Saveit (IOI10_saveit)	C++14	0 / 100	515 ms	19088 KiB

encoder

#include "grader.h"
#include "encoder.h"

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e3+42;

queue< pair<int/*parent*/,int/*node*/> > q,idle;
int parent[nmax],dist[nmax];
vector< int > adj[nmax];

int PARENT[nmax];

void dfs(int node,int par)
{
    PARENT[node]=par;

    for(auto k:adj[node])
        if(k!=par)
            dfs(k,node);
}

int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}
void encode(int nv, int nh, int ne, int *v1, int *v2){

    for(int i=0;i<nv;i++)parent[i]=i;

    for(int i=0;i<ne;i++)
    {
        int p=v1[i],q=v2[i];

        if(root(p)==root(q))continue;

        parent[root(p)]=root(q);

        adj[p].push_back(q);
        adj[q].push_back(p);

        //cout<<"adj "<<p<<" "<<q<<endl;
    }

    dfs(0,0);

    //for(int i=0;i<nv;i++)cout<<PARENT[i]<<" ";cout<<endl;

    for(int i=0;i<nv;i++)adj[i]={};

    for(int i=0;i<ne;i++)
    {
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }

    for(int i=0;i<nv;i++)
    {
        for(int j=9;j>=0;j--)
            if((PARENT[i]&(1<<j)))encode_bit(1);
            else encode_bit(0);
    }

    int hsh=0,in=0;

    for(int i=0;i<nh;i++)
    {
        for(int j=0;j<nv;j++)parent[j]=-1,dist[j]=-1;
        q=idle;
        q.push({-1,i});
        while(q.size())
        {
            pair<int/*parent*/,int/*node*/> now=q.front();
            q.pop();
            if(dist[now.second]!=-1)continue;
            if(now.first==-1)
            {
                dist[now.second]=0;
                parent[now.second]=-1;
            }
            else
            {
                dist[now.second]=dist[now.first]+1;
                parent[now.second]=now.first;
            }
            for(auto k:adj[now.second])
                q.push({now.second,k});
        }
        /*
        cout<<endl;
        cout<<i<<" -> ";for(int j=0;j<nv;j++)cout<<dist[j]<<" ";cout<<endl;
        */
        for(int k=0;k<nv;k++)
        {
            int delta=dist[k]-dist[PARENT[k]]+1;

            in++;

            hsh=hsh*3+delta;

            if(in==3)
            {
                in=0;
                for(int t=4;t>=0;t--)
                    if((hsh&(1<<t)))encode_bit(1);
                    else encode_bit(0);

                hsh=0;
            }
        }
    }

    if(in==0)return;

    while(in%3)
    {
        in++;
        hsh=hsh*3;
    }

    for(int t=4;t>=0;t--)
        if((hsh&(1<<t)))encode_bit(1);
        else encode_bit(0);
}

decoder

#include "grader.h"
#include "decoder.h"

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e3+42;


vector<int> other_adj[nmax];
int par_decode[nmax];

int DIFF[nmax*50];

int actual[nmax];

void dfs_decode(int node,int par,int sum)
{
    sum+=DIFF[node];

    actual[node]=sum;

    for(auto k:other_adj[node])
        if(k!=par)
            dfs_decode(k,node,sum);
}

int HELP[nmax*nmax],pointer;

void decode(int nv, int nh) {
    for(int i=0;i<nv;i++)
    {
        int val=0;
        for(int j=0;j<=9;j++)
            val=val*2+decode_bit();

        par_decode[i]=val;

        //cout<<i<<" -> "<<val<<endl;

        if(i!=val)
        {
            other_adj[i].push_back(val);
            other_adj[val].push_back(i);
        }
    }

    for(int i=0;i<nh;i++)
    {
        //cout<<"i= "<<i<<endl;

        for(int j=0;j<nv;j++)
            if((i*nh+j)%3==0)
            {
                int arr[5];
                arr[0]=decode_bit();
                arr[1]=decode_bit();
                arr[2]=decode_bit();
                arr[3]=decode_bit();
                arr[4]=decode_bit();

                int num=arr[0]*16+arr[1]*8+arr[2]*4+arr[3]*2+arr[4];

                HELP[pointer]=num/9-1;
                HELP[pointer+1]=num%9/3-1;
                HELP[pointer+2]=num%3-1;

                pointer+=3;
            }

        for(int j=0;j<nv;j++)
            DIFF[j]=HELP[i*nv+j];

        dfs_decode(0,0,0);

        //for(int j=0;j<nv;j++)cout<<actual[j]<<" ";cout<<endl;

        for(int j=0;j<nv;j++)
        {
            int sum=actual[j]-actual[i];

            hops(i,j,sum);
        }
        //cout<<"---"<<endl;
    }
}

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