oj.uz

Submission #566757

# Submission time Handle Problem Language Result Execution time Memory
566757 2022-05-22T19:54:10 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 185 ms 14048 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 "encoder.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]);
        }
    }
    
}

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 185 ms 14048 KB Output isn't correct
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 8948 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 24 ms 9092 KB Output isn't correct
6 Incorrect 28 ms 9412 KB Output isn't correct
7 Incorrect 37 ms 9776 KB Output isn't correct
8 Incorrect 22 ms 9216 KB Output isn't correct
9 Incorrect 23 ms 9452 KB Output isn't correct
10 Incorrect 25 ms 9544 KB Output isn't correct
11 Incorrect 33 ms 9392 KB Output isn't correct
12 Incorrect 22 ms 9484 KB Output isn't correct
13 Incorrect 40 ms 9860 KB Output isn't correct
14 Incorrect 26 ms 9428 KB Output isn't correct
15 Incorrect 24 ms 9312 KB Output isn't correct
16 Incorrect 40 ms 9816 KB Output isn't correct
17 Incorrect 40 ms 9832 KB Output isn't correct
18 Incorrect 51 ms 10164 KB Output isn't correct
19 Incorrect 30 ms 9572 KB Output isn't correct
20 Incorrect 55 ms 10476 KB Output isn't correct
21 Incorrect 64 ms 10384 KB Output isn't correct
22 Incorrect 39 ms 9852 KB Output isn't correct
23 Incorrect 63 ms 10940 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 14048 KB Output isn't correct
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 8948 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 24 ms 9092 KB Output isn't correct
6 Incorrect 28 ms 9412 KB Output isn't correct
7 Incorrect 37 ms 9776 KB Output isn't correct
8 Incorrect 22 ms 9216 KB Output isn't correct
9 Incorrect 23 ms 9452 KB Output isn't correct
10 Incorrect 25 ms 9544 KB Output isn't correct
11 Incorrect 33 ms 9392 KB Output isn't correct
12 Incorrect 22 ms 9484 KB Output isn't correct
13 Incorrect 40 ms 9860 KB Output isn't correct
14 Incorrect 26 ms 9428 KB Output isn't correct
15 Incorrect 24 ms 9312 KB Output isn't correct
16 Incorrect 40 ms 9816 KB Output isn't correct
17 Incorrect 40 ms 9832 KB Output isn't correct
18 Incorrect 51 ms 10164 KB Output isn't correct
19 Incorrect 30 ms 9572 KB Output isn't correct
20 Incorrect 55 ms 10476 KB Output isn't correct
21 Incorrect 64 ms 10384 KB Output isn't correct
22 Incorrect 39 ms 9852 KB Output isn't correct
23 Incorrect 63 ms 10940 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 14048 KB Output isn't correct
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 8948 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 24 ms 9092 KB Output isn't correct
6 Incorrect 28 ms 9412 KB Output isn't correct
7 Incorrect 37 ms 9776 KB Output isn't correct
8 Incorrect 22 ms 9216 KB Output isn't correct
9 Incorrect 23 ms 9452 KB Output isn't correct
10 Incorrect 25 ms 9544 KB Output isn't correct
11 Incorrect 33 ms 9392 KB Output isn't correct
12 Incorrect 22 ms 9484 KB Output isn't correct
13 Incorrect 40 ms 9860 KB Output isn't correct
14 Incorrect 26 ms 9428 KB Output isn't correct
15 Incorrect 24 ms 9312 KB Output isn't correct
16 Incorrect 40 ms 9816 KB Output isn't correct
17 Incorrect 40 ms 9832 KB Output isn't correct
18 Incorrect 51 ms 10164 KB Output isn't correct
19 Incorrect 30 ms 9572 KB Output isn't correct
20 Incorrect 55 ms 10476 KB Output isn't correct
21 Incorrect 64 ms 10384 KB Output isn't correct
22 Incorrect 39 ms 9852 KB Output isn't correct
23 Incorrect 63 ms 10940 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 14048 KB Output isn't correct
2 Incorrect 3 ms 4604 KB Output isn't correct
3 Incorrect 19 ms 8948 KB Output isn't correct
4 Incorrect 2 ms 4612 KB Output isn't correct
5 Incorrect 24 ms 9092 KB Output isn't correct
6 Incorrect 28 ms 9412 KB Output isn't correct
7 Incorrect 37 ms 9776 KB Output isn't correct
8 Incorrect 22 ms 9216 KB Output isn't correct
9 Incorrect 23 ms 9452 KB Output isn't correct
10 Incorrect 25 ms 9544 KB Output isn't correct
11 Incorrect 33 ms 9392 KB Output isn't correct
12 Incorrect 22 ms 9484 KB Output isn't correct
13 Incorrect 40 ms 9860 KB Output isn't correct
14 Incorrect 26 ms 9428 KB Output isn't correct
15 Incorrect 24 ms 9312 KB Output isn't correct
16 Incorrect 40 ms 9816 KB Output isn't correct
17 Incorrect 40 ms 9832 KB Output isn't correct
18 Incorrect 51 ms 10164 KB Output isn't correct
19 Incorrect 30 ms 9572 KB Output isn't correct
20 Incorrect 55 ms 10476 KB Output isn't correct
21 Incorrect 64 ms 10384 KB Output isn't correct
22 Incorrect 39 ms 9852 KB Output isn't correct
23 Incorrect 63 ms 10940 KB Output isn't correct