제출 #1177354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177354		simona1230	저장 (Saveit) (IOI10_saveit)	C++20	100 / 100	512 ms	9860 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;

int d[1024][1024];
int used[1024],p[1024];

int nn,hh;
vector<int> v[1024];

void send(int x)
{
    for(int i=0;i<10;i++)
        if((1<<i)&x)encode_bit(1);
        else encode_bit(0);
}

void send5(int x)
{
    for(int i=0;i<5;i++)
        if((1<<i)&x)encode_bit(1);
        else encode_bit(0);
}

void bfs(int s)
{
    for(int i=0;i<nn;i++)
        used[i]=0;

    queue<int> q;
    q.push(s);
    used[s]=1;

    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<v[x].size();i++)
        {
            int nb=v[x][i];
            if(!used[nb])
            {
                if(s==0)p[nb]=x;
                used[nb]=1;
                q.push(nb);
                d[s][nb]=d[s][x]+1;
            }
        }
    }

    if(s==0)
    {
        for(int i=1;i<nn;i++)
            send(p[i]);
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2)
{
    nn=nv;
    hh=nh;
    for(int i=0;i<ne;i++)
    {
        v[v1[i]].push_back(v2[i]);
        v[v2[i]].push_back(v1[i]);
    }

    for(int i=0;i<nn;i++)
        bfs(i);

    string s="";
    for(int i=1;i<nn;i++)
    {
        for(int j=1;j<nh;j++)
        {
            if(d[i][j]==d[p[i]][j])s+='0';
            else if(d[i][j]==d[p[i]][j]+1)s+='1';
            else s+='2';
        }
    }

    map<string,int> mp;
    int id=0;
    for(int i=0;i<=2;i++)
    {
        for(int j=0;j<=2;j++)
        {
            for(int k=0;k<=2;k++)
            {
                string c="";
                c+=(i+'0');
                c+=(j+'0');
                c+=(k+'0');
                mp[c]=id++;
            }
        }
    }

    if(s.size()%3==1)s+="00";
    else if(s.size()%3==2)s+='0';

    for(int i=0;i<s.size();i+=3)
    {
        string c="";
        c+=s[i];
        c+=s[i+1];
        c+=s[i+2];
        send5(mp[c]);
    }
    //cout<<"end"<<endl;
}

decoder

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;

int _d[1024][1024];
int f[1024][38];
int hhh;
vector<int> _v[1024];

void dfs(int i,int x)
{
    for(int j=0;j<_v[i].size();j++)
    {
        int nb=_v[i][j];
        _d[0][nb]=x,_d[nb][0]=x;
        dfs(nb,x+1);
    }
}

void dfs1(int i)
{

    for(int j=0;j<_v[i].size();j++)
    {
        int nb=_v[i][j];
        for(int k=1;k<hhh;k++)
            _d[nb][k]=_d[i][k]+f[nb][k];
            dfs1(nb);
    }
}

void decode(int nv, int nh)
{
    hhh=nh;
    for(int i=1;i<nv;i++)
    {
        int curr=0;
        for(int j=0;j<10;j++)
        {
            int b=decode_bit();
            if(b)curr+=(1<<j);
        }
        _v[curr].push_back(i);
    }
    dfs(0,1);

    map<int,string> mp;
    int id=0;
    for(int i=0;i<=2;i++)
    {
        for(int j=0;j<=2;j++)
        {
            for(int k=0;k<=2;k++)
            {
                string c="";
                c+=(i+'0');
                c+=(j+'0');
                c+=(k+'0');
                mp[id++]=c;
            }
        }
    }
    int len=(nv-1)*(nh-1);
    int nb=len/3;
    if(len%3!=0)nb++;
    //cout<<nv<<" "<<nh<<endl;
    len=nb*5;

    string s="";
    for(int i=0;i<len;i+=5)
    {
        int y=0;
        for(int j=0;j<5;j++)
        {
            int x=decode_bit();
            //cout<<x;
            if(x)y+=(1<<j);
        }

        s+=mp[y];
    }
    id=0;

    for(int i=1;i<nv;i++)
    {
        for(int j=1;j<nh;j++)
        {
            int x=s[id++]-'0';
            if(x==0)f[i][j]=0;
            else if(x==1)f[i][j]=1;
            else f[i][j]=-1;
        }
    }

    dfs1(0);

    for(int i=0;i<nv;i++)
    {
        for(int j=0;j<nh;j++)
        {
            ///cout<<i<<" - "<<j<<" "<<_d[i][j]<<endl;
            hops(j,i,_d[i][j]);
        }
    }
    //cout<<"end"<<endl;
}

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