oj.uz

Submission #566721

# Submission time Handle Problem Language Result Execution time Memory
566721 2022-05-22T18:10:29 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 194 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 i = 1; i < n; i++){
            int diff = pc[i] - pc[par[i]];
            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;
 
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 = 0; 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 194 ms 14084 KB wrong parameter
2 Incorrect 2 ms 4600 KB duplicate hops call
3 Incorrect 18 ms 8816 KB wrong parameter
4 Incorrect 2 ms 4612 KB duplicate hops call
5 Incorrect 19 ms 9044 KB wrong parameter
6 Incorrect 22 ms 9416 KB wrong parameter
7 Incorrect 33 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9180 KB wrong parameter
9 Incorrect 31 ms 9284 KB wrong parameter
10 Incorrect 25 ms 9324 KB wrong parameter
11 Incorrect 27 ms 9452 KB wrong parameter
12 Incorrect 20 ms 9320 KB wrong parameter
13 Incorrect 40 ms 9828 KB wrong parameter
14 Incorrect 25 ms 9336 KB wrong parameter
15 Incorrect 20 ms 9332 KB wrong parameter
16 Incorrect 44 ms 9980 KB wrong parameter
17 Incorrect 36 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10024 KB wrong parameter
19 Incorrect 34 ms 9692 KB wrong parameter
20 Incorrect 51 ms 10348 KB wrong parameter
21 Incorrect 63 ms 10396 KB wrong parameter
22 Incorrect 43 ms 9652 KB wrong parameter
23 Incorrect 64 ms 10620 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 14084 KB wrong parameter
2 Incorrect 2 ms 4600 KB duplicate hops call
3 Incorrect 18 ms 8816 KB wrong parameter
4 Incorrect 2 ms 4612 KB duplicate hops call
5 Incorrect 19 ms 9044 KB wrong parameter
6 Incorrect 22 ms 9416 KB wrong parameter
7 Incorrect 33 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9180 KB wrong parameter
9 Incorrect 31 ms 9284 KB wrong parameter
10 Incorrect 25 ms 9324 KB wrong parameter
11 Incorrect 27 ms 9452 KB wrong parameter
12 Incorrect 20 ms 9320 KB wrong parameter
13 Incorrect 40 ms 9828 KB wrong parameter
14 Incorrect 25 ms 9336 KB wrong parameter
15 Incorrect 20 ms 9332 KB wrong parameter
16 Incorrect 44 ms 9980 KB wrong parameter
17 Incorrect 36 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10024 KB wrong parameter
19 Incorrect 34 ms 9692 KB wrong parameter
20 Incorrect 51 ms 10348 KB wrong parameter
21 Incorrect 63 ms 10396 KB wrong parameter
22 Incorrect 43 ms 9652 KB wrong parameter
23 Incorrect 64 ms 10620 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 14084 KB wrong parameter
2 Incorrect 2 ms 4600 KB duplicate hops call
3 Incorrect 18 ms 8816 KB wrong parameter
4 Incorrect 2 ms 4612 KB duplicate hops call
5 Incorrect 19 ms 9044 KB wrong parameter
6 Incorrect 22 ms 9416 KB wrong parameter
7 Incorrect 33 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9180 KB wrong parameter
9 Incorrect 31 ms 9284 KB wrong parameter
10 Incorrect 25 ms 9324 KB wrong parameter
11 Incorrect 27 ms 9452 KB wrong parameter
12 Incorrect 20 ms 9320 KB wrong parameter
13 Incorrect 40 ms 9828 KB wrong parameter
14 Incorrect 25 ms 9336 KB wrong parameter
15 Incorrect 20 ms 9332 KB wrong parameter
16 Incorrect 44 ms 9980 KB wrong parameter
17 Incorrect 36 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10024 KB wrong parameter
19 Incorrect 34 ms 9692 KB wrong parameter
20 Incorrect 51 ms 10348 KB wrong parameter
21 Incorrect 63 ms 10396 KB wrong parameter
22 Incorrect 43 ms 9652 KB wrong parameter
23 Incorrect 64 ms 10620 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 14084 KB wrong parameter
2 Incorrect 2 ms 4600 KB duplicate hops call
3 Incorrect 18 ms 8816 KB wrong parameter
4 Incorrect 2 ms 4612 KB duplicate hops call
5 Incorrect 19 ms 9044 KB wrong parameter
6 Incorrect 22 ms 9416 KB wrong parameter
7 Incorrect 33 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9180 KB wrong parameter
9 Incorrect 31 ms 9284 KB wrong parameter
10 Incorrect 25 ms 9324 KB wrong parameter
11 Incorrect 27 ms 9452 KB wrong parameter
12 Incorrect 20 ms 9320 KB wrong parameter
13 Incorrect 40 ms 9828 KB wrong parameter
14 Incorrect 25 ms 9336 KB wrong parameter
15 Incorrect 20 ms 9332 KB wrong parameter
16 Incorrect 44 ms 9980 KB wrong parameter
17 Incorrect 36 ms 9764 KB wrong parameter
18 Incorrect 48 ms 10024 KB wrong parameter
19 Incorrect 34 ms 9692 KB wrong parameter
20 Incorrect 51 ms 10348 KB wrong parameter
21 Incorrect 63 ms 10396 KB wrong parameter
22 Incorrect 43 ms 9652 KB wrong parameter
23 Incorrect 64 ms 10620 KB wrong parameter