oj.uz

Submission #514915

# Submission time Handle Problem Language Result Execution time Memory
514915 2022-01-18T19:19:45 Z alextodoran Saveit (IOI10_saveit) C++17
100 / 100
 305 ms 10588 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
 
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
static const int N_MAX = 1000;
static const int H_MAX = 36;
 
static int N, H, E;
 
static int dist[H_MAX][N_MAX];
 
static int parent[N_MAX];
 
static vector <int> adj[N_MAX];
 
static vector <int> order;
 
void dfsRec (int u) {
    order.push_back(u);
    for (int v : adj[u]) {
        if (parent[v] == -1) {
            parent[v] = u;
            dfsRec(v);
        }
    }
}
void dfs (int h) {
    for (int u = 0; u < N; u++) {
        parent[u] = -1;
    }
    parent[h] = h;
    dfsRec(h);
}
 
#include "grader.h"
#include "encoder.h"
 
void encode_bit (int bit);
 
void encode_int (int val, int len) {
    for (int bit = len - 1; bit >= 0; bit--) {
        encode_bit((val >> bit) & 1);
    }
}
 
void bfs (int h, int dist[]) {
    for (int u = 0; u < N; u++) {
        dist[u] = -1;
    }
    queue <int> q;
    dist[h] = 0;
    q.push(h);
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}
 
void encode (int nv, int nh, int ne, int *v1, int *v2) {
    N = nv; H = nh; E = ne;
    for (int i = 0; i < E; i++) {
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }
    for (int u = 0; u < N; u++) {
        sort(adj[u].begin(), adj[u].end());
    }
 
    for (int h = 0; h < H; h++) {
        bfs(h, dist[h]);
    }
 
    dfs(0);
    for (int u = 0; u < N; u++) {
        adj[u].clear();
    }
    order.clear();
    for (int u = 1; u < N; u++) {
        encode_int(parent[u], 10);
        adj[u].push_back(parent[u]);
        adj[parent[u]].push_back(u);
    }
    for (int u = 0; u < N; u++) {
        sort(adj[u].begin(), adj[u].end());
    }
 
    for (int h = 0; h < H; h++) {
        dfs(h);
        int x = 0, p = 1;
        for (int i = 1; i < N; i++) {
            int u = order[i];
            int d = 1 + (dist[h][u] - dist[h][parent[u]]);
            x += p * d; p *= 3;
            if (i % 3 == 0 || i == N - 1) {
                encode_int(x, 5);
                x = 0; p = 1;
            }
        }
        order.clear();
    }
 
    for (int u = 0; u < N; u++) {
        adj[u].clear();
    }
}
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
 
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
static const int N_MAX = 1000;
static const int H_MAX = 36;
 
static int N, H, E;
 
static int dist[H_MAX][N_MAX];
 
static int parent[N_MAX];
 
static vector <int> adj[N_MAX];
 
static vector <int> order;
 
void dfsRec (int u) {
    order.push_back(u);
    for (int v : adj[u]) {
        if (parent[v] == -1) {
            parent[v] = u;
            dfsRec(v);
        }
    }
}
void dfs (int h) {
    for (int u = 0; u < N; u++) {
        parent[u] = -1;
    }
    parent[h] = h;
    dfsRec(h);
}
 
#include "grader.h"
#include "decoder.h"
 
int decode_bit ();
 
void hops (int a, int b, int d);
 
int decode_int (int len) {
    int val = 0;
    for (int bit = len - 1; bit >= 0; bit--) {
        val |= (decode_bit() << bit);
    }
    return val;
}
 
void decode (int nv, int nh) {
    N = nv; H = nh;
    for (int u = 1; u < N; u++) {
        parent[u] = decode_int(10);
        adj[u].push_back(parent[u]);
        adj[parent[u]].push_back(u);
    }
    for (int u = 0; u < N; u++) {
        sort(adj[u].begin(), adj[u].end());
    }
 
    for (int h = 0; h < H; h++) {
        dfs(h);
        dist[h][h] = 0;
        int x = decode_int(5);
        for (int i = 1; i < N; i++) {
            int u = order[i];
            int d = x % 3 - 1; x /= 3;
            dist[h][u] = dist[h][parent[u]] + d;
            if (i % 3 == 0 && i != N - 1) {
                x = decode_int(5);
            }
        }
        order.clear();
    }
    for (int h = 0; h < H; h++) {
        for (int u = 0; u < N; u++) {
            hops(h, u, dist[h][u]);
        }
    }
 
    for (int u = 0; u < N; u++) {
        adj[u].clear();
    }
}

Compilation message

decoder.cpp:18:18: warning: 'E' defined but not used [-Wunused-variable]
   18 | static int N, H, E;
      |                  ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 10588 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5736 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 26 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 26 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 41 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 5732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 24 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 27 ms 5808 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 5784 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 24 ms 5684 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 56 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 5840 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 49 ms 6264 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 41 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 56 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 6096 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 75 ms 6768 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 88 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 51 ms 6288 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 79 ms 7008 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 10588 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5736 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 26 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 26 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 41 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 5732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 24 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 27 ms 5808 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 5784 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 24 ms 5684 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 56 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 5840 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 49 ms 6264 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 41 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 56 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 6096 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 75 ms 6768 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 88 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 51 ms 6288 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 79 ms 7008 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 10588 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5736 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 26 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 26 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 41 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 5732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 24 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 27 ms 5808 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 5784 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 24 ms 5684 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 56 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 5840 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 49 ms 6264 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 41 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 56 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 6096 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 75 ms 6768 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 88 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 51 ms 6288 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 79 ms 7008 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 10588 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5736 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 26 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 26 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 41 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 20 ms 5732 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 24 ms 5704 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 27 ms 5808 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 5784 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 24 ms 5684 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 56 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 22 ms 5840 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 22 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 49 ms 6264 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 41 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 56 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 6096 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 75 ms 6768 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 88 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 51 ms 6288 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 79 ms 7008 KB Output is correct - 69930 call(s) of encode_bit()