oj.uz

Submission #15629

# Submission time Handle Problem Language Result Execution time Memory
15629 2015-07-13T12:20:41 Z gs14004 Saveit (IOI10_saveit) C++14
100 / 100
 360 ms 11448 KB 
#include "grader.h"
#include "encoder.h"
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int dist[36][1005];
vector<int> graph[1005];

bool vis[1005];
int par[1005];
queue<int> q;

void bfs(int* dist, int st){
    memset(vis,0,sizeof(vis));
    q.push(st);
    vis[st] = 1;
    while(!q.empty()){
        int qf = q.front();
        q.pop();
        for(auto &i : graph[qf]){
            if(vis[i]) continue;
            vis[i] = 1;
            dist[i] = dist[qf] + 1;
            par[i] = qf;
            q.push(i);
        }
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    for(int i=0; i<ne; i++){
        graph[v1[i]].push_back(v2[i]);
        graph[v2[i]].push_back(v1[i]);
    }
    for(int i=nh-1; i>=0; i--){
        bfs(dist[i],i);
    }
    for(int i=1; i<nv; i++){
        for(int j=0; j<10; j++){
            encode_bit((par[i] >> j) & 1);
        }
    }
    for(int i=0; i<nh; i++){
        for(int j=1; j<nv; j+=5){
            int ret = 0;
            for(int k=0; k<5; k++){
                int dx = dist[i][j+k] - dist[i][par[j+k]] + 1;
                if(j+k >= nv) dx = 0;
                ret = ret * 3 + dx;
            }
            for(int i=0; i<8; i++){
                encode_bit((ret >> i) & 1);
            }
        }
    }
}
#include "grader.h"
#include "decoder.h"
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector<int> tree[1005];

int dx[1005];

void dfs(int x, int pa){
	for(auto &i : tree[x]){
		dx[i] += dx[x];
		dfs(i, x);
	}
}

void decode(int nv, int nh){
	for(int i=1; i<nv; i++){
		int r = 0;
		for(int j=0; j<10; j++){
			r |= (decode_bit() << j);
		}
		tree[r].push_back(i);
	}
	for(int i=0; i<nh; i++){
		for(int j=1; j<nv; j+=5){
			int buf = 0;
			for(int k=0; k<8; k++){
				buf |= (decode_bit() << k);
			}
			for(int i=4; i>=0; i--){
				int r = buf % 3;
				buf /= 3;
				r--;
				dx[j + i] = r;
			}
		}
		dfs(0,0);
		for(int j=0; j<nv; j++){
			hops(i,j,dx[j] - dx[i]);
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 11448 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 3 ms 4596 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5552 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4592 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 34 ms 5752 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 39 ms 5776 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5540 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 30 ms 5488 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5772 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 44 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5644 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 82 ms 6248 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5564 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 31 ms 5700 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 92 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 61 ms 6020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 61 ms 6352 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 43 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 82 ms 6624 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 86 ms 6756 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 64 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 90 ms 6816 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 11448 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 3 ms 4596 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5552 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4592 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 34 ms 5752 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 39 ms 5776 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5540 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 30 ms 5488 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5772 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 44 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5644 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 82 ms 6248 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5564 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 31 ms 5700 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 92 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 61 ms 6020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 61 ms 6352 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 43 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 82 ms 6624 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 86 ms 6756 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 64 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 90 ms 6816 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 11448 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 3 ms 4596 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5552 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4592 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 34 ms 5752 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 39 ms 5776 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5540 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 30 ms 5488 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5772 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 44 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5644 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 82 ms 6248 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5564 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 31 ms 5700 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 92 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 61 ms 6020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 61 ms 6352 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 43 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 82 ms 6624 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 86 ms 6756 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 64 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 90 ms 6816 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 11448 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 3 ms 4596 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5552 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 7 ms 4592 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 34 ms 5752 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 39 ms 5776 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 62 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5540 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 30 ms 5488 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 32 ms 5772 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 44 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 30 ms 5644 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 82 ms 6248 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 31 ms 5564 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 31 ms 5700 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 92 ms 6076 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 61 ms 6020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 61 ms 6352 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 43 ms 5848 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 82 ms 6624 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 86 ms 6756 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 64 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 90 ms 6816 KB Output is correct - 67590 call(s) of encode_bit()