oj.uz

Submission #201471

# Submission time Handle Problem Language Result Execution time Memory
201471 2020-02-10T16:40:10 Z dolphingarlic Saveit (IOI10_saveit) C++14
100 / 100
 264 ms 12272 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

vector<int> graph[1000];
int par[1000], dist[1000][36], state[1000];
bool visited[1000];

void dfs(int node = 0, int parent = 0) {
    par[node] = parent;
    visited[node] = true;
    for (int i : graph[node]) if (!visited[i]) dfs(i, node);
}

void encode(int nv, int nh, int ne, int *v1, int *v2) {
    FOR(i, 0, ne) {
        graph[v1[i]].push_back(v2[i]);
        graph[v2[i]].push_back(v1[i]);
    }
    dfs();
    FOR(i, 0, nv) FOR(j, 0, 10) encode_bit((par[i] & (1 << j)) >> j);

    FOR(hub, 0, nh) {
        dist[hub][hub] = 1;
        queue<int> q;
        q.push(hub);
        while (q.size()) {
            int curr = q.front();
            q.pop();
            for (int i : graph[curr]) if (!dist[i][hub]) {
                dist[i][hub] = dist[curr][hub] + 1;
                q.push(i);
            }
        }

        FOR(i, 0, nv) {
            if (dist[i][hub] == dist[par[i]][hub]) state[i] = 0;
            else if (dist[i][hub] > dist[par[i]][hub]) state[i] = 1;
            else state[i] = 2;
        }
        for (int i = 0; i < nv; i += 5) {
            int enc = 0;
            FOR(j, i, min(i + 5, nv)) enc = (enc * 3 + state[j]);
            FOR(j, 0, 8) encode_bit((enc & (1 << j)) >> j);
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<int> graph[1000];
int par[1000], dist[1000][36], state[1000];

void dfs(int hub, int node = 0, int parent = 0) {
    dist[node][hub] = dist[par[node]][hub] + (state[node] + 1) % 3 - 1;
    for (int i : graph[node]) if (i != parent) dfs(hub, i, node);
}

void decode(int nv, int nh) {
    FOR(i, 0, nv) {
        FOR(j, 0, 10) par[i] += decode_bit() << j;
        graph[par[i]].push_back(i);
    }

    FOR(hub, 0, nh) {
        for (int i = 0; i < nv; i += 5) {
            int enc = 0;
            FOR(j, 0, 8) enc += decode_bit() << j;
            for (int j = min(i + 5, nv) - 1; j >= i; j--) {
                state[j] = enc % 3;
                enc /= 3;
            }
        }

        int curr = hub;
        while (curr != par[curr]) {
            dist[par[curr]][hub] = dist[curr][hub] - (state[curr] + 1) % 3 + 1;
            curr = par[curr];
        }
        dfs(hub);

        FOR(i, 0, nv) hops(hub, i, dist[i][hub]);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 12272 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4904 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 37 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 11 ms 4676 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 40 ms 5824 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 38 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 34 ms 5568 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 38 ms 5660 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 43 ms 5840 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 40 ms 6028 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 69 ms 6584 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 40 ms 5824 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 46 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 67 ms 6700 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 51 ms 6272 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 90 ms 6948 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 88 ms 7012 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 92 ms 7236 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 12272 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4904 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 37 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 11 ms 4676 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 40 ms 5824 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 38 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 34 ms 5568 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 38 ms 5660 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 43 ms 5840 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 40 ms 6028 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 69 ms 6584 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 40 ms 5824 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 46 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 67 ms 6700 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 51 ms 6272 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 90 ms 6948 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 88 ms 7012 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 92 ms 7236 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 12272 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4904 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 37 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 11 ms 4676 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 40 ms 5824 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 38 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 34 ms 5568 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 38 ms 5660 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 43 ms 5840 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 40 ms 6028 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 69 ms 6584 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 40 ms 5824 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 46 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 67 ms 6700 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 51 ms 6272 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 90 ms 6948 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 88 ms 7012 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 92 ms 7236 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 12272 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4904 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 37 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 11 ms 4676 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 40 ms 5824 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 38 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 34 ms 5568 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 38 ms 5660 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 43 ms 5840 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 40 ms 6028 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 69 ms 6584 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 40 ms 5824 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 46 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 60 ms 6340 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 67 ms 6700 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 51 ms 6272 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 90 ms 6948 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 88 ms 7012 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 67 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 92 ms 7236 KB Output is correct - 67600 call(s) of encode_bit()