oj.uz

Submission #566752

# Submission time Handle Problem Language Result Execution time Memory
566752 2022-05-22T19:41:06 Z birthdaycake Saveit (IOI10_saveit) C++14
0 / 100
 201 ms 14044 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 201 ms 14044 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8836 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 23 ms 8960 KB wrong parameter
6 Incorrect 20 ms 9396 KB wrong parameter
7 Incorrect 35 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9176 KB wrong parameter
9 Incorrect 24 ms 9504 KB wrong parameter
10 Incorrect 20 ms 9296 KB wrong parameter
11 Incorrect 24 ms 9532 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 41 ms 9920 KB wrong parameter
14 Incorrect 19 ms 9364 KB wrong parameter
15 Incorrect 22 ms 9424 KB wrong parameter
16 Incorrect 41 ms 9900 KB wrong parameter
17 Incorrect 44 ms 9680 KB wrong parameter
18 Incorrect 51 ms 10128 KB wrong parameter
19 Incorrect 29 ms 9604 KB wrong parameter
20 Incorrect 51 ms 10280 KB wrong parameter
21 Incorrect 60 ms 10412 KB wrong parameter
22 Incorrect 35 ms 9948 KB wrong parameter
23 Incorrect 70 ms 10520 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 14044 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8836 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 23 ms 8960 KB wrong parameter
6 Incorrect 20 ms 9396 KB wrong parameter
7 Incorrect 35 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9176 KB wrong parameter
9 Incorrect 24 ms 9504 KB wrong parameter
10 Incorrect 20 ms 9296 KB wrong parameter
11 Incorrect 24 ms 9532 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 41 ms 9920 KB wrong parameter
14 Incorrect 19 ms 9364 KB wrong parameter
15 Incorrect 22 ms 9424 KB wrong parameter
16 Incorrect 41 ms 9900 KB wrong parameter
17 Incorrect 44 ms 9680 KB wrong parameter
18 Incorrect 51 ms 10128 KB wrong parameter
19 Incorrect 29 ms 9604 KB wrong parameter
20 Incorrect 51 ms 10280 KB wrong parameter
21 Incorrect 60 ms 10412 KB wrong parameter
22 Incorrect 35 ms 9948 KB wrong parameter
23 Incorrect 70 ms 10520 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 14044 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8836 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 23 ms 8960 KB wrong parameter
6 Incorrect 20 ms 9396 KB wrong parameter
7 Incorrect 35 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9176 KB wrong parameter
9 Incorrect 24 ms 9504 KB wrong parameter
10 Incorrect 20 ms 9296 KB wrong parameter
11 Incorrect 24 ms 9532 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 41 ms 9920 KB wrong parameter
14 Incorrect 19 ms 9364 KB wrong parameter
15 Incorrect 22 ms 9424 KB wrong parameter
16 Incorrect 41 ms 9900 KB wrong parameter
17 Incorrect 44 ms 9680 KB wrong parameter
18 Incorrect 51 ms 10128 KB wrong parameter
19 Incorrect 29 ms 9604 KB wrong parameter
20 Incorrect 51 ms 10280 KB wrong parameter
21 Incorrect 60 ms 10412 KB wrong parameter
22 Incorrect 35 ms 9948 KB wrong parameter
23 Incorrect 70 ms 10520 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 14044 KB wrong parameter
2 Correct 2 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 18 ms 8836 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 23 ms 8960 KB wrong parameter
6 Incorrect 20 ms 9396 KB wrong parameter
7 Incorrect 35 ms 9708 KB wrong parameter
8 Incorrect 19 ms 9176 KB wrong parameter
9 Incorrect 24 ms 9504 KB wrong parameter
10 Incorrect 20 ms 9296 KB wrong parameter
11 Incorrect 24 ms 9532 KB wrong parameter
12 Incorrect 22 ms 9340 KB wrong parameter
13 Incorrect 41 ms 9920 KB wrong parameter
14 Incorrect 19 ms 9364 KB wrong parameter
15 Incorrect 22 ms 9424 KB wrong parameter
16 Incorrect 41 ms 9900 KB wrong parameter
17 Incorrect 44 ms 9680 KB wrong parameter
18 Incorrect 51 ms 10128 KB wrong parameter
19 Incorrect 29 ms 9604 KB wrong parameter
20 Incorrect 51 ms 10280 KB wrong parameter
21 Incorrect 60 ms 10412 KB wrong parameter
22 Incorrect 35 ms 9948 KB wrong parameter
23 Incorrect 70 ms 10520 KB wrong parameter