oj.uz

Submission #23149

# Submission time Handle Problem Language Result Execution time Memory
23149 2017-05-03T16:00:16 Z kdh9949 Saveit (IOI10_saveit) C++14
100 / 100
 275 ms 11608 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

static int n, h, p[1010], md[1010], v[1010];
static vector<int> e[1010], t[1010];
static queue<int> q;

void dfs(int x){
    for(auto &i : e[x]){
		if(p[i] != -1) continue;
		p[i] = x;
		dfs(i);
    }
}

void fil(int x, int p){
    for(auto &i : t[x]){
		if(i == p) continue;
		v[i] = md[i] - md[x] + 1;
		fil(i, x);
    }
}

void bfs(int x){
	fill(md, md + n, 1e9);
	md[x] = 0;
	q.push(x);
	while(!q.empty()){
		int c = q.front(); q.pop();
		for(auto &i : e[c]){
			if(md[c] + 1 >= md[i]) continue;
			md[i] = md[c] + 1;
			q.push(i);
		}
	}
	fil(x, -1);
	v[x] = 1;
	for(int i = 0; i < n; i += 5){
		int t = 0;
		for(int j = 0, k = 1; j < 5; j++, k *= 3) t += k * v[i + j];
        for(int j = 0; j < 8; j++) encode_bit(!!(t & (1 << j)));
	}
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
	n = nv;
	h = nh;
    for(int i = 0, x, y; i < ne; i++){
		x = v1[i]; y = v2[i];
		e[x].push_back(y);
		e[y].push_back(x);
    }
    fill(p + 1, p + n, -1);
    dfs(0);
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 10; j++) encode_bit(!!(p[i] & (1 << j)));
    }
    for(int i = 1; i < n; i++){
		t[i].push_back(p[i]);
		t[p[i]].push_back(i);
    }
    for(int i = 0; i < h; i++){
        bfs(i);
    }
}

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

static int n, h, v[1010];
static vector<int> t[1010];

void get(int x, int p){
	for(auto &i : t[x]){
		if(i == p) continue;
		v[i] += v[x];
		get(i, x);
	}
}

void decode(int nv, int nh){
	n = nv;
	h = nh;
	for(int i = 1; i < n; i++){
		int x = 0;
		for(int j = 0; j < 10; j++) x += (decode_bit() << j);
		t[x].push_back(i);
		t[i].push_back(x);
	}
	for(int i = 0; i < h; i++){
        for(int j = 0; j < n; j += 5){
        	int x = 0;
			for(int k = 0; k < 8; k++) x += (decode_bit() << k);
            for(int k = 0; k < 5; k++){
				v[j + k] = x % 3 - 1;
				x /= 3;
            }
        }
        get(i, -1);
        for(int j = 0; j < n; j++) hops(i, j, v[j]);
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 11608 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4668 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5492 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 51 ms 5768 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5764 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6124 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5544 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5628 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 40 ms 5784 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5592 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 89 ms 6220 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 32 ms 5824 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 66 ms 6132 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 77 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 56 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 79 ms 6656 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 144 ms 6692 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 61 ms 6176 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 128 ms 7120 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 11608 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4668 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5492 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 51 ms 5768 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5764 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6124 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5544 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5628 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 40 ms 5784 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5592 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 89 ms 6220 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 32 ms 5824 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 66 ms 6132 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 77 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 56 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 79 ms 6656 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 144 ms 6692 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 61 ms 6176 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 128 ms 7120 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 11608 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4668 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5492 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 51 ms 5768 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5764 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6124 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5544 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5628 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 40 ms 5784 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5592 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 89 ms 6220 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 32 ms 5824 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 66 ms 6132 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 77 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 56 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 79 ms 6656 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 144 ms 6692 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 61 ms 6176 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 128 ms 7120 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 11608 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4668 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5492 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 51 ms 5768 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5764 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6124 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5544 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5628 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 40 ms 5784 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5592 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 89 ms 6220 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 32 ms 5824 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 66 ms 6132 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 77 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 56 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 79 ms 6656 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 144 ms 6692 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 61 ms 6176 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 128 ms 7120 KB Output is correct - 67590 call(s) of encode_bit()