oj.uz

Submission #583401

# Submission time Handle Problem Language Result Execution time Memory
583401 2022-06-25T10:23:03 Z Jomnoi Saveit (IOI10_saveit) C++17
0 / 100
 192 ms 14568 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;

namespace {
    
const int MAX_N = 1005;

vector <int> graph[MAX_N];
int parent[MAX_N], dist[MAX_N];

}

void encode(int nv, int nh, int ne, int *v1, int *v2) {
    for(int i = 0; i < ne; i++) {
        graph[v1[i]].push_back(v2[i]);
        graph[v2[i]].push_back(v1[i]);
    }

    for(int i = 0; i < nv; i++) {
        dist[i] = -1;
    }
    queue <int> q;
    q.push(0);
    dist[0] = 0;
    parent[0] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();

        for(auto v : graph[u]) {
            if(dist[v] == -1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }

    for(int i = 1; i < nv; i++) {
        for(int k = 0; k < 10; k++) {
            if((1<<k) & parent[i]) {
                encode_bit(1);
            }
            else {
                encode_bit(0);
            }
        }
    }

    for(int h = 1; h < nh; h++) {
        for(int i = 0; i < nv; i++) {
            dist[i] = -1;
        }

        queue <int> q;
        q.push(h);
        dist[h] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();

            for(auto v : graph[u]) {
                if(dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }

        for(int i = 1; i < nv; i++) {
            if(dist[i] == dist[parent[i]]) {
                encode_bit(0);
            }
            else {
                encode_bit(1);
                if(dist[i] < dist[parent[i]]) {
                    encode_bit(1);
                }
                else {
                    encode_bit(0);
                }
            }
        }
    }
}

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;

namespace {
    
const int MAX_N = 1005;

vector <int> graph[MAX_N];
int parent[MAX_N];
int dist[MAX_N], W[MAX_N][MAX_N];

}

void decode(int nv, int nh) {
    for(int i = 1; i < nv; i++) {
        int p;
        for(int k = 0; k < 10; k++) {
            p += (1<<k) * decode_bit();
        }

        parent[i] = p;
        graph[p].push_back(i);
        graph[i].push_back(p);
    }

    for(int i = 0; i < nv; i++) {
        dist[i] = -1;
    }

    queue <int> q;
    q.push(0);
    dist[0] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();

        for(auto v : graph[u]) {
            if(dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for(int i = 0; i < nv; i++) {
        hops(0, i, dist[i]);
    }

    for(int h = 1; h < nh; h++) {
        for(int i = 0; i < nv; i++) {
            dist[i] = -1;
        }

        for(int i = 1; i < nv; i++) {
            if(decode_bit() == 0) {
                W[i][parent[i]] = 0;
                W[parent[i]][i] = 0;
            }
            else {
                if(decode_bit() == 1) {
                    W[i][parent[i]] = 1;
                    W[parent[i]][i] = -1;
                }
                else {
                    W[i][parent[i]] = -1;
                    W[parent[i]][i] = 1;
                }
            }
        }

        queue <int> q;
        q.push(h);
        dist[h] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();

            for(auto v : graph[u]) {
                if(dist[v] == -1) {
                    dist[v] = dist[u] + W[u][v];
                    q.push(v);
                }
            }
        }

        for(int i = 0; i < nv; i++) {
            hops(h, i, dist[i]);
        }
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 14568 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB wrong parameter
3 Runtime error 33 ms 9616 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB wrong parameter
5 Runtime error 24 ms 9848 KB Execution killed with signal 11
6 Runtime error 28 ms 9892 KB Execution killed with signal 11
7 Runtime error 45 ms 10048 KB Execution killed with signal 11
8 Runtime error 25 ms 9928 KB Execution killed with signal 11
9 Runtime error 26 ms 9928 KB Execution killed with signal 11
10 Runtime error 34 ms 9956 KB Execution killed with signal 11
11 Runtime error 30 ms 9936 KB Execution killed with signal 11
12 Runtime error 27 ms 9904 KB Execution killed with signal 11
13 Runtime error 68 ms 10204 KB Execution killed with signal 11
14 Runtime error 29 ms 9844 KB Execution killed with signal 11
15 Runtime error 28 ms 9944 KB Execution killed with signal 11
16 Runtime error 60 ms 10260 KB Execution killed with signal 11
17 Runtime error 41 ms 10184 KB Execution killed with signal 11
18 Runtime error 45 ms 10596 KB Execution killed with signal 11
19 Runtime error 37 ms 10080 KB Execution killed with signal 11
20 Runtime error 71 ms 10736 KB Execution killed with signal 11
21 Runtime error 84 ms 10916 KB Execution killed with signal 11
22 Runtime error 56 ms 10272 KB Execution killed with signal 11
23 Runtime error 88 ms 10920 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 14568 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB wrong parameter
3 Runtime error 33 ms 9616 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB wrong parameter
5 Runtime error 24 ms 9848 KB Execution killed with signal 11
6 Runtime error 28 ms 9892 KB Execution killed with signal 11
7 Runtime error 45 ms 10048 KB Execution killed with signal 11
8 Runtime error 25 ms 9928 KB Execution killed with signal 11
9 Runtime error 26 ms 9928 KB Execution killed with signal 11
10 Runtime error 34 ms 9956 KB Execution killed with signal 11
11 Runtime error 30 ms 9936 KB Execution killed with signal 11
12 Runtime error 27 ms 9904 KB Execution killed with signal 11
13 Runtime error 68 ms 10204 KB Execution killed with signal 11
14 Runtime error 29 ms 9844 KB Execution killed with signal 11
15 Runtime error 28 ms 9944 KB Execution killed with signal 11
16 Runtime error 60 ms 10260 KB Execution killed with signal 11
17 Runtime error 41 ms 10184 KB Execution killed with signal 11
18 Runtime error 45 ms 10596 KB Execution killed with signal 11
19 Runtime error 37 ms 10080 KB Execution killed with signal 11
20 Runtime error 71 ms 10736 KB Execution killed with signal 11
21 Runtime error 84 ms 10916 KB Execution killed with signal 11
22 Runtime error 56 ms 10272 KB Execution killed with signal 11
23 Runtime error 88 ms 10920 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 14568 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB wrong parameter
3 Runtime error 33 ms 9616 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB wrong parameter
5 Runtime error 24 ms 9848 KB Execution killed with signal 11
6 Runtime error 28 ms 9892 KB Execution killed with signal 11
7 Runtime error 45 ms 10048 KB Execution killed with signal 11
8 Runtime error 25 ms 9928 KB Execution killed with signal 11
9 Runtime error 26 ms 9928 KB Execution killed with signal 11
10 Runtime error 34 ms 9956 KB Execution killed with signal 11
11 Runtime error 30 ms 9936 KB Execution killed with signal 11
12 Runtime error 27 ms 9904 KB Execution killed with signal 11
13 Runtime error 68 ms 10204 KB Execution killed with signal 11
14 Runtime error 29 ms 9844 KB Execution killed with signal 11
15 Runtime error 28 ms 9944 KB Execution killed with signal 11
16 Runtime error 60 ms 10260 KB Execution killed with signal 11
17 Runtime error 41 ms 10184 KB Execution killed with signal 11
18 Runtime error 45 ms 10596 KB Execution killed with signal 11
19 Runtime error 37 ms 10080 KB Execution killed with signal 11
20 Runtime error 71 ms 10736 KB Execution killed with signal 11
21 Runtime error 84 ms 10916 KB Execution killed with signal 11
22 Runtime error 56 ms 10272 KB Execution killed with signal 11
23 Runtime error 88 ms 10920 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 14568 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB wrong parameter
3 Runtime error 33 ms 9616 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB wrong parameter
5 Runtime error 24 ms 9848 KB Execution killed with signal 11
6 Runtime error 28 ms 9892 KB Execution killed with signal 11
7 Runtime error 45 ms 10048 KB Execution killed with signal 11
8 Runtime error 25 ms 9928 KB Execution killed with signal 11
9 Runtime error 26 ms 9928 KB Execution killed with signal 11
10 Runtime error 34 ms 9956 KB Execution killed with signal 11
11 Runtime error 30 ms 9936 KB Execution killed with signal 11
12 Runtime error 27 ms 9904 KB Execution killed with signal 11
13 Runtime error 68 ms 10204 KB Execution killed with signal 11
14 Runtime error 29 ms 9844 KB Execution killed with signal 11
15 Runtime error 28 ms 9944 KB Execution killed with signal 11
16 Runtime error 60 ms 10260 KB Execution killed with signal 11
17 Runtime error 41 ms 10184 KB Execution killed with signal 11
18 Runtime error 45 ms 10596 KB Execution killed with signal 11
19 Runtime error 37 ms 10080 KB Execution killed with signal 11
20 Runtime error 71 ms 10736 KB Execution killed with signal 11
21 Runtime error 84 ms 10916 KB Execution killed with signal 11
22 Runtime error 56 ms 10272 KB Execution killed with signal 11
23 Runtime error 88 ms 10920 KB Execution killed with signal 11