oj.uz

Submission #566725

# Submission time Handle Problem Language Result Execution time Memory
566725 2022-05-22T18:32:44 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 220 ms 14068 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 "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 = 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 220 ms 14068 KB wrong parameter
2 Incorrect 2 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 24 ms 8828 KB wrong parameter
4 Incorrect 2 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9088 KB wrong parameter
6 Incorrect 37 ms 9312 KB wrong parameter
7 Incorrect 39 ms 9620 KB wrong parameter
8 Incorrect 25 ms 9192 KB wrong parameter
9 Incorrect 24 ms 9448 KB wrong parameter
10 Incorrect 22 ms 9268 KB wrong parameter
11 Incorrect 25 ms 9452 KB wrong parameter
12 Incorrect 28 ms 9284 KB wrong parameter
13 Incorrect 48 ms 9760 KB wrong parameter
14 Incorrect 27 ms 9276 KB wrong parameter
15 Incorrect 22 ms 9460 KB wrong parameter
16 Incorrect 39 ms 9784 KB wrong parameter
17 Incorrect 36 ms 9700 KB wrong parameter
18 Incorrect 42 ms 10020 KB wrong parameter
19 Incorrect 28 ms 9644 KB wrong parameter
20 Incorrect 65 ms 10244 KB wrong parameter
21 Incorrect 68 ms 10360 KB wrong parameter
22 Incorrect 39 ms 9820 KB wrong parameter
23 Incorrect 60 ms 10584 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 14068 KB wrong parameter
2 Incorrect 2 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 24 ms 8828 KB wrong parameter
4 Incorrect 2 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9088 KB wrong parameter
6 Incorrect 37 ms 9312 KB wrong parameter
7 Incorrect 39 ms 9620 KB wrong parameter
8 Incorrect 25 ms 9192 KB wrong parameter
9 Incorrect 24 ms 9448 KB wrong parameter
10 Incorrect 22 ms 9268 KB wrong parameter
11 Incorrect 25 ms 9452 KB wrong parameter
12 Incorrect 28 ms 9284 KB wrong parameter
13 Incorrect 48 ms 9760 KB wrong parameter
14 Incorrect 27 ms 9276 KB wrong parameter
15 Incorrect 22 ms 9460 KB wrong parameter
16 Incorrect 39 ms 9784 KB wrong parameter
17 Incorrect 36 ms 9700 KB wrong parameter
18 Incorrect 42 ms 10020 KB wrong parameter
19 Incorrect 28 ms 9644 KB wrong parameter
20 Incorrect 65 ms 10244 KB wrong parameter
21 Incorrect 68 ms 10360 KB wrong parameter
22 Incorrect 39 ms 9820 KB wrong parameter
23 Incorrect 60 ms 10584 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 14068 KB wrong parameter
2 Incorrect 2 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 24 ms 8828 KB wrong parameter
4 Incorrect 2 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9088 KB wrong parameter
6 Incorrect 37 ms 9312 KB wrong parameter
7 Incorrect 39 ms 9620 KB wrong parameter
8 Incorrect 25 ms 9192 KB wrong parameter
9 Incorrect 24 ms 9448 KB wrong parameter
10 Incorrect 22 ms 9268 KB wrong parameter
11 Incorrect 25 ms 9452 KB wrong parameter
12 Incorrect 28 ms 9284 KB wrong parameter
13 Incorrect 48 ms 9760 KB wrong parameter
14 Incorrect 27 ms 9276 KB wrong parameter
15 Incorrect 22 ms 9460 KB wrong parameter
16 Incorrect 39 ms 9784 KB wrong parameter
17 Incorrect 36 ms 9700 KB wrong parameter
18 Incorrect 42 ms 10020 KB wrong parameter
19 Incorrect 28 ms 9644 KB wrong parameter
20 Incorrect 65 ms 10244 KB wrong parameter
21 Incorrect 68 ms 10360 KB wrong parameter
22 Incorrect 39 ms 9820 KB wrong parameter
23 Incorrect 60 ms 10584 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 14068 KB wrong parameter
2 Incorrect 2 ms 4608 KB function hops(h,c,d) must be called exactly N×H times
3 Incorrect 24 ms 8828 KB wrong parameter
4 Incorrect 2 ms 4612 KB function hops(h,c,d) must be called exactly N×H times
5 Incorrect 20 ms 9088 KB wrong parameter
6 Incorrect 37 ms 9312 KB wrong parameter
7 Incorrect 39 ms 9620 KB wrong parameter
8 Incorrect 25 ms 9192 KB wrong parameter
9 Incorrect 24 ms 9448 KB wrong parameter
10 Incorrect 22 ms 9268 KB wrong parameter
11 Incorrect 25 ms 9452 KB wrong parameter
12 Incorrect 28 ms 9284 KB wrong parameter
13 Incorrect 48 ms 9760 KB wrong parameter
14 Incorrect 27 ms 9276 KB wrong parameter
15 Incorrect 22 ms 9460 KB wrong parameter
16 Incorrect 39 ms 9784 KB wrong parameter
17 Incorrect 36 ms 9700 KB wrong parameter
18 Incorrect 42 ms 10020 KB wrong parameter
19 Incorrect 28 ms 9644 KB wrong parameter
20 Incorrect 65 ms 10244 KB wrong parameter
21 Incorrect 68 ms 10360 KB wrong parameter
22 Incorrect 39 ms 9820 KB wrong parameter
23 Incorrect 60 ms 10584 KB wrong parameter