oj.uz

Submission #274948

# Submission time Handle Problem Language Result Execution time Memory
274948 2020-08-20T02:04:54 Z TMJN Saveit (IOI10_saveit) C++17
50 / 100
 646 ms 19248 KB 
#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;
}

#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 19248 KB Output is partially correct - 205440 call(s) of encode_bit()
2 Correct 3 ms 4736 KB Output is correct - 95 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 43280 call(s) of encode_bit()
4 Correct 4 ms 4896 KB Output is correct - 125 call(s) of encode_bit()
5 Correct 63 ms 6788 KB Output is partially correct - 89280 call(s) of encode_bit()
6 Correct 61 ms 6712 KB Output is partially correct - 91180 call(s) of encode_bit()
7 Correct 107 ms 8208 KB Output is partially correct - 168850 call(s) of encode_bit()
8 Correct 22 ms 5576 KB Output is correct - 26451 call(s) of encode_bit()
9 Correct 26 ms 5832 KB Output is correct - 24650 call(s) of encode_bit()
10 Correct 25 ms 5756 KB Output is correct - 24110 call(s) of encode_bit()
11 Correct 43 ms 6080 KB Output is correct - 41310 call(s) of encode_bit()
12 Correct 19 ms 5516 KB Output is correct - 17600 call(s) of encode_bit()
13 Correct 111 ms 7636 KB Output is partially correct - 110290 call(s) of encode_bit()
14 Correct 28 ms 5800 KB Output is correct - 28230 call(s) of encode_bit()
15 Correct 27 ms 5888 KB Output is correct - 29870 call(s) of encode_bit()
16 Correct 100 ms 6976 KB Output is correct - 56330 call(s) of encode_bit()
17 Correct 81 ms 6948 KB Output is correct - 52560 call(s) of encode_bit()
18 Correct 111 ms 7620 KB Output is partially correct - 76010 call(s) of encode_bit()
19 Correct 67 ms 6848 KB Output is partially correct - 74280 call(s) of encode_bit()
20 Correct 131 ms 8044 KB Output is partially correct - 96200 call(s) of encode_bit()
21 Correct 158 ms 8376 KB Output is partially correct - 96870 call(s) of encode_bit()
22 Correct 112 ms 7836 KB Output is partially correct - 136030 call(s) of encode_bit()
23 Correct 190 ms 9060 KB Output is partially correct - 126420 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 19248 KB Output is partially correct - 205440 call(s) of encode_bit()
2 Correct 3 ms 4736 KB Output is correct - 95 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 43280 call(s) of encode_bit()
4 Correct 4 ms 4896 KB Output is correct - 125 call(s) of encode_bit()
5 Correct 63 ms 6788 KB Output is partially correct - 89280 call(s) of encode_bit()
6 Correct 61 ms 6712 KB Output is partially correct - 91180 call(s) of encode_bit()
7 Correct 107 ms 8208 KB Output is partially correct - 168850 call(s) of encode_bit()
8 Correct 22 ms 5576 KB Output is correct - 26451 call(s) of encode_bit()
9 Correct 26 ms 5832 KB Output is correct - 24650 call(s) of encode_bit()
10 Correct 25 ms 5756 KB Output is correct - 24110 call(s) of encode_bit()
11 Correct 43 ms 6080 KB Output is correct - 41310 call(s) of encode_bit()
12 Correct 19 ms 5516 KB Output is correct - 17600 call(s) of encode_bit()
13 Correct 111 ms 7636 KB Output is partially correct - 110290 call(s) of encode_bit()
14 Correct 28 ms 5800 KB Output is correct - 28230 call(s) of encode_bit()
15 Correct 27 ms 5888 KB Output is correct - 29870 call(s) of encode_bit()
16 Correct 100 ms 6976 KB Output is correct - 56330 call(s) of encode_bit()
17 Correct 81 ms 6948 KB Output is correct - 52560 call(s) of encode_bit()
18 Correct 111 ms 7620 KB Output is partially correct - 76010 call(s) of encode_bit()
19 Correct 67 ms 6848 KB Output is partially correct - 74280 call(s) of encode_bit()
20 Correct 131 ms 8044 KB Output is partially correct - 96200 call(s) of encode_bit()
21 Correct 158 ms 8376 KB Output is partially correct - 96870 call(s) of encode_bit()
22 Correct 112 ms 7836 KB Output is partially correct - 136030 call(s) of encode_bit()
23 Correct 190 ms 9060 KB Output is partially correct - 126420 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 19248 KB Output is partially correct - 205440 call(s) of encode_bit()
2 Correct 3 ms 4736 KB Output is correct - 95 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 43280 call(s) of encode_bit()
4 Correct 4 ms 4896 KB Output is correct - 125 call(s) of encode_bit()
5 Correct 63 ms 6788 KB Output is partially correct - 89280 call(s) of encode_bit()
6 Correct 61 ms 6712 KB Output is partially correct - 91180 call(s) of encode_bit()
7 Correct 107 ms 8208 KB Output is partially correct - 168850 call(s) of encode_bit()
8 Correct 22 ms 5576 KB Output is correct - 26451 call(s) of encode_bit()
9 Correct 26 ms 5832 KB Output is correct - 24650 call(s) of encode_bit()
10 Correct 25 ms 5756 KB Output is correct - 24110 call(s) of encode_bit()
11 Correct 43 ms 6080 KB Output is correct - 41310 call(s) of encode_bit()
12 Correct 19 ms 5516 KB Output is correct - 17600 call(s) of encode_bit()
13 Correct 111 ms 7636 KB Output is partially correct - 110290 call(s) of encode_bit()
14 Correct 28 ms 5800 KB Output is correct - 28230 call(s) of encode_bit()
15 Correct 27 ms 5888 KB Output is correct - 29870 call(s) of encode_bit()
16 Correct 100 ms 6976 KB Output is correct - 56330 call(s) of encode_bit()
17 Correct 81 ms 6948 KB Output is correct - 52560 call(s) of encode_bit()
18 Correct 111 ms 7620 KB Output is partially correct - 76010 call(s) of encode_bit()
19 Correct 67 ms 6848 KB Output is partially correct - 74280 call(s) of encode_bit()
20 Correct 131 ms 8044 KB Output is partially correct - 96200 call(s) of encode_bit()
21 Correct 158 ms 8376 KB Output is partially correct - 96870 call(s) of encode_bit()
22 Correct 112 ms 7836 KB Output is partially correct - 136030 call(s) of encode_bit()
23 Correct 190 ms 9060 KB Output is partially correct - 126420 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 19248 KB Output is partially correct - 205440 call(s) of encode_bit()
2 Correct 3 ms 4736 KB Output is correct - 95 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 43280 call(s) of encode_bit()
4 Correct 4 ms 4896 KB Output is correct - 125 call(s) of encode_bit()
5 Correct 63 ms 6788 KB Output is partially correct - 89280 call(s) of encode_bit()
6 Correct 61 ms 6712 KB Output is partially correct - 91180 call(s) of encode_bit()
7 Correct 107 ms 8208 KB Output is partially correct - 168850 call(s) of encode_bit()
8 Correct 22 ms 5576 KB Output is correct - 26451 call(s) of encode_bit()
9 Correct 26 ms 5832 KB Output is correct - 24650 call(s) of encode_bit()
10 Correct 25 ms 5756 KB Output is correct - 24110 call(s) of encode_bit()
11 Correct 43 ms 6080 KB Output is correct - 41310 call(s) of encode_bit()
12 Correct 19 ms 5516 KB Output is correct - 17600 call(s) of encode_bit()
13 Correct 111 ms 7636 KB Output is partially correct - 110290 call(s) of encode_bit()
14 Correct 28 ms 5800 KB Output is correct - 28230 call(s) of encode_bit()
15 Correct 27 ms 5888 KB Output is correct - 29870 call(s) of encode_bit()
16 Correct 100 ms 6976 KB Output is correct - 56330 call(s) of encode_bit()
17 Correct 81 ms 6948 KB Output is correct - 52560 call(s) of encode_bit()
18 Correct 111 ms 7620 KB Output is partially correct - 76010 call(s) of encode_bit()
19 Correct 67 ms 6848 KB Output is partially correct - 74280 call(s) of encode_bit()
20 Correct 131 ms 8044 KB Output is partially correct - 96200 call(s) of encode_bit()
21 Correct 158 ms 8376 KB Output is partially correct - 96870 call(s) of encode_bit()
22 Correct 112 ms 7836 KB Output is partially correct - 136030 call(s) of encode_bit()
23 Correct 190 ms 9060 KB Output is partially correct - 126420 call(s) of encode_bit()