oj.uz

Submission #566764

# Submission time Handle Problem Language Result Execution time Memory
566764 2022-05-22T20:02:55 Z shrimb Saveit (IOI10_saveit) C++17
0 / 100
 215 ms 13984 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;

vector<int>adj[1001];


int dis[1001],p[1001],diff[1001][1001],j;

void decode(int n, int h){
    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;
    }
    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:32:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(j < b.size()){
      |           ~~^~~~~~~~~~
decoder.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while(j < bb.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 13984 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 18 ms 8812 KB wrong parameter
4 Incorrect 2 ms 4672 KB wrong parameter
5 Incorrect 24 ms 9028 KB wrong parameter
6 Incorrect 25 ms 9464 KB wrong parameter
7 Incorrect 34 ms 9644 KB wrong parameter
8 Incorrect 25 ms 9184 KB wrong parameter
9 Incorrect 23 ms 9248 KB wrong parameter
10 Incorrect 26 ms 9340 KB wrong parameter
11 Incorrect 25 ms 9528 KB wrong parameter
12 Incorrect 25 ms 9332 KB wrong parameter
13 Incorrect 35 ms 9932 KB wrong parameter
14 Incorrect 22 ms 9292 KB wrong parameter
15 Incorrect 23 ms 9276 KB wrong parameter
16 Incorrect 44 ms 9724 KB wrong parameter
17 Incorrect 41 ms 9800 KB wrong parameter
18 Incorrect 45 ms 10068 KB wrong parameter
19 Incorrect 36 ms 9496 KB wrong parameter
20 Incorrect 56 ms 10260 KB wrong parameter
21 Incorrect 56 ms 10292 KB wrong parameter
22 Incorrect 39 ms 9788 KB wrong parameter
23 Incorrect 70 ms 10640 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 13984 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 18 ms 8812 KB wrong parameter
4 Incorrect 2 ms 4672 KB wrong parameter
5 Incorrect 24 ms 9028 KB wrong parameter
6 Incorrect 25 ms 9464 KB wrong parameter
7 Incorrect 34 ms 9644 KB wrong parameter
8 Incorrect 25 ms 9184 KB wrong parameter
9 Incorrect 23 ms 9248 KB wrong parameter
10 Incorrect 26 ms 9340 KB wrong parameter
11 Incorrect 25 ms 9528 KB wrong parameter
12 Incorrect 25 ms 9332 KB wrong parameter
13 Incorrect 35 ms 9932 KB wrong parameter
14 Incorrect 22 ms 9292 KB wrong parameter
15 Incorrect 23 ms 9276 KB wrong parameter
16 Incorrect 44 ms 9724 KB wrong parameter
17 Incorrect 41 ms 9800 KB wrong parameter
18 Incorrect 45 ms 10068 KB wrong parameter
19 Incorrect 36 ms 9496 KB wrong parameter
20 Incorrect 56 ms 10260 KB wrong parameter
21 Incorrect 56 ms 10292 KB wrong parameter
22 Incorrect 39 ms 9788 KB wrong parameter
23 Incorrect 70 ms 10640 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 13984 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 18 ms 8812 KB wrong parameter
4 Incorrect 2 ms 4672 KB wrong parameter
5 Incorrect 24 ms 9028 KB wrong parameter
6 Incorrect 25 ms 9464 KB wrong parameter
7 Incorrect 34 ms 9644 KB wrong parameter
8 Incorrect 25 ms 9184 KB wrong parameter
9 Incorrect 23 ms 9248 KB wrong parameter
10 Incorrect 26 ms 9340 KB wrong parameter
11 Incorrect 25 ms 9528 KB wrong parameter
12 Incorrect 25 ms 9332 KB wrong parameter
13 Incorrect 35 ms 9932 KB wrong parameter
14 Incorrect 22 ms 9292 KB wrong parameter
15 Incorrect 23 ms 9276 KB wrong parameter
16 Incorrect 44 ms 9724 KB wrong parameter
17 Incorrect 41 ms 9800 KB wrong parameter
18 Incorrect 45 ms 10068 KB wrong parameter
19 Incorrect 36 ms 9496 KB wrong parameter
20 Incorrect 56 ms 10260 KB wrong parameter
21 Incorrect 56 ms 10292 KB wrong parameter
22 Incorrect 39 ms 9788 KB wrong parameter
23 Incorrect 70 ms 10640 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 13984 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 18 ms 8812 KB wrong parameter
4 Incorrect 2 ms 4672 KB wrong parameter
5 Incorrect 24 ms 9028 KB wrong parameter
6 Incorrect 25 ms 9464 KB wrong parameter
7 Incorrect 34 ms 9644 KB wrong parameter
8 Incorrect 25 ms 9184 KB wrong parameter
9 Incorrect 23 ms 9248 KB wrong parameter
10 Incorrect 26 ms 9340 KB wrong parameter
11 Incorrect 25 ms 9528 KB wrong parameter
12 Incorrect 25 ms 9332 KB wrong parameter
13 Incorrect 35 ms 9932 KB wrong parameter
14 Incorrect 22 ms 9292 KB wrong parameter
15 Incorrect 23 ms 9276 KB wrong parameter
16 Incorrect 44 ms 9724 KB wrong parameter
17 Incorrect 41 ms 9800 KB wrong parameter
18 Incorrect 45 ms 10068 KB wrong parameter
19 Incorrect 36 ms 9496 KB wrong parameter
20 Incorrect 56 ms 10260 KB wrong parameter
21 Incorrect 56 ms 10292 KB wrong parameter
22 Incorrect 39 ms 9788 KB wrong parameter
23 Incorrect 70 ms 10640 KB wrong parameter