oj.uz

Submission #566753

# Submission time Handle Problem Language Result Execution time Memory
566753 2022-05-22T19:48:03 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 210 ms 14148 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
 
using namespace std;
 
vector<int>adj[1001];
 
 
int dis[1001],par[1001];
void re(int n){
    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[]){
    
    re(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};
    int j = 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] = 0;
        int 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 re(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){
    
    re(n);
    for(int i = 1; i < n; i++){
        int parent = 0;
        for(int k = 0; k < 10; k++){
            if(decode_bit()) parent += (1 << k);
        }
        p[i] = parent;
        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++){
            if(!decode_bit()){
                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:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while(j < b.size()){
      |               ~~^~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:36:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     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 210 ms 14148 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 20 ms 8748 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 19 ms 8952 KB wrong parameter
6 Incorrect 24 ms 9448 KB wrong parameter
7 Incorrect 35 ms 9636 KB wrong parameter
8 Incorrect 22 ms 9208 KB wrong parameter
9 Incorrect 22 ms 9296 KB wrong parameter
10 Incorrect 23 ms 9340 KB wrong parameter
11 Incorrect 26 ms 9448 KB wrong parameter
12 Incorrect 24 ms 9360 KB wrong parameter
13 Incorrect 42 ms 9904 KB wrong parameter
14 Incorrect 25 ms 9300 KB wrong parameter
15 Incorrect 30 ms 9384 KB wrong parameter
16 Incorrect 44 ms 9728 KB wrong parameter
17 Incorrect 38 ms 9836 KB wrong parameter
18 Incorrect 40 ms 10048 KB wrong parameter
19 Incorrect 31 ms 9528 KB wrong parameter
20 Incorrect 54 ms 10348 KB wrong parameter
21 Incorrect 58 ms 10384 KB wrong parameter
22 Incorrect 40 ms 9816 KB wrong parameter
23 Incorrect 61 ms 10552 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 14148 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 20 ms 8748 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 19 ms 8952 KB wrong parameter
6 Incorrect 24 ms 9448 KB wrong parameter
7 Incorrect 35 ms 9636 KB wrong parameter
8 Incorrect 22 ms 9208 KB wrong parameter
9 Incorrect 22 ms 9296 KB wrong parameter
10 Incorrect 23 ms 9340 KB wrong parameter
11 Incorrect 26 ms 9448 KB wrong parameter
12 Incorrect 24 ms 9360 KB wrong parameter
13 Incorrect 42 ms 9904 KB wrong parameter
14 Incorrect 25 ms 9300 KB wrong parameter
15 Incorrect 30 ms 9384 KB wrong parameter
16 Incorrect 44 ms 9728 KB wrong parameter
17 Incorrect 38 ms 9836 KB wrong parameter
18 Incorrect 40 ms 10048 KB wrong parameter
19 Incorrect 31 ms 9528 KB wrong parameter
20 Incorrect 54 ms 10348 KB wrong parameter
21 Incorrect 58 ms 10384 KB wrong parameter
22 Incorrect 40 ms 9816 KB wrong parameter
23 Incorrect 61 ms 10552 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 14148 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 20 ms 8748 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 19 ms 8952 KB wrong parameter
6 Incorrect 24 ms 9448 KB wrong parameter
7 Incorrect 35 ms 9636 KB wrong parameter
8 Incorrect 22 ms 9208 KB wrong parameter
9 Incorrect 22 ms 9296 KB wrong parameter
10 Incorrect 23 ms 9340 KB wrong parameter
11 Incorrect 26 ms 9448 KB wrong parameter
12 Incorrect 24 ms 9360 KB wrong parameter
13 Incorrect 42 ms 9904 KB wrong parameter
14 Incorrect 25 ms 9300 KB wrong parameter
15 Incorrect 30 ms 9384 KB wrong parameter
16 Incorrect 44 ms 9728 KB wrong parameter
17 Incorrect 38 ms 9836 KB wrong parameter
18 Incorrect 40 ms 10048 KB wrong parameter
19 Incorrect 31 ms 9528 KB wrong parameter
20 Incorrect 54 ms 10348 KB wrong parameter
21 Incorrect 58 ms 10384 KB wrong parameter
22 Incorrect 40 ms 9816 KB wrong parameter
23 Incorrect 61 ms 10552 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 14148 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 20 ms 8748 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 19 ms 8952 KB wrong parameter
6 Incorrect 24 ms 9448 KB wrong parameter
7 Incorrect 35 ms 9636 KB wrong parameter
8 Incorrect 22 ms 9208 KB wrong parameter
9 Incorrect 22 ms 9296 KB wrong parameter
10 Incorrect 23 ms 9340 KB wrong parameter
11 Incorrect 26 ms 9448 KB wrong parameter
12 Incorrect 24 ms 9360 KB wrong parameter
13 Incorrect 42 ms 9904 KB wrong parameter
14 Incorrect 25 ms 9300 KB wrong parameter
15 Incorrect 30 ms 9384 KB wrong parameter
16 Incorrect 44 ms 9728 KB wrong parameter
17 Incorrect 38 ms 9836 KB wrong parameter
18 Incorrect 40 ms 10048 KB wrong parameter
19 Incorrect 31 ms 9528 KB wrong parameter
20 Incorrect 54 ms 10348 KB wrong parameter
21 Incorrect 58 ms 10384 KB wrong parameter
22 Incorrect 40 ms 9816 KB wrong parameter
23 Incorrect 61 ms 10552 KB wrong parameter