oj.uz

Submission #566775

# Submission time Handle Problem Language Result Execution time Memory
566775 2022-05-22T20:32:06 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 199 ms 18944 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
 
using namespace std;
 
 
 
 
void encode(int n, int h, int p, int a[], int b[]){
 
    vector<int>adj[1001];
 
 
    int dis[1001],par[1001];
    for(int i = 0; i < n; i++) {
        dis[i] = INT_MAX;
    }
    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;
 
 
void decode(int n, int h){
    int dis[1001],p[1001],j;
    vector<int> diff[1001];
    vector<int>adj[1001];
 
 
    j = 0;
    for(int i = 0; i < n; i++) {
        diff[i].resize(n);
        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;
    }
    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;
              	b.push_back(dis[s]);
            }
        }
        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:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(j < d.size()){
      |           ~~^~~~~~~~~~
encoder.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while(j < b.size()){
      |               ~~^~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while(j < b.size()){
      |           ~~^~~~~~~~~~
decoder.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while(j < bb.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 14056 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Runtime error 27 ms 16132 KB Execution killed with signal 11
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8684 KB wrong parameter
6 Runtime error 33 ms 18004 KB Execution killed with signal 11
7 Incorrect 31 ms 9696 KB wrong parameter
8 Runtime error 27 ms 17256 KB Execution killed with signal 11
9 Runtime error 34 ms 17980 KB Execution killed with signal 11
10 Runtime error 30 ms 18068 KB Execution killed with signal 11
11 Runtime error 41 ms 18172 KB Execution killed with signal 11
12 Runtime error 31 ms 17908 KB Execution killed with signal 11
13 Incorrect 49 ms 9932 KB wrong parameter
14 Runtime error 30 ms 17840 KB Execution killed with signal 11
15 Runtime error 33 ms 18044 KB Execution killed with signal 11
16 Runtime error 49 ms 18308 KB Execution killed with signal 11
17 Runtime error 43 ms 18332 KB Execution killed with signal 11
18 Incorrect 45 ms 10232 KB wrong parameter
19 Incorrect 26 ms 9616 KB wrong parameter
20 Runtime error 60 ms 18836 KB Execution killed with signal 11
21 Incorrect 59 ms 10332 KB wrong parameter
22 Incorrect 41 ms 9760 KB wrong parameter
23 Runtime error 70 ms 18944 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 14056 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Runtime error 27 ms 16132 KB Execution killed with signal 11
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8684 KB wrong parameter
6 Runtime error 33 ms 18004 KB Execution killed with signal 11
7 Incorrect 31 ms 9696 KB wrong parameter
8 Runtime error 27 ms 17256 KB Execution killed with signal 11
9 Runtime error 34 ms 17980 KB Execution killed with signal 11
10 Runtime error 30 ms 18068 KB Execution killed with signal 11
11 Runtime error 41 ms 18172 KB Execution killed with signal 11
12 Runtime error 31 ms 17908 KB Execution killed with signal 11
13 Incorrect 49 ms 9932 KB wrong parameter
14 Runtime error 30 ms 17840 KB Execution killed with signal 11
15 Runtime error 33 ms 18044 KB Execution killed with signal 11
16 Runtime error 49 ms 18308 KB Execution killed with signal 11
17 Runtime error 43 ms 18332 KB Execution killed with signal 11
18 Incorrect 45 ms 10232 KB wrong parameter
19 Incorrect 26 ms 9616 KB wrong parameter
20 Runtime error 60 ms 18836 KB Execution killed with signal 11
21 Incorrect 59 ms 10332 KB wrong parameter
22 Incorrect 41 ms 9760 KB wrong parameter
23 Runtime error 70 ms 18944 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 14056 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Runtime error 27 ms 16132 KB Execution killed with signal 11
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8684 KB wrong parameter
6 Runtime error 33 ms 18004 KB Execution killed with signal 11
7 Incorrect 31 ms 9696 KB wrong parameter
8 Runtime error 27 ms 17256 KB Execution killed with signal 11
9 Runtime error 34 ms 17980 KB Execution killed with signal 11
10 Runtime error 30 ms 18068 KB Execution killed with signal 11
11 Runtime error 41 ms 18172 KB Execution killed with signal 11
12 Runtime error 31 ms 17908 KB Execution killed with signal 11
13 Incorrect 49 ms 9932 KB wrong parameter
14 Runtime error 30 ms 17840 KB Execution killed with signal 11
15 Runtime error 33 ms 18044 KB Execution killed with signal 11
16 Runtime error 49 ms 18308 KB Execution killed with signal 11
17 Runtime error 43 ms 18332 KB Execution killed with signal 11
18 Incorrect 45 ms 10232 KB wrong parameter
19 Incorrect 26 ms 9616 KB wrong parameter
20 Runtime error 60 ms 18836 KB Execution killed with signal 11
21 Incorrect 59 ms 10332 KB wrong parameter
22 Incorrect 41 ms 9760 KB wrong parameter
23 Runtime error 70 ms 18944 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 14056 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Runtime error 27 ms 16132 KB Execution killed with signal 11
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 22 ms 8684 KB wrong parameter
6 Runtime error 33 ms 18004 KB Execution killed with signal 11
7 Incorrect 31 ms 9696 KB wrong parameter
8 Runtime error 27 ms 17256 KB Execution killed with signal 11
9 Runtime error 34 ms 17980 KB Execution killed with signal 11
10 Runtime error 30 ms 18068 KB Execution killed with signal 11
11 Runtime error 41 ms 18172 KB Execution killed with signal 11
12 Runtime error 31 ms 17908 KB Execution killed with signal 11
13 Incorrect 49 ms 9932 KB wrong parameter
14 Runtime error 30 ms 17840 KB Execution killed with signal 11
15 Runtime error 33 ms 18044 KB Execution killed with signal 11
16 Runtime error 49 ms 18308 KB Execution killed with signal 11
17 Runtime error 43 ms 18332 KB Execution killed with signal 11
18 Incorrect 45 ms 10232 KB wrong parameter
19 Incorrect 26 ms 9616 KB wrong parameter
20 Runtime error 60 ms 18836 KB Execution killed with signal 11
21 Incorrect 59 ms 10332 KB wrong parameter
22 Incorrect 41 ms 9760 KB wrong parameter
23 Runtime error 70 ms 18944 KB Execution killed with signal 11