oj.uz

Submission #566765

# Submission time Handle Problem Language Result Execution time Memory
566765 2022-05-22T20:02:59 Z birthdaycake Saveit (IOI10_saveit) C++14
0 / 100
 208 ms 14208 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
 
using namespace std;
 
 
 
 
void encode(int n, int h, int p, int a[], int b[]){
    
    vector<int>adj[1001];
     
     
    int dis[1001],par[1001];
    for(int i = 0; i < n; i++) {
        dis[i] = INT_MAX;
    }
    for(int i = 0; i < p; i++){
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    dis[0] = par[0] = 0;
    vector<int>d = {0};
    int j = 0;
    while(j < d.size()){
        for(auto s: adj[d[j]]){
            if(dis[s] == INT_MAX){
                dis[s] = dis[d[j]] + 1;
                par[s] = d[j];
                d.push_back(s);
            }
        }
        j++;
    }
    
    for(int i = 1; i < n; i++){
        for(int k = 0; k < 10; k++){
            if(par[i] & (1 << k)) encode_bit(1);
            else encode_bit(0);
        }
    }
    for(int i = 1; i < h; i++){
        vector<int>pc(n, INT_MAX);
        pc[i] = 0;
        int j = 0;
        vector<int>b = {i};
        while(j < b.size()){
            for(auto s:adj[b[j]]){
                if(pc[s] == INT_MAX){
                    pc[s] = pc[b[j]] + 1;
                    b.push_back(s);
                }
            }
            j++;
        }
        for(int k = 1; k < n; k++){
            int diff = pc[k] - pc[par[k]];
            if(diff != 0){
                encode_bit(1);
                if(diff < 0) encode_bit(1);
                else encode_bit(0);
            }else{
                encode_bit(0);
            }
        }
    }
    
    
}
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
 
using namespace std;
 
 

 
void decode(int n, int h){
    
    vector<int>adj[1001];
 
	int dis[1001],p[1001],diff[1001][1001],j;
  	j = 0;
    for(int i = 0; i < n; i++) {
        dis[i] = INT_MAX;
    }
    for(int i = 0; i < n; i++){
        for(int k = 0; k < n; k++) diff[i][k] = 0;
    }
    for(int i = 1; i < n; i++){
        int parent = 0;
        for(int k = 0; k < 10; k++){
            if(decode_bit()) parent += (1 << k);
        }
        p[i] = parent;
        adj[i].push_back(parent);
        adj[parent].push_back(i);
    }
    dis[0] = j = 0;
    vector<int>b = {0};
    while(j < b.size()){
        for(auto s: adj[b[j]]){
            if(dis[s] == INT_MAX){
                dis[s] = dis[b[j]] + 1;
            }
        }
        j++;
    }
    for(int i = 0; i < n; i++) hops(0,i, dis[i]);
    
    
    for(int i = 1; i < h; i++){
        for(int k = 1; k < n; k++){
            if(!decode_bit()){
                diff[k][p[k]] = diff[p[k]][k] = 0;
            }else{
                if(decode_bit()){
                    diff[k][p[k]] = -1;
                    diff[p[k]][k] = 1;
                }else{
                    diff[p[k]][k] = -1;
                    diff[k][p[k]] = 1;
                }
            }
        }
        vector<int>pc(n, INT_MAX);
        pc[i] = j = 0;
        vector<int>bb = {i};
        while(j < bb.size()){
            for(auto s:adj[bb[j]]){
                if(pc[s] == INT_MAX){
                    pc[s] = pc[bb[j]] + diff[bb[j]][s];
                    bb.push_back(s);
                }
            }
            j++;
        }
        for(int t = 0; t < n; t++){
            hops(i,t,pc[t]);
        }
    }
    
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(j < d.size()){
      |           ~~^~~~~~~~~~
encoder.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while(j < b.size()){
      |               ~~^~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:33:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while(j < b.size()){
      |           ~~^~~~~~~~~~
decoder.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while(j < bb.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 14208 KB wrong parameter
2 Incorrect 5 ms 8580 KB wrong parameter
3 Incorrect 22 ms 9148 KB wrong parameter
4 Incorrect 4 ms 8568 KB wrong parameter
5 Incorrect 24 ms 9424 KB wrong parameter
6 Incorrect 33 ms 9404 KB wrong parameter
7 Incorrect 41 ms 9664 KB wrong parameter
8 Incorrect 19 ms 9340 KB wrong parameter
9 Incorrect 24 ms 9336 KB wrong parameter
10 Incorrect 25 ms 9344 KB wrong parameter
11 Incorrect 24 ms 9460 KB wrong parameter
12 Incorrect 25 ms 9472 KB wrong parameter
13 Incorrect 43 ms 9752 KB wrong parameter
14 Incorrect 23 ms 9324 KB wrong parameter
15 Incorrect 26 ms 9372 KB wrong parameter
16 Incorrect 40 ms 9840 KB wrong parameter
17 Incorrect 38 ms 9684 KB wrong parameter
18 Incorrect 44 ms 9904 KB wrong parameter
19 Incorrect 30 ms 9588 KB wrong parameter
20 Incorrect 54 ms 10396 KB wrong parameter
21 Incorrect 62 ms 10340 KB wrong parameter
22 Incorrect 40 ms 9808 KB wrong parameter
23 Incorrect 64 ms 10584 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 14208 KB wrong parameter
2 Incorrect 5 ms 8580 KB wrong parameter
3 Incorrect 22 ms 9148 KB wrong parameter
4 Incorrect 4 ms 8568 KB wrong parameter
5 Incorrect 24 ms 9424 KB wrong parameter
6 Incorrect 33 ms 9404 KB wrong parameter
7 Incorrect 41 ms 9664 KB wrong parameter
8 Incorrect 19 ms 9340 KB wrong parameter
9 Incorrect 24 ms 9336 KB wrong parameter
10 Incorrect 25 ms 9344 KB wrong parameter
11 Incorrect 24 ms 9460 KB wrong parameter
12 Incorrect 25 ms 9472 KB wrong parameter
13 Incorrect 43 ms 9752 KB wrong parameter
14 Incorrect 23 ms 9324 KB wrong parameter
15 Incorrect 26 ms 9372 KB wrong parameter
16 Incorrect 40 ms 9840 KB wrong parameter
17 Incorrect 38 ms 9684 KB wrong parameter
18 Incorrect 44 ms 9904 KB wrong parameter
19 Incorrect 30 ms 9588 KB wrong parameter
20 Incorrect 54 ms 10396 KB wrong parameter
21 Incorrect 62 ms 10340 KB wrong parameter
22 Incorrect 40 ms 9808 KB wrong parameter
23 Incorrect 64 ms 10584 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 14208 KB wrong parameter
2 Incorrect 5 ms 8580 KB wrong parameter
3 Incorrect 22 ms 9148 KB wrong parameter
4 Incorrect 4 ms 8568 KB wrong parameter
5 Incorrect 24 ms 9424 KB wrong parameter
6 Incorrect 33 ms 9404 KB wrong parameter
7 Incorrect 41 ms 9664 KB wrong parameter
8 Incorrect 19 ms 9340 KB wrong parameter
9 Incorrect 24 ms 9336 KB wrong parameter
10 Incorrect 25 ms 9344 KB wrong parameter
11 Incorrect 24 ms 9460 KB wrong parameter
12 Incorrect 25 ms 9472 KB wrong parameter
13 Incorrect 43 ms 9752 KB wrong parameter
14 Incorrect 23 ms 9324 KB wrong parameter
15 Incorrect 26 ms 9372 KB wrong parameter
16 Incorrect 40 ms 9840 KB wrong parameter
17 Incorrect 38 ms 9684 KB wrong parameter
18 Incorrect 44 ms 9904 KB wrong parameter
19 Incorrect 30 ms 9588 KB wrong parameter
20 Incorrect 54 ms 10396 KB wrong parameter
21 Incorrect 62 ms 10340 KB wrong parameter
22 Incorrect 40 ms 9808 KB wrong parameter
23 Incorrect 64 ms 10584 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 14208 KB wrong parameter
2 Incorrect 5 ms 8580 KB wrong parameter
3 Incorrect 22 ms 9148 KB wrong parameter
4 Incorrect 4 ms 8568 KB wrong parameter
5 Incorrect 24 ms 9424 KB wrong parameter
6 Incorrect 33 ms 9404 KB wrong parameter
7 Incorrect 41 ms 9664 KB wrong parameter
8 Incorrect 19 ms 9340 KB wrong parameter
9 Incorrect 24 ms 9336 KB wrong parameter
10 Incorrect 25 ms 9344 KB wrong parameter
11 Incorrect 24 ms 9460 KB wrong parameter
12 Incorrect 25 ms 9472 KB wrong parameter
13 Incorrect 43 ms 9752 KB wrong parameter
14 Incorrect 23 ms 9324 KB wrong parameter
15 Incorrect 26 ms 9372 KB wrong parameter
16 Incorrect 40 ms 9840 KB wrong parameter
17 Incorrect 38 ms 9684 KB wrong parameter
18 Incorrect 44 ms 9904 KB wrong parameter
19 Incorrect 30 ms 9588 KB wrong parameter
20 Incorrect 54 ms 10396 KB wrong parameter
21 Incorrect 62 ms 10340 KB wrong parameter
22 Incorrect 40 ms 9808 KB wrong parameter
23 Incorrect 64 ms 10584 KB wrong parameter