oj.uz

Submission #566767

# Submission time Handle Problem Language Result Execution time Memory
566767 2022-05-22T20:05:38 Z shrimb Saveit (IOI10_saveit) C++17
0 / 100
 200 ms 14012 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 "encoder.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;
            }
        }
        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:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(j < bb.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14012 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8428 KB wrong parameter
4 Correct 3 ms 4616 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 8760 KB wrong parameter
6 Incorrect 20 ms 9476 KB wrong parameter
7 Incorrect 31 ms 9712 KB wrong parameter
8 Incorrect 26 ms 8912 KB wrong parameter
9 Incorrect 31 ms 9440 KB wrong parameter
10 Incorrect 25 ms 9536 KB wrong parameter
11 Incorrect 27 ms 9548 KB wrong parameter
12 Incorrect 22 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 25 ms 9428 KB wrong parameter
15 Incorrect 24 ms 9404 KB wrong parameter
16 Incorrect 43 ms 9916 KB wrong parameter
17 Incorrect 38 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10040 KB wrong parameter
19 Incorrect 30 ms 9520 KB wrong parameter
20 Incorrect 49 ms 10364 KB wrong parameter
21 Incorrect 60 ms 10476 KB wrong parameter
22 Incorrect 38 ms 9792 KB wrong parameter
23 Incorrect 66 ms 10520 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14012 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8428 KB wrong parameter
4 Correct 3 ms 4616 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 8760 KB wrong parameter
6 Incorrect 20 ms 9476 KB wrong parameter
7 Incorrect 31 ms 9712 KB wrong parameter
8 Incorrect 26 ms 8912 KB wrong parameter
9 Incorrect 31 ms 9440 KB wrong parameter
10 Incorrect 25 ms 9536 KB wrong parameter
11 Incorrect 27 ms 9548 KB wrong parameter
12 Incorrect 22 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 25 ms 9428 KB wrong parameter
15 Incorrect 24 ms 9404 KB wrong parameter
16 Incorrect 43 ms 9916 KB wrong parameter
17 Incorrect 38 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10040 KB wrong parameter
19 Incorrect 30 ms 9520 KB wrong parameter
20 Incorrect 49 ms 10364 KB wrong parameter
21 Incorrect 60 ms 10476 KB wrong parameter
22 Incorrect 38 ms 9792 KB wrong parameter
23 Incorrect 66 ms 10520 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14012 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8428 KB wrong parameter
4 Correct 3 ms 4616 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 8760 KB wrong parameter
6 Incorrect 20 ms 9476 KB wrong parameter
7 Incorrect 31 ms 9712 KB wrong parameter
8 Incorrect 26 ms 8912 KB wrong parameter
9 Incorrect 31 ms 9440 KB wrong parameter
10 Incorrect 25 ms 9536 KB wrong parameter
11 Incorrect 27 ms 9548 KB wrong parameter
12 Incorrect 22 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 25 ms 9428 KB wrong parameter
15 Incorrect 24 ms 9404 KB wrong parameter
16 Incorrect 43 ms 9916 KB wrong parameter
17 Incorrect 38 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10040 KB wrong parameter
19 Incorrect 30 ms 9520 KB wrong parameter
20 Incorrect 49 ms 10364 KB wrong parameter
21 Incorrect 60 ms 10476 KB wrong parameter
22 Incorrect 38 ms 9792 KB wrong parameter
23 Incorrect 66 ms 10520 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 14012 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8428 KB wrong parameter
4 Correct 3 ms 4616 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 8760 KB wrong parameter
6 Incorrect 20 ms 9476 KB wrong parameter
7 Incorrect 31 ms 9712 KB wrong parameter
8 Incorrect 26 ms 8912 KB wrong parameter
9 Incorrect 31 ms 9440 KB wrong parameter
10 Incorrect 25 ms 9536 KB wrong parameter
11 Incorrect 27 ms 9548 KB wrong parameter
12 Incorrect 22 ms 9404 KB wrong parameter
13 Incorrect 44 ms 9836 KB wrong parameter
14 Incorrect 25 ms 9428 KB wrong parameter
15 Incorrect 24 ms 9404 KB wrong parameter
16 Incorrect 43 ms 9916 KB wrong parameter
17 Incorrect 38 ms 9796 KB wrong parameter
18 Incorrect 41 ms 10040 KB wrong parameter
19 Incorrect 30 ms 9520 KB wrong parameter
20 Incorrect 49 ms 10364 KB wrong parameter
21 Incorrect 60 ms 10476 KB wrong parameter
22 Incorrect 38 ms 9792 KB wrong parameter
23 Incorrect 66 ms 10520 KB wrong parameter