oj.uz

Submission #566755

# Submission time Handle Problem Language Result Execution time Memory
566755 2022-05-22T19:52:16 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 189 ms 14032 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]);
        }
    }
  assert(0);

    
}

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 189 ms 14032 KB wrong parameter
2 Runtime error 6 ms 8828 KB Execution killed with signal 6
3 Incorrect 18 ms 8820 KB wrong parameter
4 Runtime error 7 ms 8848 KB Execution killed with signal 6
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9488 KB wrong parameter
7 Incorrect 35 ms 9700 KB wrong parameter
8 Incorrect 22 ms 9212 KB wrong parameter
9 Incorrect 23 ms 9404 KB wrong parameter
10 Incorrect 27 ms 9388 KB wrong parameter
11 Incorrect 25 ms 9492 KB wrong parameter
12 Incorrect 23 ms 9412 KB wrong parameter
13 Incorrect 41 ms 9848 KB wrong parameter
14 Incorrect 20 ms 9412 KB wrong parameter
15 Incorrect 28 ms 9340 KB wrong parameter
16 Incorrect 41 ms 9788 KB wrong parameter
17 Incorrect 39 ms 9864 KB wrong parameter
18 Incorrect 46 ms 10092 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 50 ms 10268 KB wrong parameter
21 Incorrect 67 ms 10384 KB wrong parameter
22 Incorrect 37 ms 9820 KB wrong parameter
23 Incorrect 66 ms 10552 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 14032 KB wrong parameter
2 Runtime error 6 ms 8828 KB Execution killed with signal 6
3 Incorrect 18 ms 8820 KB wrong parameter
4 Runtime error 7 ms 8848 KB Execution killed with signal 6
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9488 KB wrong parameter
7 Incorrect 35 ms 9700 KB wrong parameter
8 Incorrect 22 ms 9212 KB wrong parameter
9 Incorrect 23 ms 9404 KB wrong parameter
10 Incorrect 27 ms 9388 KB wrong parameter
11 Incorrect 25 ms 9492 KB wrong parameter
12 Incorrect 23 ms 9412 KB wrong parameter
13 Incorrect 41 ms 9848 KB wrong parameter
14 Incorrect 20 ms 9412 KB wrong parameter
15 Incorrect 28 ms 9340 KB wrong parameter
16 Incorrect 41 ms 9788 KB wrong parameter
17 Incorrect 39 ms 9864 KB wrong parameter
18 Incorrect 46 ms 10092 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 50 ms 10268 KB wrong parameter
21 Incorrect 67 ms 10384 KB wrong parameter
22 Incorrect 37 ms 9820 KB wrong parameter
23 Incorrect 66 ms 10552 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 14032 KB wrong parameter
2 Runtime error 6 ms 8828 KB Execution killed with signal 6
3 Incorrect 18 ms 8820 KB wrong parameter
4 Runtime error 7 ms 8848 KB Execution killed with signal 6
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9488 KB wrong parameter
7 Incorrect 35 ms 9700 KB wrong parameter
8 Incorrect 22 ms 9212 KB wrong parameter
9 Incorrect 23 ms 9404 KB wrong parameter
10 Incorrect 27 ms 9388 KB wrong parameter
11 Incorrect 25 ms 9492 KB wrong parameter
12 Incorrect 23 ms 9412 KB wrong parameter
13 Incorrect 41 ms 9848 KB wrong parameter
14 Incorrect 20 ms 9412 KB wrong parameter
15 Incorrect 28 ms 9340 KB wrong parameter
16 Incorrect 41 ms 9788 KB wrong parameter
17 Incorrect 39 ms 9864 KB wrong parameter
18 Incorrect 46 ms 10092 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 50 ms 10268 KB wrong parameter
21 Incorrect 67 ms 10384 KB wrong parameter
22 Incorrect 37 ms 9820 KB wrong parameter
23 Incorrect 66 ms 10552 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 14032 KB wrong parameter
2 Runtime error 6 ms 8828 KB Execution killed with signal 6
3 Incorrect 18 ms 8820 KB wrong parameter
4 Runtime error 7 ms 8848 KB Execution killed with signal 6
5 Incorrect 20 ms 9084 KB wrong parameter
6 Incorrect 20 ms 9488 KB wrong parameter
7 Incorrect 35 ms 9700 KB wrong parameter
8 Incorrect 22 ms 9212 KB wrong parameter
9 Incorrect 23 ms 9404 KB wrong parameter
10 Incorrect 27 ms 9388 KB wrong parameter
11 Incorrect 25 ms 9492 KB wrong parameter
12 Incorrect 23 ms 9412 KB wrong parameter
13 Incorrect 41 ms 9848 KB wrong parameter
14 Incorrect 20 ms 9412 KB wrong parameter
15 Incorrect 28 ms 9340 KB wrong parameter
16 Incorrect 41 ms 9788 KB wrong parameter
17 Incorrect 39 ms 9864 KB wrong parameter
18 Incorrect 46 ms 10092 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 50 ms 10268 KB wrong parameter
21 Incorrect 67 ms 10384 KB wrong parameter
22 Incorrect 37 ms 9820 KB wrong parameter
23 Incorrect 66 ms 10552 KB wrong parameter