oj.uz

Submission #566723

# Submission time Handle Problem Language Result Execution time Memory
566723 2022-05-22T18:18:54 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 181 ms 14048 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
 
using namespace std;
 
vector<int>adj[1001];
 
 
int dis[1001],par[1001], j;
void reset(int n){
    j = 0;
    for(int i = 0; i < n; i++) {
        adj[i].clear();
        dis[i] = INT_MAX;
    }
}
 
 
void encode(int n, int h, int p, int a[], int b[]){
    
    reset(n);
    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};
    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] = 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;
 
vector<int>adj[1001];
 
 
int dis[1001],p[1001],diff[1001][1001],j;
void reset(int n){
    j = 0;
    for(int i = 0; i < n; i++) {
        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;
    }
}
 
void decode(int n, int h){
    
    reset(n);
    for(int i = 1; i < n; i++){
        int parent = 0;
        for(int k = 0; k < 10; k++){
            if(decode_bit()) parent += (1 << k);
        }
        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++){
            int x = decode_bit();
            if(x == 0){
                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>b = {i};
            while(j < b.size()){
                for(auto s:adj[b[j]]){
                    if(pc[s] == INT_MAX){
                        pc[s] = pc[b[j]] + diff[b[j]][s];
                        b.push_back(s);
                    }
                }
                j++;
            }
            for(int t = 1; t < n; t++){
                hops(i,t,pc[t]);
            }
        }
    }
    
}

Compilation message

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

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

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 14048 KB wrong parameter
2 Incorrect 2 ms 4604 KB duplicate hops call
3 Incorrect 23 ms 8880 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 20 ms 8916 KB wrong parameter
6 Incorrect 26 ms 9448 KB wrong parameter
7 Incorrect 37 ms 9684 KB wrong parameter
8 Incorrect 23 ms 9228 KB wrong parameter
9 Incorrect 28 ms 9216 KB wrong parameter
10 Incorrect 23 ms 9372 KB wrong parameter
11 Incorrect 25 ms 9372 KB wrong parameter
12 Incorrect 20 ms 9340 KB wrong parameter
13 Incorrect 47 ms 9904 KB wrong parameter
14 Incorrect 20 ms 9308 KB wrong parameter
15 Incorrect 22 ms 9372 KB wrong parameter
16 Incorrect 45 ms 9752 KB wrong parameter
17 Incorrect 40 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10008 KB wrong parameter
19 Incorrect 29 ms 9704 KB wrong parameter
20 Incorrect 51 ms 10284 KB wrong parameter
21 Incorrect 58 ms 10388 KB wrong parameter
22 Incorrect 39 ms 9928 KB wrong parameter
23 Incorrect 59 ms 10536 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 14048 KB wrong parameter
2 Incorrect 2 ms 4604 KB duplicate hops call
3 Incorrect 23 ms 8880 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 20 ms 8916 KB wrong parameter
6 Incorrect 26 ms 9448 KB wrong parameter
7 Incorrect 37 ms 9684 KB wrong parameter
8 Incorrect 23 ms 9228 KB wrong parameter
9 Incorrect 28 ms 9216 KB wrong parameter
10 Incorrect 23 ms 9372 KB wrong parameter
11 Incorrect 25 ms 9372 KB wrong parameter
12 Incorrect 20 ms 9340 KB wrong parameter
13 Incorrect 47 ms 9904 KB wrong parameter
14 Incorrect 20 ms 9308 KB wrong parameter
15 Incorrect 22 ms 9372 KB wrong parameter
16 Incorrect 45 ms 9752 KB wrong parameter
17 Incorrect 40 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10008 KB wrong parameter
19 Incorrect 29 ms 9704 KB wrong parameter
20 Incorrect 51 ms 10284 KB wrong parameter
21 Incorrect 58 ms 10388 KB wrong parameter
22 Incorrect 39 ms 9928 KB wrong parameter
23 Incorrect 59 ms 10536 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 14048 KB wrong parameter
2 Incorrect 2 ms 4604 KB duplicate hops call
3 Incorrect 23 ms 8880 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 20 ms 8916 KB wrong parameter
6 Incorrect 26 ms 9448 KB wrong parameter
7 Incorrect 37 ms 9684 KB wrong parameter
8 Incorrect 23 ms 9228 KB wrong parameter
9 Incorrect 28 ms 9216 KB wrong parameter
10 Incorrect 23 ms 9372 KB wrong parameter
11 Incorrect 25 ms 9372 KB wrong parameter
12 Incorrect 20 ms 9340 KB wrong parameter
13 Incorrect 47 ms 9904 KB wrong parameter
14 Incorrect 20 ms 9308 KB wrong parameter
15 Incorrect 22 ms 9372 KB wrong parameter
16 Incorrect 45 ms 9752 KB wrong parameter
17 Incorrect 40 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10008 KB wrong parameter
19 Incorrect 29 ms 9704 KB wrong parameter
20 Incorrect 51 ms 10284 KB wrong parameter
21 Incorrect 58 ms 10388 KB wrong parameter
22 Incorrect 39 ms 9928 KB wrong parameter
23 Incorrect 59 ms 10536 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 14048 KB wrong parameter
2 Incorrect 2 ms 4604 KB duplicate hops call
3 Incorrect 23 ms 8880 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 20 ms 8916 KB wrong parameter
6 Incorrect 26 ms 9448 KB wrong parameter
7 Incorrect 37 ms 9684 KB wrong parameter
8 Incorrect 23 ms 9228 KB wrong parameter
9 Incorrect 28 ms 9216 KB wrong parameter
10 Incorrect 23 ms 9372 KB wrong parameter
11 Incorrect 25 ms 9372 KB wrong parameter
12 Incorrect 20 ms 9340 KB wrong parameter
13 Incorrect 47 ms 9904 KB wrong parameter
14 Incorrect 20 ms 9308 KB wrong parameter
15 Incorrect 22 ms 9372 KB wrong parameter
16 Incorrect 45 ms 9752 KB wrong parameter
17 Incorrect 40 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10008 KB wrong parameter
19 Incorrect 29 ms 9704 KB wrong parameter
20 Incorrect 51 ms 10284 KB wrong parameter
21 Incorrect 58 ms 10388 KB wrong parameter
22 Incorrect 39 ms 9928 KB wrong parameter
23 Incorrect 59 ms 10536 KB wrong parameter