oj.uz

Submission #1019140

# Submission time Handle Problem Language Result Execution time Memory
1019140 2024-07-10T14:06:04 Z socpite Saveit (IOI10_saveit) C++14
100 / 100
 353 ms 15724 KB 
#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);
		}
	}
}

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

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 353 ms 15724 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 12580 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 49 ms 13372 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 6 ms 12568 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 94 ms 13480 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 77 ms 13784 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 90 ms 13992 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 51 ms 13732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 81 ms 13720 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 59 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 75 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 88 ms 13704 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 116 ms 14004 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 57 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 61 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 86 ms 13984 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 88 ms 13800 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 98 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 75 ms 13736 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 110 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 134 ms 14236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 96 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 124 ms 14244 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 15724 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 12580 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 49 ms 13372 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 6 ms 12568 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 94 ms 13480 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 77 ms 13784 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 90 ms 13992 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 51 ms 13732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 81 ms 13720 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 59 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 75 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 88 ms 13704 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 116 ms 14004 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 57 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 61 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 86 ms 13984 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 88 ms 13800 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 98 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 75 ms 13736 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 110 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 134 ms 14236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 96 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 124 ms 14244 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 15724 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 12580 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 49 ms 13372 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 6 ms 12568 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 94 ms 13480 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 77 ms 13784 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 90 ms 13992 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 51 ms 13732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 81 ms 13720 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 59 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 75 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 88 ms 13704 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 116 ms 14004 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 57 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 61 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 86 ms 13984 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 88 ms 13800 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 98 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 75 ms 13736 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 110 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 134 ms 14236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 96 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 124 ms 14244 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 15724 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 12580 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 49 ms 13372 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 6 ms 12568 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 94 ms 13480 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 77 ms 13784 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 90 ms 13992 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 51 ms 13732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 81 ms 13720 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 59 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 75 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 88 ms 13704 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 116 ms 14004 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 57 ms 13816 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 61 ms 13732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 86 ms 13984 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 88 ms 13800 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 98 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 75 ms 13736 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 110 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 134 ms 14236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 96 ms 13988 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 124 ms 14244 KB Output is correct - 69930 call(s) of encode_bit()