제출 #785850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785850		PoonYaPat	저장 (Saveit) (IOI10_saveit)	C++14	100 / 100	151 ms	12700 KiB

encoder

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

vector<int> adj[1005];
int n,h,p[1005],dis[1005][36];
bool vis[1005];

void dfs(int x, int par) {
  p[x]=par;
  vis[x]=true;
  for (auto s : adj[x]) if (!vis[s]) dfs(s,x);
}

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

  dfs(0,0);
  for (int i=1; i<n; ++i) {
    for (int j=0; j<10; ++j) {
      if (p[i]&(1<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }

  vector<int> v;
  memset(dis,-1,sizeof(dis));
  for (int i=0; i<h; ++i) {
    dis[i][i]=0;
    queue<int> q;
    q.push(i);

    while (!q.empty()) {
      int node=q.front();
      q.pop();
      for (auto s : adj[node]) {
        if (dis[s][i]==-1) {
          dis[s][i]=dis[node][i]+1;
          q.push(s);
        }
      }
    }

    for (int j=1; j<n; ++j) v.push_back(dis[p[j]][i]-dis[j][i]+1);
  }

  while (v.size()%3) v.push_back(0);

  for (int i=0; i<v.size(); i+=3) {
    int sum=v[i]+3*v[i+1]+9*v[i+2];
    for (int j=0; j<5; ++j) {
      if (sum&(1<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int nn,hh,pp[1005];
vector<int> v;
vector<pii> adjj[1005][36];

void dfs(int x, int par, int val, int gr) {
   hops(gr,x,val);
   for (auto s : adjj[x][gr]) {
      if (s.first!=par) dfs(s.first,x,val+s.second,gr); 
   }
}

void decode(int nv, int nh) {
   nn=nv; hh=nh;
   for (int i=1; i<nn; ++i) {
      int sum=0;
      for (int j=0; j<10; ++j) {
         if (decode_bit()==1) sum+=(1<<j);
      }
      pp[i]=sum;
   }

   for (int i=0; i<((nn-1)*hh+2)/3; ++i) {
      int sum=0;
      for (int j=0; j<5; ++j) if (decode_bit()==1) sum+=(1<<j);
      v.push_back(sum%3-1); sum/=3;
      v.push_back(sum%3-1); sum/=3;
      v.push_back(sum%3-1);
   }

   int idx=0;
   for (int i=0; i<hh; ++i) {
      for (int j=1; j<nn; ++j) {
         adjj[j][i].push_back({pp[j],v[idx]});
         adjj[pp[j]][i].push_back({j,-v[idx]});
         ++idx;
      }
   }

   for (int i=0; i<hh; ++i) dfs(i,i,0,i);
}

컴파일 시 표준 에러 (stderr) 메시지

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i=0; i<v.size(); i+=3) {
      |                 ~^~~~~~~~~

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