oj.uz

Submission #274939

# Submission time Handle Problem Language Result Execution time Memory
274939 2020-08-20T01:49:59 Z TMJN Saveit (IOI10_saveit) C++17
0 / 100
 607 ms 19880 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];

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);
			}
		}
	}
}


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

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;
}

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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 19880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 2 ms 4736 KB wrong parameter
3 Runtime error 32 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 2 ms 4736 KB wrong parameter
5 Runtime error 53 ms 10920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 56 ms 10892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 116 ms 12348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 26 ms 9548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 34 ms 9728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 27 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 45 ms 10168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 22 ms 9752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 104 ms 12252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 34 ms 9908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 35 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 97 ms 11300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 95 ms 10976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 120 ms 11668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 60 ms 10876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 137 ms 12236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 151 ms 12588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 108 ms 12156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 185 ms 13760 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 19880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 2 ms 4736 KB wrong parameter
3 Runtime error 32 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 2 ms 4736 KB wrong parameter
5 Runtime error 53 ms 10920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 56 ms 10892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 116 ms 12348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 26 ms 9548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 34 ms 9728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 27 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 45 ms 10168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 22 ms 9752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 104 ms 12252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 34 ms 9908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 35 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 97 ms 11300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 95 ms 10976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 120 ms 11668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 60 ms 10876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 137 ms 12236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 151 ms 12588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 108 ms 12156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 185 ms 13760 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 19880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 2 ms 4736 KB wrong parameter
3 Runtime error 32 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 2 ms 4736 KB wrong parameter
5 Runtime error 53 ms 10920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 56 ms 10892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 116 ms 12348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 26 ms 9548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 34 ms 9728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 27 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 45 ms 10168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 22 ms 9752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 104 ms 12252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 34 ms 9908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 35 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 97 ms 11300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 95 ms 10976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 120 ms 11668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 60 ms 10876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 137 ms 12236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 151 ms 12588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 108 ms 12156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 185 ms 13760 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 19880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 2 ms 4736 KB wrong parameter
3 Runtime error 32 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 2 ms 4736 KB wrong parameter
5 Runtime error 53 ms 10920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 56 ms 10892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 116 ms 12348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 26 ms 9548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 34 ms 9728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 27 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 45 ms 10168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 22 ms 9752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 104 ms 12252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 34 ms 9908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 35 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 97 ms 11300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 95 ms 10976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 120 ms 11668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 60 ms 10876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 137 ms 12236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 151 ms 12588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 108 ms 12156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 185 ms 13760 KB Execution killed with signal 11 (could be triggered by violating memory limits)