oj.uz

Submission #362642

# Submission time Handle Problem Language Result Execution time Memory
362642 2021-02-03T19:52:21 Z LucaDantas Saveit (IOI10_saveit) C++17
100 / 100
 289 ms 10844 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;

#define pb push_back

constexpr int maxn = 1e3+10;

static int pai[maxn], dist[maxn];

static vector<int> g[maxn];

bool on(int a, int b) {return a&(1<<b);}

void dfs(int u) {
	dist[u] = 1;
	for(int v : g[u])
		if(!dist[v])
			pai[v] = u, dfs(v);
}

void encode(int N, int H, int M, int *A, int *B){
	for(int i = 0; i < M; i++)
		g[A[i]].pb(B[i]), g[B[i]].pb(A[i]);
	memset(pai, -1, sizeof pai);
	dfs(0);
	for(int i = 1; i < N; i++)
		for(int j = 0; j < 10; j++)
			encode_bit(on(pai[i], j));
	for(int i = 0; i < H; i++) {
		queue<int> q;
		for(int j = 0; j < N; j++)
			dist[j] = maxn;
		q.push(i);
		dist[i] = 0;

		while(q.size()) {
			int u = q.front(); q.pop();
			for(int v : g[u])
				if(dist[v] > dist[u]+1)
					q.push(v), dist[v] = dist[u]+1;
		}

		for(int j = 1; j < N; j += 3) {
			int pot[3] = {1, 3, 9}, p = 0;
			for(int k : {0, 1, 2})
				p += (dist[pai[j+k]]-dist[j+k]+1)*pot[k];
			for(int k = 0; k < 5; k++)
				encode_bit(on(p, k));
		}
	}
}

#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

using namespace std;

#define pb push_back

constexpr int maxn = 1e3+10;

static int pai[maxn], dist[maxn], f[maxn];

static vector<int> g[maxn];

bool mark[maxn];

void dfs_ans(int u) {
	mark[u] = 1;
	if(!mark[pai[u]])
		dist[pai[u]] = dist[u] + f[u], dfs_ans(pai[u]);
	for(int v : g[u]) {
		if(mark[v]) continue;
		dist[v] = dist[u] - f[v];
		dfs_ans(v);
	}
}

void decode(int N, int H) {
	for(int i = 1; i < N; i++) {
		for(int j = 0; j < 10; j++)
			pai[i] += decode_bit()<<j;
		g[pai[i]].pb(i);
	}
	for(int i = 0; i < H; i++) {
		for(int j = 1; j < N; j += 3) {
			int p = 0;
			for(int k = 0; k < 5; k++)
				p += decode_bit()<<k;
			int pot[] = {1, 3, 9, 27};
			for(int k : {0, 1, 2})
				f[j+k] = ((p%pot[k+1])/pot[k])-1;
		}
		dfs_ans(i);
		for(int j = 0; j < N; j++)
			hops(i, j, dist[j]);
		memset(f, 0, sizeof f);
		memset(dist, 0, sizeof dist);
		memset(mark, 0, sizeof mark);
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 10844 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4756 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5472 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4704 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 32 ms 5856 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 39 ms 5856 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 53 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 28 ms 5716 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 33 ms 5728 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 34 ms 5896 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 64 ms 6384 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 30 ms 5828 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 84 ms 6128 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 73 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 47 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 78 ms 6752 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 7016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 87 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 10844 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4756 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5472 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4704 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 32 ms 5856 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 39 ms 5856 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 53 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 28 ms 5716 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 33 ms 5728 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 34 ms 5896 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 64 ms 6384 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 30 ms 5828 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 84 ms 6128 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 73 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 47 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 78 ms 6752 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 7016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 87 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 10844 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4756 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5472 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4704 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 32 ms 5856 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 39 ms 5856 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 53 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 28 ms 5716 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 33 ms 5728 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 34 ms 5896 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 64 ms 6384 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 30 ms 5828 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 84 ms 6128 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 73 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 47 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 78 ms 6752 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 7016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 87 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 10844 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4756 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5472 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4704 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 32 ms 5856 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 39 ms 5856 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 53 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 28 ms 5716 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 33 ms 5728 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 34 ms 5896 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 64 ms 6384 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 5600 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 30 ms 5828 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 84 ms 6128 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 73 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 47 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 78 ms 6752 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 92 ms 7016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 87 ms 7032 KB Output is correct - 69930 call(s) of encode_bit()