oj.uz

Submission #566727

# Submission time Handle Problem Language Result Execution time Memory
566727 2022-05-22T18:45:33 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 206 ms 14172 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],j;
void reset(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){
    
    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);
        }
        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 206 ms 14172 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8852 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9080 KB wrong parameter
6 Incorrect 22 ms 9528 KB wrong parameter
7 Incorrect 35 ms 9684 KB wrong parameter
8 Incorrect 20 ms 9132 KB wrong parameter
9 Incorrect 19 ms 9516 KB wrong parameter
10 Incorrect 23 ms 9288 KB wrong parameter
11 Incorrect 34 ms 9404 KB wrong parameter
12 Incorrect 25 ms 9320 KB wrong parameter
13 Incorrect 42 ms 9760 KB wrong parameter
14 Incorrect 22 ms 9332 KB wrong parameter
15 Incorrect 22 ms 9320 KB wrong parameter
16 Incorrect 44 ms 9820 KB wrong parameter
17 Incorrect 39 ms 9696 KB wrong parameter
18 Incorrect 45 ms 10092 KB wrong parameter
19 Incorrect 37 ms 9564 KB wrong parameter
20 Incorrect 63 ms 10336 KB wrong parameter
21 Incorrect 62 ms 10336 KB wrong parameter
22 Incorrect 37 ms 9824 KB wrong parameter
23 Incorrect 67 ms 10600 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 14172 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8852 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9080 KB wrong parameter
6 Incorrect 22 ms 9528 KB wrong parameter
7 Incorrect 35 ms 9684 KB wrong parameter
8 Incorrect 20 ms 9132 KB wrong parameter
9 Incorrect 19 ms 9516 KB wrong parameter
10 Incorrect 23 ms 9288 KB wrong parameter
11 Incorrect 34 ms 9404 KB wrong parameter
12 Incorrect 25 ms 9320 KB wrong parameter
13 Incorrect 42 ms 9760 KB wrong parameter
14 Incorrect 22 ms 9332 KB wrong parameter
15 Incorrect 22 ms 9320 KB wrong parameter
16 Incorrect 44 ms 9820 KB wrong parameter
17 Incorrect 39 ms 9696 KB wrong parameter
18 Incorrect 45 ms 10092 KB wrong parameter
19 Incorrect 37 ms 9564 KB wrong parameter
20 Incorrect 63 ms 10336 KB wrong parameter
21 Incorrect 62 ms 10336 KB wrong parameter
22 Incorrect 37 ms 9824 KB wrong parameter
23 Incorrect 67 ms 10600 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 14172 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8852 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9080 KB wrong parameter
6 Incorrect 22 ms 9528 KB wrong parameter
7 Incorrect 35 ms 9684 KB wrong parameter
8 Incorrect 20 ms 9132 KB wrong parameter
9 Incorrect 19 ms 9516 KB wrong parameter
10 Incorrect 23 ms 9288 KB wrong parameter
11 Incorrect 34 ms 9404 KB wrong parameter
12 Incorrect 25 ms 9320 KB wrong parameter
13 Incorrect 42 ms 9760 KB wrong parameter
14 Incorrect 22 ms 9332 KB wrong parameter
15 Incorrect 22 ms 9320 KB wrong parameter
16 Incorrect 44 ms 9820 KB wrong parameter
17 Incorrect 39 ms 9696 KB wrong parameter
18 Incorrect 45 ms 10092 KB wrong parameter
19 Incorrect 37 ms 9564 KB wrong parameter
20 Incorrect 63 ms 10336 KB wrong parameter
21 Incorrect 62 ms 10336 KB wrong parameter
22 Incorrect 37 ms 9824 KB wrong parameter
23 Incorrect 67 ms 10600 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 14172 KB wrong parameter
2 Correct 4 ms 4604 KB Output is correct - 52 call(s) of encode_bit()
3 Incorrect 24 ms 8852 KB wrong parameter
4 Correct 2 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Incorrect 20 ms 9080 KB wrong parameter
6 Incorrect 22 ms 9528 KB wrong parameter
7 Incorrect 35 ms 9684 KB wrong parameter
8 Incorrect 20 ms 9132 KB wrong parameter
9 Incorrect 19 ms 9516 KB wrong parameter
10 Incorrect 23 ms 9288 KB wrong parameter
11 Incorrect 34 ms 9404 KB wrong parameter
12 Incorrect 25 ms 9320 KB wrong parameter
13 Incorrect 42 ms 9760 KB wrong parameter
14 Incorrect 22 ms 9332 KB wrong parameter
15 Incorrect 22 ms 9320 KB wrong parameter
16 Incorrect 44 ms 9820 KB wrong parameter
17 Incorrect 39 ms 9696 KB wrong parameter
18 Incorrect 45 ms 10092 KB wrong parameter
19 Incorrect 37 ms 9564 KB wrong parameter
20 Incorrect 63 ms 10336 KB wrong parameter
21 Incorrect 62 ms 10336 KB wrong parameter
22 Incorrect 37 ms 9824 KB wrong parameter
23 Incorrect 67 ms 10600 KB wrong parameter