Submission #254276

#	Time	Username	Problem	Language	Result	Execution time	Memory
254276		MKopchev	Saveit (IOI10_saveit)	C++14	0 / 100	522 ms	19552 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<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);
    }

    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);
    }

    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]];
            if(delta==-1)
            {
                encode_bit(0);
                encode_bit(0);
            }
            else if(delta==0)
            {
                encode_bit(0);
                encode_bit(1);
            }
            else
            {
                encode_bit(1);
                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];

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);
}
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;

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

    for(int i=0;i<nh;i++)
    {
        for(int j=0;j<nv;j++)
        {
            int p=decode_bit();
            int q=decode_bit();

            DIFF[j]=2*p+q-1;
        }

        dfs_decode(0,0,0);

        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