oj.uz

Submission #566759

# Submission time Handle Problem Language Result Execution time Memory
566759 2022-05-22T19:55:47 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 197 ms 14024 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];
    //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;
 


void decode(int n, int h){
    
  vector<int>adj[1001];
 
 
int dis[1001],p[1001],diff[1001][1001],j;
    //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:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while(j < d.size()){
      |           ~~^~~~~~~~~~
encoder.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(j < b.size()){
      |               ~~^~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:27:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while(j < b.size()){
      |           ~~^~~~~~~~~~
decoder.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while(j < bb.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 14024 KB Output isn't correct
2 Incorrect 3 ms 8572 KB Output isn't correct
3 Incorrect 22 ms 9180 KB Output isn't correct
4 Incorrect 3 ms 8572 KB Output isn't correct
5 Incorrect 24 ms 9420 KB Output isn't correct
6 Incorrect 25 ms 9392 KB Output isn't correct
7 Incorrect 43 ms 9660 KB Output isn't correct
8 Incorrect 23 ms 9332 KB Output isn't correct
9 Incorrect 24 ms 9340 KB Output isn't correct
10 Incorrect 24 ms 9284 KB Output isn't correct
11 Incorrect 28 ms 9536 KB Output isn't correct
12 Incorrect 25 ms 9460 KB Output isn't correct
13 Incorrect 50 ms 9760 KB Output isn't correct
14 Incorrect 27 ms 9444 KB Output isn't correct
15 Incorrect 31 ms 9320 KB Output isn't correct
16 Incorrect 49 ms 10020 KB Output isn't correct
17 Incorrect 40 ms 9760 KB Output isn't correct
18 Incorrect 47 ms 10180 KB Output isn't correct
19 Incorrect 35 ms 9528 KB Output isn't correct
20 Incorrect 61 ms 10472 KB Output isn't correct
21 Incorrect 59 ms 10480 KB Output isn't correct
22 Incorrect 39 ms 9856 KB Output isn't correct
23 Incorrect 62 ms 10684 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 14024 KB Output isn't correct
2 Incorrect 3 ms 8572 KB Output isn't correct
3 Incorrect 22 ms 9180 KB Output isn't correct
4 Incorrect 3 ms 8572 KB Output isn't correct
5 Incorrect 24 ms 9420 KB Output isn't correct
6 Incorrect 25 ms 9392 KB Output isn't correct
7 Incorrect 43 ms 9660 KB Output isn't correct
8 Incorrect 23 ms 9332 KB Output isn't correct
9 Incorrect 24 ms 9340 KB Output isn't correct
10 Incorrect 24 ms 9284 KB Output isn't correct
11 Incorrect 28 ms 9536 KB Output isn't correct
12 Incorrect 25 ms 9460 KB Output isn't correct
13 Incorrect 50 ms 9760 KB Output isn't correct
14 Incorrect 27 ms 9444 KB Output isn't correct
15 Incorrect 31 ms 9320 KB Output isn't correct
16 Incorrect 49 ms 10020 KB Output isn't correct
17 Incorrect 40 ms 9760 KB Output isn't correct
18 Incorrect 47 ms 10180 KB Output isn't correct
19 Incorrect 35 ms 9528 KB Output isn't correct
20 Incorrect 61 ms 10472 KB Output isn't correct
21 Incorrect 59 ms 10480 KB Output isn't correct
22 Incorrect 39 ms 9856 KB Output isn't correct
23 Incorrect 62 ms 10684 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 14024 KB Output isn't correct
2 Incorrect 3 ms 8572 KB Output isn't correct
3 Incorrect 22 ms 9180 KB Output isn't correct
4 Incorrect 3 ms 8572 KB Output isn't correct
5 Incorrect 24 ms 9420 KB Output isn't correct
6 Incorrect 25 ms 9392 KB Output isn't correct
7 Incorrect 43 ms 9660 KB Output isn't correct
8 Incorrect 23 ms 9332 KB Output isn't correct
9 Incorrect 24 ms 9340 KB Output isn't correct
10 Incorrect 24 ms 9284 KB Output isn't correct
11 Incorrect 28 ms 9536 KB Output isn't correct
12 Incorrect 25 ms 9460 KB Output isn't correct
13 Incorrect 50 ms 9760 KB Output isn't correct
14 Incorrect 27 ms 9444 KB Output isn't correct
15 Incorrect 31 ms 9320 KB Output isn't correct
16 Incorrect 49 ms 10020 KB Output isn't correct
17 Incorrect 40 ms 9760 KB Output isn't correct
18 Incorrect 47 ms 10180 KB Output isn't correct
19 Incorrect 35 ms 9528 KB Output isn't correct
20 Incorrect 61 ms 10472 KB Output isn't correct
21 Incorrect 59 ms 10480 KB Output isn't correct
22 Incorrect 39 ms 9856 KB Output isn't correct
23 Incorrect 62 ms 10684 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 14024 KB Output isn't correct
2 Incorrect 3 ms 8572 KB Output isn't correct
3 Incorrect 22 ms 9180 KB Output isn't correct
4 Incorrect 3 ms 8572 KB Output isn't correct
5 Incorrect 24 ms 9420 KB Output isn't correct
6 Incorrect 25 ms 9392 KB Output isn't correct
7 Incorrect 43 ms 9660 KB Output isn't correct
8 Incorrect 23 ms 9332 KB Output isn't correct
9 Incorrect 24 ms 9340 KB Output isn't correct
10 Incorrect 24 ms 9284 KB Output isn't correct
11 Incorrect 28 ms 9536 KB Output isn't correct
12 Incorrect 25 ms 9460 KB Output isn't correct
13 Incorrect 50 ms 9760 KB Output isn't correct
14 Incorrect 27 ms 9444 KB Output isn't correct
15 Incorrect 31 ms 9320 KB Output isn't correct
16 Incorrect 49 ms 10020 KB Output isn't correct
17 Incorrect 40 ms 9760 KB Output isn't correct
18 Incorrect 47 ms 10180 KB Output isn't correct
19 Incorrect 35 ms 9528 KB Output isn't correct
20 Incorrect 61 ms 10472 KB Output isn't correct
21 Incorrect 59 ms 10480 KB Output isn't correct
22 Incorrect 39 ms 9856 KB Output isn't correct
23 Incorrect 62 ms 10684 KB Output isn't correct