oj.uz

Submission #566769

# Submission time Handle Problem Language Result Execution time Memory
566769 2022-05-22T20:12:46 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 200 ms 14040 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 "decoder.h"
 
using namespace std;
 
 
void decode(int n, int h){
    int dis[1001],p[1001],j;
    vector<int> diff[1001];
    vector<int>adj[1001];
 
 
    j = 0;
    for(int i = 0; i < n; i++) {
        diff[i].resize(n);
        adj[i].clear();
        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:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while(j < b.size()){
      |           ~~^~~~~~~~~~
decoder.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(j < bb.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14040 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8428 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8664 KB wrong parameter
6 Incorrect 22 ms 9520 KB wrong parameter
7 Incorrect 33 ms 9716 KB wrong parameter
8 Incorrect 22 ms 9104 KB wrong parameter
9 Incorrect 27 ms 9304 KB wrong parameter
10 Incorrect 31 ms 9452 KB wrong parameter
11 Incorrect 28 ms 9556 KB wrong parameter
12 Incorrect 25 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 29 ms 9400 KB wrong parameter
15 Incorrect 30 ms 9424 KB wrong parameter
16 Incorrect 47 ms 9876 KB wrong parameter
17 Incorrect 47 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10028 KB wrong parameter
19 Incorrect 37 ms 9580 KB wrong parameter
20 Incorrect 64 ms 10212 KB wrong parameter
21 Incorrect 67 ms 10396 KB wrong parameter
22 Incorrect 44 ms 9828 KB wrong parameter
23 Incorrect 62 ms 10616 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14040 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8428 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8664 KB wrong parameter
6 Incorrect 22 ms 9520 KB wrong parameter
7 Incorrect 33 ms 9716 KB wrong parameter
8 Incorrect 22 ms 9104 KB wrong parameter
9 Incorrect 27 ms 9304 KB wrong parameter
10 Incorrect 31 ms 9452 KB wrong parameter
11 Incorrect 28 ms 9556 KB wrong parameter
12 Incorrect 25 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 29 ms 9400 KB wrong parameter
15 Incorrect 30 ms 9424 KB wrong parameter
16 Incorrect 47 ms 9876 KB wrong parameter
17 Incorrect 47 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10028 KB wrong parameter
19 Incorrect 37 ms 9580 KB wrong parameter
20 Incorrect 64 ms 10212 KB wrong parameter
21 Incorrect 67 ms 10396 KB wrong parameter
22 Incorrect 44 ms 9828 KB wrong parameter
23 Incorrect 62 ms 10616 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14040 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8428 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8664 KB wrong parameter
6 Incorrect 22 ms 9520 KB wrong parameter
7 Incorrect 33 ms 9716 KB wrong parameter
8 Incorrect 22 ms 9104 KB wrong parameter
9 Incorrect 27 ms 9304 KB wrong parameter
10 Incorrect 31 ms 9452 KB wrong parameter
11 Incorrect 28 ms 9556 KB wrong parameter
12 Incorrect 25 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 29 ms 9400 KB wrong parameter
15 Incorrect 30 ms 9424 KB wrong parameter
16 Incorrect 47 ms 9876 KB wrong parameter
17 Incorrect 47 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10028 KB wrong parameter
19 Incorrect 37 ms 9580 KB wrong parameter
20 Incorrect 64 ms 10212 KB wrong parameter
21 Incorrect 67 ms 10396 KB wrong parameter
22 Incorrect 44 ms 9828 KB wrong parameter
23 Incorrect 62 ms 10616 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14040 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8428 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8664 KB wrong parameter
6 Incorrect 22 ms 9520 KB wrong parameter
7 Incorrect 33 ms 9716 KB wrong parameter
8 Incorrect 22 ms 9104 KB wrong parameter
9 Incorrect 27 ms 9304 KB wrong parameter
10 Incorrect 31 ms 9452 KB wrong parameter
11 Incorrect 28 ms 9556 KB wrong parameter
12 Incorrect 25 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 29 ms 9400 KB wrong parameter
15 Incorrect 30 ms 9424 KB wrong parameter
16 Incorrect 47 ms 9876 KB wrong parameter
17 Incorrect 47 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10028 KB wrong parameter
19 Incorrect 37 ms 9580 KB wrong parameter
20 Incorrect 64 ms 10212 KB wrong parameter
21 Incorrect 67 ms 10396 KB wrong parameter
22 Incorrect 44 ms 9828 KB wrong parameter
23 Incorrect 62 ms 10616 KB wrong parameter