oj.uz

Submission #566724

# Submission time Handle Problem Language Result Execution time Memory
566724 2022-05-22T18:27:12 Z birthdaycake Saveit (IOI10_saveit) C++14
0 / 100
 203 ms 14084 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:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while(j < b.size()){
      |               ~~^~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14084 KB wrong parameter
2 Incorrect 3 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 20 ms 8820 KB wrong parameter
4 Incorrect 3 ms 4604 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9448 KB wrong parameter
7 Incorrect 32 ms 9760 KB wrong parameter
8 Incorrect 19 ms 9200 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 25 ms 9252 KB wrong parameter
11 Incorrect 31 ms 9556 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 48 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9276 KB wrong parameter
15 Incorrect 23 ms 9344 KB wrong parameter
16 Incorrect 39 ms 9748 KB wrong parameter
17 Incorrect 35 ms 9780 KB wrong parameter
18 Incorrect 45 ms 10052 KB wrong parameter
19 Incorrect 30 ms 9560 KB wrong parameter
20 Incorrect 52 ms 10316 KB wrong parameter
21 Incorrect 58 ms 10380 KB wrong parameter
22 Incorrect 39 ms 9764 KB wrong parameter
23 Incorrect 65 ms 10596 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14084 KB wrong parameter
2 Incorrect 3 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 20 ms 8820 KB wrong parameter
4 Incorrect 3 ms 4604 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9448 KB wrong parameter
7 Incorrect 32 ms 9760 KB wrong parameter
8 Incorrect 19 ms 9200 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 25 ms 9252 KB wrong parameter
11 Incorrect 31 ms 9556 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 48 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9276 KB wrong parameter
15 Incorrect 23 ms 9344 KB wrong parameter
16 Incorrect 39 ms 9748 KB wrong parameter
17 Incorrect 35 ms 9780 KB wrong parameter
18 Incorrect 45 ms 10052 KB wrong parameter
19 Incorrect 30 ms 9560 KB wrong parameter
20 Incorrect 52 ms 10316 KB wrong parameter
21 Incorrect 58 ms 10380 KB wrong parameter
22 Incorrect 39 ms 9764 KB wrong parameter
23 Incorrect 65 ms 10596 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14084 KB wrong parameter
2 Incorrect 3 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 20 ms 8820 KB wrong parameter
4 Incorrect 3 ms 4604 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9448 KB wrong parameter
7 Incorrect 32 ms 9760 KB wrong parameter
8 Incorrect 19 ms 9200 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 25 ms 9252 KB wrong parameter
11 Incorrect 31 ms 9556 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 48 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9276 KB wrong parameter
15 Incorrect 23 ms 9344 KB wrong parameter
16 Incorrect 39 ms 9748 KB wrong parameter
17 Incorrect 35 ms 9780 KB wrong parameter
18 Incorrect 45 ms 10052 KB wrong parameter
19 Incorrect 30 ms 9560 KB wrong parameter
20 Incorrect 52 ms 10316 KB wrong parameter
21 Incorrect 58 ms 10380 KB wrong parameter
22 Incorrect 39 ms 9764 KB wrong parameter
23 Incorrect 65 ms 10596 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14084 KB wrong parameter
2 Incorrect 3 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 20 ms 8820 KB wrong parameter
4 Incorrect 3 ms 4604 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9448 KB wrong parameter
7 Incorrect 32 ms 9760 KB wrong parameter
8 Incorrect 19 ms 9200 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 25 ms 9252 KB wrong parameter
11 Incorrect 31 ms 9556 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 48 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9276 KB wrong parameter
15 Incorrect 23 ms 9344 KB wrong parameter
16 Incorrect 39 ms 9748 KB wrong parameter
17 Incorrect 35 ms 9780 KB wrong parameter
18 Incorrect 45 ms 10052 KB wrong parameter
19 Incorrect 30 ms 9560 KB wrong parameter
20 Incorrect 52 ms 10316 KB wrong parameter
21 Incorrect 58 ms 10380 KB wrong parameter
22 Incorrect 39 ms 9764 KB wrong parameter
23 Incorrect 65 ms 10596 KB wrong parameter