oj.uz

Submission #15622

# Submission time Handle Problem Language Result Execution time Memory
15622 2015-07-13T11:30:12 Z gs14004 Saveit (IOI10_saveit) C++14
0 / 100
 179 ms 11624 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++){
            int diff = dist[i][j] - dist[i][par[j]];
            if(diff == -1){
                encode_bit(1);
                encode_bit(1);
            }
            else if(diff == 0){
                encode_bit(0);
                encode_bit(0);
            }
            else{
                encode_bit(0);
                encode_bit(1);
            }
        }
    }
}
#include "grader.h"
#include "decoder.h"
#include <vector>
#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++){
			int t = decode_bit() << 1;
			t += decode_bit();
			if(t == 3) t = -1;
			dx[j] = t;
		}
		dfs(0,0);
		for(int j=0; j<nv; j++){
			hops(i,j,dx[i] - dx[0]);
		}
	}
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 11624 KB wrong parameter
2 Incorrect 7 ms 4572 KB wrong parameter
3 Incorrect 27 ms 5656 KB wrong parameter
4 Incorrect 6 ms 4544 KB wrong parameter
5 Incorrect 33 ms 5908 KB wrong parameter
6 Incorrect 33 ms 5848 KB wrong parameter
7 Incorrect 64 ms 6200 KB wrong parameter
8 Incorrect 27 ms 5680 KB wrong parameter
9 Incorrect 28 ms 5752 KB wrong parameter
10 Incorrect 32 ms 5704 KB wrong parameter
11 Incorrect 56 ms 5792 KB wrong parameter
12 Incorrect 27 ms 5552 KB wrong parameter
13 Incorrect 54 ms 6296 KB wrong parameter
14 Incorrect 28 ms 5740 KB wrong parameter
15 Incorrect 38 ms 5748 KB wrong parameter
16 Incorrect 59 ms 6148 KB wrong parameter
17 Incorrect 65 ms 6148 KB wrong parameter
18 Incorrect 67 ms 6544 KB wrong parameter
19 Incorrect 43 ms 6064 KB wrong parameter
20 Incorrect 56 ms 6684 KB wrong parameter
21 Incorrect 69 ms 6620 KB wrong parameter
22 Incorrect 77 ms 6308 KB wrong parameter
23 Incorrect 69 ms 7032 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 11624 KB wrong parameter
2 Incorrect 7 ms 4572 KB wrong parameter
3 Incorrect 27 ms 5656 KB wrong parameter
4 Incorrect 6 ms 4544 KB wrong parameter
5 Incorrect 33 ms 5908 KB wrong parameter
6 Incorrect 33 ms 5848 KB wrong parameter
7 Incorrect 64 ms 6200 KB wrong parameter
8 Incorrect 27 ms 5680 KB wrong parameter
9 Incorrect 28 ms 5752 KB wrong parameter
10 Incorrect 32 ms 5704 KB wrong parameter
11 Incorrect 56 ms 5792 KB wrong parameter
12 Incorrect 27 ms 5552 KB wrong parameter
13 Incorrect 54 ms 6296 KB wrong parameter
14 Incorrect 28 ms 5740 KB wrong parameter
15 Incorrect 38 ms 5748 KB wrong parameter
16 Incorrect 59 ms 6148 KB wrong parameter
17 Incorrect 65 ms 6148 KB wrong parameter
18 Incorrect 67 ms 6544 KB wrong parameter
19 Incorrect 43 ms 6064 KB wrong parameter
20 Incorrect 56 ms 6684 KB wrong parameter
21 Incorrect 69 ms 6620 KB wrong parameter
22 Incorrect 77 ms 6308 KB wrong parameter
23 Incorrect 69 ms 7032 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 11624 KB wrong parameter
2 Incorrect 7 ms 4572 KB wrong parameter
3 Incorrect 27 ms 5656 KB wrong parameter
4 Incorrect 6 ms 4544 KB wrong parameter
5 Incorrect 33 ms 5908 KB wrong parameter
6 Incorrect 33 ms 5848 KB wrong parameter
7 Incorrect 64 ms 6200 KB wrong parameter
8 Incorrect 27 ms 5680 KB wrong parameter
9 Incorrect 28 ms 5752 KB wrong parameter
10 Incorrect 32 ms 5704 KB wrong parameter
11 Incorrect 56 ms 5792 KB wrong parameter
12 Incorrect 27 ms 5552 KB wrong parameter
13 Incorrect 54 ms 6296 KB wrong parameter
14 Incorrect 28 ms 5740 KB wrong parameter
15 Incorrect 38 ms 5748 KB wrong parameter
16 Incorrect 59 ms 6148 KB wrong parameter
17 Incorrect 65 ms 6148 KB wrong parameter
18 Incorrect 67 ms 6544 KB wrong parameter
19 Incorrect 43 ms 6064 KB wrong parameter
20 Incorrect 56 ms 6684 KB wrong parameter
21 Incorrect 69 ms 6620 KB wrong parameter
22 Incorrect 77 ms 6308 KB wrong parameter
23 Incorrect 69 ms 7032 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 11624 KB wrong parameter
2 Incorrect 7 ms 4572 KB wrong parameter
3 Incorrect 27 ms 5656 KB wrong parameter
4 Incorrect 6 ms 4544 KB wrong parameter
5 Incorrect 33 ms 5908 KB wrong parameter
6 Incorrect 33 ms 5848 KB wrong parameter
7 Incorrect 64 ms 6200 KB wrong parameter
8 Incorrect 27 ms 5680 KB wrong parameter
9 Incorrect 28 ms 5752 KB wrong parameter
10 Incorrect 32 ms 5704 KB wrong parameter
11 Incorrect 56 ms 5792 KB wrong parameter
12 Incorrect 27 ms 5552 KB wrong parameter
13 Incorrect 54 ms 6296 KB wrong parameter
14 Incorrect 28 ms 5740 KB wrong parameter
15 Incorrect 38 ms 5748 KB wrong parameter
16 Incorrect 59 ms 6148 KB wrong parameter
17 Incorrect 65 ms 6148 KB wrong parameter
18 Incorrect 67 ms 6544 KB wrong parameter
19 Incorrect 43 ms 6064 KB wrong parameter
20 Incorrect 56 ms 6684 KB wrong parameter
21 Incorrect 69 ms 6620 KB wrong parameter
22 Incorrect 77 ms 6308 KB wrong parameter
23 Incorrect 69 ms 7032 KB wrong parameter