oj.uz

Submission #566718

# Submission time Handle Problem Language Result Execution time Memory
566718 2022-05-22T18:08:33 Z birthdaycake Saveit (IOI10_saveit) C++17
0 / 100
 169 ms 10776 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
 
using namespace std;
 
vector<int>adj[1001];
 
 
int dis[1001],par[1001], j;
void reset(int n){
    j = 0;
    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};
    while(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] = j = 0;
        vector<int>b = {i};
        while(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 i = 1; i < n; i++){
            int diff = pc[i] - pc[par[i]];
            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);
        }
        adj[i].push_back(parent);
        adj[parent].push_back(i);
    }
    dis[0] = j = 0;
    vector<int>b = {0};
    while(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++){
            int x = decode_bit();
            if(x == 0){
                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>b = {i};
            while(b.size()){
                for(auto s:adj[b[j]]){
                    if(pc[s] == INT_MAX){
                        pc[s] = pc[b[j]] + diff[b[j]][s];
                        b.push_back(s);
                    }
                }
                j++;
            }
            for(int t = 0; t < n; t++){
                hops(i,t,pc[t]);
            }
        }
    }
    
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 10776 KB Execution killed with signal 11
2 Runtime error 2 ms 464 KB Execution killed with signal 11
3 Runtime error 8 ms 948 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 7 ms 1360 KB Execution killed with signal 11
6 Runtime error 7 ms 1360 KB Execution killed with signal 11
7 Runtime error 21 ms 1952 KB Execution killed with signal 11
8 Runtime error 9 ms 848 KB Execution killed with signal 11
9 Runtime error 6 ms 956 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 5 ms 848 KB Execution killed with signal 11
13 Runtime error 24 ms 2304 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 6 ms 1104 KB Execution killed with signal 11
16 Runtime error 25 ms 1996 KB Execution killed with signal 11
17 Runtime error 16 ms 1872 KB Execution killed with signal 11
18 Runtime error 27 ms 2556 KB Execution killed with signal 11
19 Runtime error 10 ms 1668 KB Execution killed with signal 11
20 Runtime error 37 ms 3144 KB Execution killed with signal 11
21 Runtime error 49 ms 3332 KB Execution killed with signal 11
22 Runtime error 31 ms 2336 KB Execution killed with signal 11
23 Runtime error 51 ms 3832 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 10776 KB Execution killed with signal 11
2 Runtime error 2 ms 464 KB Execution killed with signal 11
3 Runtime error 8 ms 948 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 7 ms 1360 KB Execution killed with signal 11
6 Runtime error 7 ms 1360 KB Execution killed with signal 11
7 Runtime error 21 ms 1952 KB Execution killed with signal 11
8 Runtime error 9 ms 848 KB Execution killed with signal 11
9 Runtime error 6 ms 956 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 5 ms 848 KB Execution killed with signal 11
13 Runtime error 24 ms 2304 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 6 ms 1104 KB Execution killed with signal 11
16 Runtime error 25 ms 1996 KB Execution killed with signal 11
17 Runtime error 16 ms 1872 KB Execution killed with signal 11
18 Runtime error 27 ms 2556 KB Execution killed with signal 11
19 Runtime error 10 ms 1668 KB Execution killed with signal 11
20 Runtime error 37 ms 3144 KB Execution killed with signal 11
21 Runtime error 49 ms 3332 KB Execution killed with signal 11
22 Runtime error 31 ms 2336 KB Execution killed with signal 11
23 Runtime error 51 ms 3832 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 10776 KB Execution killed with signal 11
2 Runtime error 2 ms 464 KB Execution killed with signal 11
3 Runtime error 8 ms 948 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 7 ms 1360 KB Execution killed with signal 11
6 Runtime error 7 ms 1360 KB Execution killed with signal 11
7 Runtime error 21 ms 1952 KB Execution killed with signal 11
8 Runtime error 9 ms 848 KB Execution killed with signal 11
9 Runtime error 6 ms 956 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 5 ms 848 KB Execution killed with signal 11
13 Runtime error 24 ms 2304 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 6 ms 1104 KB Execution killed with signal 11
16 Runtime error 25 ms 1996 KB Execution killed with signal 11
17 Runtime error 16 ms 1872 KB Execution killed with signal 11
18 Runtime error 27 ms 2556 KB Execution killed with signal 11
19 Runtime error 10 ms 1668 KB Execution killed with signal 11
20 Runtime error 37 ms 3144 KB Execution killed with signal 11
21 Runtime error 49 ms 3332 KB Execution killed with signal 11
22 Runtime error 31 ms 2336 KB Execution killed with signal 11
23 Runtime error 51 ms 3832 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 10776 KB Execution killed with signal 11
2 Runtime error 2 ms 464 KB Execution killed with signal 11
3 Runtime error 8 ms 948 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 7 ms 1360 KB Execution killed with signal 11
6 Runtime error 7 ms 1360 KB Execution killed with signal 11
7 Runtime error 21 ms 1952 KB Execution killed with signal 11
8 Runtime error 9 ms 848 KB Execution killed with signal 11
9 Runtime error 6 ms 956 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 5 ms 848 KB Execution killed with signal 11
13 Runtime error 24 ms 2304 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 6 ms 1104 KB Execution killed with signal 11
16 Runtime error 25 ms 1996 KB Execution killed with signal 11
17 Runtime error 16 ms 1872 KB Execution killed with signal 11
18 Runtime error 27 ms 2556 KB Execution killed with signal 11
19 Runtime error 10 ms 1668 KB Execution killed with signal 11
20 Runtime error 37 ms 3144 KB Execution killed with signal 11
21 Runtime error 49 ms 3332 KB Execution killed with signal 11
22 Runtime error 31 ms 2336 KB Execution killed with signal 11
23 Runtime error 51 ms 3832 KB Execution killed with signal 11