Submission #15623

#	Time	Username	Problem	Language	Result	Execution time	Memory
15623		gs14004	Saveit (IOI10_saveit)	C++14	50 / 100	184 ms	11808 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int dist[36][1005];
vector<int> graph[1005];

bool vis[1005];
int par[1005];
queue<int> q;

void bfs(int* dist, int st){
    memset(vis,0,sizeof(vis));
    q.push(st);
    vis[st] = 1;
    while(!q.empty()){
        int qf = q.front();
        q.pop();
        for(auto &i : graph[qf]){
            if(vis[i]) continue;
            vis[i] = 1;
            dist[i] = dist[qf] + 1;
            par[i] = qf;
            q.push(i);
        }
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    for(int i=0; i<ne; i++){
        graph[v1[i]].push_back(v2[i]);
        graph[v2[i]].push_back(v1[i]);
    }
    for(int i=nh-1; i>=0; i--){
        bfs(dist[i],i);
    }
    for(int i=1; i<nv; i++){
        for(int j=0; j<10; j++){
            encode_bit((par[i] >> j) & 1);
        }
    }
    for(int i=0; i<nh; i++){
        for(int j=1; j<nv; j++){
            int diff = dist[i][j] - dist[i][par[j]];
            if(diff == -1){
                encode_bit(1);
                encode_bit(1);
            }
            else if(diff == 0){
                encode_bit(0);
                encode_bit(0);
            }
            else{
                encode_bit(0);
                encode_bit(1);
            }
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector<int> tree[1005];

int dx[1005];

void dfs(int x, int pa){
	for(auto &i : tree[x]){
		dx[i] += dx[x];
		dfs(i, x);
	}
}

void decode(int nv, int nh){
	for(int i=1; i<nv; i++){
		int r = 0;
		for(int j=0; j<10; j++){
			r |= (decode_bit() << j);
		}
		tree[r].push_back(i);
	}
	for(int i=0; i<nh; i++){
		for(int j=1; j<nv; j++){
			int t = decode_bit() << 1;
			t += decode_bit();
			if(t == 3) t = -1;
			dx[j] = t;
		}
		dfs(0,0);
		for(int j=0; j<nv; j++){
			hops(i,j,dx[j] - dx[i]);
		}
	}
}

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