oj.uz

Submission #583410

# Submission time Handle Problem Language Result Execution time Memory
583410 2022-06-25T10:32:35 Z Jomnoi Saveit (IOI10_saveit) C++17
75 / 100
 214 ms 13980 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;
    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 = 0;
        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 = 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;
                }
            }
        }

        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] + W[u][v];
                    q.push(v);
                }
            }
        }

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 13980 KB Output is correct - 62913 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Correct 20 ms 8568 KB Output is correct - 58901 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Correct 23 ms 8616 KB Output is correct - 56288 call(s) of encode_bit()
6 Correct 23 ms 9004 KB Output is correct - 60905 call(s) of encode_bit()
7 Correct 33 ms 9228 KB Output is correct - 50828 call(s) of encode_bit()
8 Correct 27 ms 8868 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 25 ms 9372 KB Output is partially correct - 78646 call(s) of encode_bit()
10 Correct 26 ms 9220 KB Output is partially correct - 78245 call(s) of encode_bit()
11 Correct 33 ms 9320 KB Output is partially correct - 76543 call(s) of encode_bit()
12 Correct 26 ms 9276 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 53 ms 9312 KB Output is correct - 58326 call(s) of encode_bit()
14 Correct 25 ms 9244 KB Output is partially correct - 77694 call(s) of encode_bit()
15 Correct 25 ms 9212 KB Output is partially correct - 76176 call(s) of encode_bit()
16 Correct 54 ms 9640 KB Output is partially correct - 72118 call(s) of encode_bit()
17 Correct 46 ms 9572 KB Output is partially correct - 74009 call(s) of encode_bit()
18 Correct 53 ms 9916 KB Output is correct - 69823 call(s) of encode_bit()
19 Correct 35 ms 9272 KB Output is correct - 66843 call(s) of encode_bit()
20 Correct 63 ms 9888 KB Output is correct - 63570 call(s) of encode_bit()
21 Correct 88 ms 9964 KB Output is correct - 64320 call(s) of encode_bit()
22 Correct 54 ms 9348 KB Output is correct - 53039 call(s) of encode_bit()
23 Correct 63 ms 10136 KB Output is correct - 56825 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 13980 KB Output is correct - 62913 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Correct 20 ms 8568 KB Output is correct - 58901 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Correct 23 ms 8616 KB Output is correct - 56288 call(s) of encode_bit()
6 Correct 23 ms 9004 KB Output is correct - 60905 call(s) of encode_bit()
7 Correct 33 ms 9228 KB Output is correct - 50828 call(s) of encode_bit()
8 Correct 27 ms 8868 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 25 ms 9372 KB Output is partially correct - 78646 call(s) of encode_bit()
10 Correct 26 ms 9220 KB Output is partially correct - 78245 call(s) of encode_bit()
11 Correct 33 ms 9320 KB Output is partially correct - 76543 call(s) of encode_bit()
12 Correct 26 ms 9276 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 53 ms 9312 KB Output is correct - 58326 call(s) of encode_bit()
14 Correct 25 ms 9244 KB Output is partially correct - 77694 call(s) of encode_bit()
15 Correct 25 ms 9212 KB Output is partially correct - 76176 call(s) of encode_bit()
16 Correct 54 ms 9640 KB Output is partially correct - 72118 call(s) of encode_bit()
17 Correct 46 ms 9572 KB Output is partially correct - 74009 call(s) of encode_bit()
18 Correct 53 ms 9916 KB Output is correct - 69823 call(s) of encode_bit()
19 Correct 35 ms 9272 KB Output is correct - 66843 call(s) of encode_bit()
20 Correct 63 ms 9888 KB Output is correct - 63570 call(s) of encode_bit()
21 Correct 88 ms 9964 KB Output is correct - 64320 call(s) of encode_bit()
22 Correct 54 ms 9348 KB Output is correct - 53039 call(s) of encode_bit()
23 Correct 63 ms 10136 KB Output is correct - 56825 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 13980 KB Output is correct - 62913 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Correct 20 ms 8568 KB Output is correct - 58901 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Correct 23 ms 8616 KB Output is correct - 56288 call(s) of encode_bit()
6 Correct 23 ms 9004 KB Output is correct - 60905 call(s) of encode_bit()
7 Correct 33 ms 9228 KB Output is correct - 50828 call(s) of encode_bit()
8 Correct 27 ms 8868 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 25 ms 9372 KB Output is partially correct - 78646 call(s) of encode_bit()
10 Correct 26 ms 9220 KB Output is partially correct - 78245 call(s) of encode_bit()
11 Correct 33 ms 9320 KB Output is partially correct - 76543 call(s) of encode_bit()
12 Correct 26 ms 9276 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 53 ms 9312 KB Output is correct - 58326 call(s) of encode_bit()
14 Correct 25 ms 9244 KB Output is partially correct - 77694 call(s) of encode_bit()
15 Correct 25 ms 9212 KB Output is partially correct - 76176 call(s) of encode_bit()
16 Correct 54 ms 9640 KB Output is partially correct - 72118 call(s) of encode_bit()
17 Correct 46 ms 9572 KB Output is partially correct - 74009 call(s) of encode_bit()
18 Correct 53 ms 9916 KB Output is correct - 69823 call(s) of encode_bit()
19 Correct 35 ms 9272 KB Output is correct - 66843 call(s) of encode_bit()
20 Correct 63 ms 9888 KB Output is correct - 63570 call(s) of encode_bit()
21 Correct 88 ms 9964 KB Output is correct - 64320 call(s) of encode_bit()
22 Correct 54 ms 9348 KB Output is correct - 53039 call(s) of encode_bit()
23 Correct 63 ms 10136 KB Output is correct - 56825 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 13980 KB Output is correct - 62913 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 52 call(s) of encode_bit()
3 Correct 20 ms 8568 KB Output is correct - 58901 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 62 call(s) of encode_bit()
5 Correct 23 ms 8616 KB Output is correct - 56288 call(s) of encode_bit()
6 Correct 23 ms 9004 KB Output is correct - 60905 call(s) of encode_bit()
7 Correct 33 ms 9228 KB Output is correct - 50828 call(s) of encode_bit()
8 Correct 27 ms 8868 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 25 ms 9372 KB Output is partially correct - 78646 call(s) of encode_bit()
10 Correct 26 ms 9220 KB Output is partially correct - 78245 call(s) of encode_bit()
11 Correct 33 ms 9320 KB Output is partially correct - 76543 call(s) of encode_bit()
12 Correct 26 ms 9276 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 53 ms 9312 KB Output is correct - 58326 call(s) of encode_bit()
14 Correct 25 ms 9244 KB Output is partially correct - 77694 call(s) of encode_bit()
15 Correct 25 ms 9212 KB Output is partially correct - 76176 call(s) of encode_bit()
16 Correct 54 ms 9640 KB Output is partially correct - 72118 call(s) of encode_bit()
17 Correct 46 ms 9572 KB Output is partially correct - 74009 call(s) of encode_bit()
18 Correct 53 ms 9916 KB Output is correct - 69823 call(s) of encode_bit()
19 Correct 35 ms 9272 KB Output is correct - 66843 call(s) of encode_bit()
20 Correct 63 ms 9888 KB Output is correct - 63570 call(s) of encode_bit()
21 Correct 88 ms 9964 KB Output is correct - 64320 call(s) of encode_bit()
22 Correct 54 ms 9348 KB Output is correct - 53039 call(s) of encode_bit()
23 Correct 63 ms 10136 KB Output is correct - 56825 call(s) of encode_bit()