제출 #1177305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177305		simona1230	Saveit (IOI10_saveit)	C++20	0 / 100	403 ms	10020 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 send2(int x)
{
    for(int i=0;i<2;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);

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

decoder

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

int _d[1024][38];
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];
        if(nb<hhh)_d[0][nb]=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=0;k<hhh;k++)
            _d[nb][k]+=f[nb][k];
    }
}

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

    for(int i=1;i<nv;i++)
    {
        for(int j=0;j<nh;j++)
        {
            int a=decode_bit();
            int b=decode_bit();
            if(a==0&&b==0)f[i][j]=0;
            else if(a==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++)
        {
            hops(j,i,_d[i][j]);
        }
    }
}

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