제출 #1019140

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

encoder

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

namespace {

const int maxn = 1e3+5;

int E[maxn][maxn];
int dist[maxn][maxn];
int change[maxn][maxn];
int vis[maxn], par[maxn];

void dfs(int x, int nv, int nh){
	vis[x] = 1;
	for(int i = 0; i < nv; i++){
		if(!E[x][i] || vis[i])continue;
		par[i] = x;
		dfs(i, nv, nh);
	}
}

void sendnum(int x, int cnt){
	while(cnt--){
		encode_bit(x&1);
		x>>=1;
	}
}

}


void encode(int nv, int nh, int ne, int *v1, int *v2){
	memset(E, 0, sizeof(E));
	memset(dist, 0, sizeof(dist));
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < ne; i++)E[v1[i]][v2[i]] = E[v2[i]][v1[i]] = 1;
	for(int i = 0; i < nh; i++){
		dist[i][i] = 0;
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			auto x = q.front();
			q.pop();
			for(int j = 0; j < nv; j++){
				if(!E[x][j] || dist[i][j] || j == i)continue;
				dist[i][j] = dist[i][x] + 1;
				q.push(j);
			}
		}
	}
	dfs(0, nv, nh);
	for(int i = 1; i < nv; i++){
		sendnum(par[i], 10);
		for(int j = 0; j < nh; j+=3){
			int sum = 0;
			for(int k = j; k < j+3 && k < nh; k++){
				sum = sum*3;
				sum += dist[k][i] - dist[k][par[i]] + 1;
			}
			sendnum(sum, 5);
		}
	}
}

decoder

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

namespace {

const int maxn = 1e3+5;

int dist[maxn][maxn];
int change[maxn][60];

vector<int> g[maxn];

int readnum(int cnt){
	int re = 0;
	for(int i = 0; i < cnt; i++){
		re += decode_bit()<<i;
	}
	return re;
}

void dfs(int x, int nh){
	for(auto v: g[x]){
		for(int i = 0; i < nh; i++){
			change[v][i] += change[x][i];
		}
		dfs(v, nh);
	}
}

}

void decode(int nv, int nh) {
   	for(int i = 1; i < nv; i++){
		g[readnum(10)].push_back(i);
		for(int j = 0; j < nh; j+=3){
			int sum = readnum(5);
			for(int k = min(j+2, nh-1); k >= j; k--){
				change[i][k] = sum%3 - 1;
				sum/=3;
			}
		}
	}
	dfs(0, nh);
	for(int i = 0; i < nh; i++){
		for(int j = 0; j < nv; j++){
			hops(i, j, change[j][i] + change[i][0]);
		}
	}
}

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

encoder.cpp:12:5: warning: '{anonymous}::change' defined but not used [-Wunused-variable]
   12 | int change[maxn][maxn];
      |     ^~~~~~

decoder.cpp:10:5: warning: '{anonymous}::dist' defined but not used [-Wunused-variable]
   10 | int dist[maxn][maxn];
      |     ^~~~

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