oj.uz

Submission #566745

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

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14072 KB wrong parameter
2 Incorrect 2 ms 4604 KB wrong parameter
3 Incorrect 16 ms 8864 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 18 ms 9076 KB wrong parameter
6 Incorrect 23 ms 9468 KB wrong parameter
7 Incorrect 33 ms 9740 KB wrong parameter
8 Incorrect 23 ms 9192 KB wrong parameter
9 Incorrect 22 ms 9332 KB wrong parameter
10 Incorrect 20 ms 9416 KB wrong parameter
11 Incorrect 23 ms 9448 KB wrong parameter
12 Incorrect 23 ms 9364 KB wrong parameter
13 Incorrect 39 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9304 KB wrong parameter
15 Incorrect 25 ms 9296 KB wrong parameter
16 Incorrect 41 ms 9832 KB wrong parameter
17 Incorrect 42 ms 9700 KB wrong parameter
18 Incorrect 44 ms 10108 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 51 ms 10340 KB wrong parameter
21 Incorrect 76 ms 10396 KB wrong parameter
22 Incorrect 37 ms 9832 KB wrong parameter
23 Incorrect 69 ms 10552 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14072 KB wrong parameter
2 Incorrect 2 ms 4604 KB wrong parameter
3 Incorrect 16 ms 8864 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 18 ms 9076 KB wrong parameter
6 Incorrect 23 ms 9468 KB wrong parameter
7 Incorrect 33 ms 9740 KB wrong parameter
8 Incorrect 23 ms 9192 KB wrong parameter
9 Incorrect 22 ms 9332 KB wrong parameter
10 Incorrect 20 ms 9416 KB wrong parameter
11 Incorrect 23 ms 9448 KB wrong parameter
12 Incorrect 23 ms 9364 KB wrong parameter
13 Incorrect 39 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9304 KB wrong parameter
15 Incorrect 25 ms 9296 KB wrong parameter
16 Incorrect 41 ms 9832 KB wrong parameter
17 Incorrect 42 ms 9700 KB wrong parameter
18 Incorrect 44 ms 10108 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 51 ms 10340 KB wrong parameter
21 Incorrect 76 ms 10396 KB wrong parameter
22 Incorrect 37 ms 9832 KB wrong parameter
23 Incorrect 69 ms 10552 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14072 KB wrong parameter
2 Incorrect 2 ms 4604 KB wrong parameter
3 Incorrect 16 ms 8864 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 18 ms 9076 KB wrong parameter
6 Incorrect 23 ms 9468 KB wrong parameter
7 Incorrect 33 ms 9740 KB wrong parameter
8 Incorrect 23 ms 9192 KB wrong parameter
9 Incorrect 22 ms 9332 KB wrong parameter
10 Incorrect 20 ms 9416 KB wrong parameter
11 Incorrect 23 ms 9448 KB wrong parameter
12 Incorrect 23 ms 9364 KB wrong parameter
13 Incorrect 39 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9304 KB wrong parameter
15 Incorrect 25 ms 9296 KB wrong parameter
16 Incorrect 41 ms 9832 KB wrong parameter
17 Incorrect 42 ms 9700 KB wrong parameter
18 Incorrect 44 ms 10108 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 51 ms 10340 KB wrong parameter
21 Incorrect 76 ms 10396 KB wrong parameter
22 Incorrect 37 ms 9832 KB wrong parameter
23 Incorrect 69 ms 10552 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 14072 KB wrong parameter
2 Incorrect 2 ms 4604 KB wrong parameter
3 Incorrect 16 ms 8864 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 18 ms 9076 KB wrong parameter
6 Incorrect 23 ms 9468 KB wrong parameter
7 Incorrect 33 ms 9740 KB wrong parameter
8 Incorrect 23 ms 9192 KB wrong parameter
9 Incorrect 22 ms 9332 KB wrong parameter
10 Incorrect 20 ms 9416 KB wrong parameter
11 Incorrect 23 ms 9448 KB wrong parameter
12 Incorrect 23 ms 9364 KB wrong parameter
13 Incorrect 39 ms 9816 KB wrong parameter
14 Incorrect 20 ms 9304 KB wrong parameter
15 Incorrect 25 ms 9296 KB wrong parameter
16 Incorrect 41 ms 9832 KB wrong parameter
17 Incorrect 42 ms 9700 KB wrong parameter
18 Incorrect 44 ms 10108 KB wrong parameter
19 Incorrect 30 ms 9608 KB wrong parameter
20 Incorrect 51 ms 10340 KB wrong parameter
21 Incorrect 76 ms 10396 KB wrong parameter
22 Incorrect 37 ms 9832 KB wrong parameter
23 Incorrect 69 ms 10552 KB wrong parameter