Submission #274948

#	Time	Username	Problem	Language	Result	Execution time	Memory
274948		TMJN	Saveit (IOI10_saveit)	C++17	50 / 100	646 ms	19248 KiB

encoder

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

static int d[1000][36];
static bool b[1000][36];
static vector<int>v[1000];

static void bfs(int x){
	b[x][x]=true;
	queue<int>q;
	int dis=0;
	q.push(x);
	q.push(-1);
	while(q.size()>=2){
		int t=q.front();
		q.pop();
		if(t==-1){
			dis++;
			q.push(-1);
			continue;
		}
		if(d[t][x]==-1){
			d[t][x]=dis;
			for(int i:v[t]){
				q.push(i);
			}
		}
	}
}


static void send1(int x){
	for(int i=9;i>=0;i--){
		encode_bit((x>>i)&1);
	}
}

static void send0(int x){
	if(x==0){
		encode_bit(1);
	}
	else{
		encode_bit(0);
		send1(x);
	}
}

void encode(int N, int H, int P, int *A, int *B){
	for(int i=0;i<N;i++){
		for(int j=0;j<H;j++){
			d[i][j]=-1;
			b[i][j]=false;
		}
	}
	for(int i=0;i<P;i++){
		if(A[i]>B[i])swap(A[i],B[i]);
		v[A[i]].push_back(B[i]);
		v[B[i]].push_back(A[i]);
	}
	for(int i=0;i<H;i++){
		bfs(i);
	}
	vector<int>r[1000];
	priority_queue<pair<int,pair<int,int>>>pq;
	for(int i=0;i<P;i++){
		int c=0;
		for(int j=0;j<H;j++){
			if(d[A[i]][j]!=d[B[i]][j])c++;
		}
		pq.push({c,{A[i],B[i]}});
	}
	while(!pq.empty()){
		auto pp=pq.top();
		pq.pop();
		bool f=false;
		for(int i=0;i<H;i++){
			if((d[pp.second.first][i]<d[pp.second.second][i]&&!b[pp.second.second][i])||(d[pp.second.second][i]<d[pp.second.first][i]&&!b[pp.second.first][i])){
				f=true;
				break;
			}
		}
		if(f){
			r[pp.second.first].push_back(pp.second.second);
			for(int i=0;i<H;i++){
				if(d[pp.second.first][i]<d[pp.second.second][i]){
					b[pp.second.second][i]=true;
				}
				if(d[pp.second.second][i]<d[pp.second.first][i]){
					b[pp.second.first][i]=true;
				}
			}
			
		}
	}
	for(int i=0;i<N;i++){
		send0(r[i].size());
		for(int j:r[i]){
			send1(j);
		}
	}
	return;
}

decoder

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

static vector<int>v[1000];
static int d[1000][36];


int read1(){
	int t=0;
	for(int i=9;i>=0;i--){
		if(decode_bit()){
			t+=(1<<i);
		}
	}
	return t;
}

int read0(){
	int t=decode_bit();
	if(!t){
		return read1();
	}
	else return 0;
}

static void bfs(int x){
	queue<int>q;
	int dis=0;
	q.push(x);
	q.push(-1);
	while(q.size()>=2){
		int t=q.front();
		q.pop();
		if(t==-1){
			dis++;
			q.push(-1);
			continue;
		}
		if(d[t][x]==-1){
			d[t][x]=dis;
			for(int i:v[t]){
				q.push(i);
			}
		}
	}
}

void decode(int N, int H) {
	for(int i=0;i<N;i++){
		int t=read0();
		for(int j=0;j<t;j++){
			int k=read1();
			v[i].push_back(k);
			v[k].push_back(i);
		}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<H;j++){
			d[i][j]=-1;
		}
	}
	for(int i=0;i<H;i++){
		bfs(i);
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<H;j++){
			hops(j,i,d[i][j]);
		}
	}
}

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