oj.uz

Submission #566726

# Submission time Handle Problem Language Result Execution time Memory
566726 2022-05-22T18:40:21 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 190 ms 14112 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>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: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 < bb.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 14112 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8828 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9008 KB wrong parameter
6 Incorrect 27 ms 9448 KB wrong parameter
7 Incorrect 39 ms 9744 KB wrong parameter
8 Incorrect 19 ms 9208 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 26 ms 9332 KB wrong parameter
11 Incorrect 25 ms 9476 KB wrong parameter
12 Incorrect 27 ms 9284 KB wrong parameter
13 Incorrect 45 ms 10000 KB wrong parameter
14 Incorrect 20 ms 9316 KB wrong parameter
15 Incorrect 19 ms 9300 KB wrong parameter
16 Incorrect 40 ms 9860 KB wrong parameter
17 Incorrect 34 ms 9820 KB wrong parameter
18 Incorrect 47 ms 10052 KB wrong parameter
19 Incorrect 32 ms 9508 KB wrong parameter
20 Incorrect 54 ms 10292 KB wrong parameter
21 Incorrect 63 ms 10400 KB wrong parameter
22 Incorrect 35 ms 9984 KB wrong parameter
23 Incorrect 66 ms 10540 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 14112 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8828 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9008 KB wrong parameter
6 Incorrect 27 ms 9448 KB wrong parameter
7 Incorrect 39 ms 9744 KB wrong parameter
8 Incorrect 19 ms 9208 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 26 ms 9332 KB wrong parameter
11 Incorrect 25 ms 9476 KB wrong parameter
12 Incorrect 27 ms 9284 KB wrong parameter
13 Incorrect 45 ms 10000 KB wrong parameter
14 Incorrect 20 ms 9316 KB wrong parameter
15 Incorrect 19 ms 9300 KB wrong parameter
16 Incorrect 40 ms 9860 KB wrong parameter
17 Incorrect 34 ms 9820 KB wrong parameter
18 Incorrect 47 ms 10052 KB wrong parameter
19 Incorrect 32 ms 9508 KB wrong parameter
20 Incorrect 54 ms 10292 KB wrong parameter
21 Incorrect 63 ms 10400 KB wrong parameter
22 Incorrect 35 ms 9984 KB wrong parameter
23 Incorrect 66 ms 10540 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 14112 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8828 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9008 KB wrong parameter
6 Incorrect 27 ms 9448 KB wrong parameter
7 Incorrect 39 ms 9744 KB wrong parameter
8 Incorrect 19 ms 9208 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 26 ms 9332 KB wrong parameter
11 Incorrect 25 ms 9476 KB wrong parameter
12 Incorrect 27 ms 9284 KB wrong parameter
13 Incorrect 45 ms 10000 KB wrong parameter
14 Incorrect 20 ms 9316 KB wrong parameter
15 Incorrect 19 ms 9300 KB wrong parameter
16 Incorrect 40 ms 9860 KB wrong parameter
17 Incorrect 34 ms 9820 KB wrong parameter
18 Incorrect 47 ms 10052 KB wrong parameter
19 Incorrect 32 ms 9508 KB wrong parameter
20 Incorrect 54 ms 10292 KB wrong parameter
21 Incorrect 63 ms 10400 KB wrong parameter
22 Incorrect 35 ms 9984 KB wrong parameter
23 Incorrect 66 ms 10540 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 14112 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8828 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9008 KB wrong parameter
6 Incorrect 27 ms 9448 KB wrong parameter
7 Incorrect 39 ms 9744 KB wrong parameter
8 Incorrect 19 ms 9208 KB wrong parameter
9 Incorrect 26 ms 9320 KB wrong parameter
10 Incorrect 26 ms 9332 KB wrong parameter
11 Incorrect 25 ms 9476 KB wrong parameter
12 Incorrect 27 ms 9284 KB wrong parameter
13 Incorrect 45 ms 10000 KB wrong parameter
14 Incorrect 20 ms 9316 KB wrong parameter
15 Incorrect 19 ms 9300 KB wrong parameter
16 Incorrect 40 ms 9860 KB wrong parameter
17 Incorrect 34 ms 9820 KB wrong parameter
18 Incorrect 47 ms 10052 KB wrong parameter
19 Incorrect 32 ms 9508 KB wrong parameter
20 Incorrect 54 ms 10292 KB wrong parameter
21 Incorrect 63 ms 10400 KB wrong parameter
22 Incorrect 35 ms 9984 KB wrong parameter
23 Incorrect 66 ms 10540 KB wrong parameter