oj.uz

Submission #566751

# Submission time Handle Problem Language Result Execution time Memory
566751 2022-05-22T19:36:51 Z birthdaycake Saveit (IOI10_saveit) C++14
0 / 100
 213 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 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 213 ms 14044 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 19 ms 8864 KB wrong parameter
4 Incorrect 2 ms 4688 KB wrong parameter
5 Incorrect 19 ms 8992 KB wrong parameter
6 Incorrect 20 ms 9388 KB wrong parameter
7 Incorrect 32 ms 9784 KB wrong parameter
8 Incorrect 20 ms 9096 KB wrong parameter
9 Incorrect 25 ms 9392 KB wrong parameter
10 Incorrect 26 ms 9268 KB wrong parameter
11 Incorrect 28 ms 9536 KB wrong parameter
12 Incorrect 19 ms 9332 KB wrong parameter
13 Incorrect 42 ms 9940 KB wrong parameter
14 Incorrect 20 ms 9340 KB wrong parameter
15 Incorrect 25 ms 9316 KB wrong parameter
16 Incorrect 46 ms 9816 KB wrong parameter
17 Incorrect 45 ms 9752 KB wrong parameter
18 Incorrect 45 ms 9996 KB wrong parameter
19 Incorrect 29 ms 9656 KB wrong parameter
20 Incorrect 50 ms 10272 KB wrong parameter
21 Incorrect 62 ms 10364 KB wrong parameter
22 Incorrect 36 ms 9816 KB wrong parameter
23 Incorrect 71 ms 10592 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 14044 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 19 ms 8864 KB wrong parameter
4 Incorrect 2 ms 4688 KB wrong parameter
5 Incorrect 19 ms 8992 KB wrong parameter
6 Incorrect 20 ms 9388 KB wrong parameter
7 Incorrect 32 ms 9784 KB wrong parameter
8 Incorrect 20 ms 9096 KB wrong parameter
9 Incorrect 25 ms 9392 KB wrong parameter
10 Incorrect 26 ms 9268 KB wrong parameter
11 Incorrect 28 ms 9536 KB wrong parameter
12 Incorrect 19 ms 9332 KB wrong parameter
13 Incorrect 42 ms 9940 KB wrong parameter
14 Incorrect 20 ms 9340 KB wrong parameter
15 Incorrect 25 ms 9316 KB wrong parameter
16 Incorrect 46 ms 9816 KB wrong parameter
17 Incorrect 45 ms 9752 KB wrong parameter
18 Incorrect 45 ms 9996 KB wrong parameter
19 Incorrect 29 ms 9656 KB wrong parameter
20 Incorrect 50 ms 10272 KB wrong parameter
21 Incorrect 62 ms 10364 KB wrong parameter
22 Incorrect 36 ms 9816 KB wrong parameter
23 Incorrect 71 ms 10592 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 14044 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 19 ms 8864 KB wrong parameter
4 Incorrect 2 ms 4688 KB wrong parameter
5 Incorrect 19 ms 8992 KB wrong parameter
6 Incorrect 20 ms 9388 KB wrong parameter
7 Incorrect 32 ms 9784 KB wrong parameter
8 Incorrect 20 ms 9096 KB wrong parameter
9 Incorrect 25 ms 9392 KB wrong parameter
10 Incorrect 26 ms 9268 KB wrong parameter
11 Incorrect 28 ms 9536 KB wrong parameter
12 Incorrect 19 ms 9332 KB wrong parameter
13 Incorrect 42 ms 9940 KB wrong parameter
14 Incorrect 20 ms 9340 KB wrong parameter
15 Incorrect 25 ms 9316 KB wrong parameter
16 Incorrect 46 ms 9816 KB wrong parameter
17 Incorrect 45 ms 9752 KB wrong parameter
18 Incorrect 45 ms 9996 KB wrong parameter
19 Incorrect 29 ms 9656 KB wrong parameter
20 Incorrect 50 ms 10272 KB wrong parameter
21 Incorrect 62 ms 10364 KB wrong parameter
22 Incorrect 36 ms 9816 KB wrong parameter
23 Incorrect 71 ms 10592 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 14044 KB wrong parameter
2 Incorrect 2 ms 4612 KB wrong parameter
3 Incorrect 19 ms 8864 KB wrong parameter
4 Incorrect 2 ms 4688 KB wrong parameter
5 Incorrect 19 ms 8992 KB wrong parameter
6 Incorrect 20 ms 9388 KB wrong parameter
7 Incorrect 32 ms 9784 KB wrong parameter
8 Incorrect 20 ms 9096 KB wrong parameter
9 Incorrect 25 ms 9392 KB wrong parameter
10 Incorrect 26 ms 9268 KB wrong parameter
11 Incorrect 28 ms 9536 KB wrong parameter
12 Incorrect 19 ms 9332 KB wrong parameter
13 Incorrect 42 ms 9940 KB wrong parameter
14 Incorrect 20 ms 9340 KB wrong parameter
15 Incorrect 25 ms 9316 KB wrong parameter
16 Incorrect 46 ms 9816 KB wrong parameter
17 Incorrect 45 ms 9752 KB wrong parameter
18 Incorrect 45 ms 9996 KB wrong parameter
19 Incorrect 29 ms 9656 KB wrong parameter
20 Incorrect 50 ms 10272 KB wrong parameter
21 Incorrect 62 ms 10364 KB wrong parameter
22 Incorrect 36 ms 9816 KB wrong parameter
23 Incorrect 71 ms 10592 KB wrong parameter