oj.uz

답안 #60481

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60481 2018-07-24T08:51:57 Z aquablitz11 저장 (Saveit) (IOI10_saveit) C++14
100 / 100
 292 ms 11592 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;

static const int N = 1000;
static vector<int> G[N];
static bool vis[N];
static int par[N], dist[N];

void build_tree(int u, int p)
{
    vis[u] = true;
    par[u] = p;
    for (auto v : G[u]) if (v != p && !vis[v])
        build_tree(v, u);
}

void bfs(int s)
{
    dist[s] = 0;
    vis[s] = true;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (auto v : G[u]) if (!vis[v]) {
            vis[v] = true;
            dist[v] = dist[u]+1;
            Q.push(v);
        }
    }
}

void encode_bits(int x, int b)
{
    for (int i = 0; i < b; ++i)
        encode_bit(((1<<i)&x) ? 1 : 0);
}

static int decis[3];
static int dc = 0;

void encode_delta(int x)
{
    decis[dc++] = x+1;
    if (dc == 3) {
        int v = decis[0]+decis[1]*3+decis[2]*9;
        encode_bits(v, 5);
        dc = 0;
    }
}

void encode(int n, int h, int m, int v1[], int v2[])
{
    for (int i = 0; i < m; ++i) {
        int u = v1[i], v = v2[i];
        G[u].push_back(v);
        G[v].push_back(u);
    }
    build_tree(0, 0);
    for (int i = 1; i < n; ++i)
        encode_bits(par[i], 10);
    for (int i = 0; i < h; ++i) {
        fill(vis, vis+n, false);
        bfs(i);
        for (int j = 1; j < n; ++j)
            encode_delta(dist[j]-dist[par[j]]);
    }
    while (dc != 0)
        encode_delta(0);
}

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

static const int N = 1000;
static int par[N], chn[N], dp[N];
static bool vis[N];
static vector<int> G[N];

int solve(int u)
{
    if (u == 0) return 0;
    if (vis[u]) return dp[u];
    vis[u] = true;
    return dp[u] = chn[u] + solve(par[u]);
}

int decode_bits(int b)
{
    int ans = 0;
    for (int i = 0; i < b; ++i) {
        if (decode_bit())
            ans |= (1<<i);
    }
    return ans;
}

static int decis[3];
static int dc = 0;

int decode_delta()
{
    if (dc == 0 || dc == 3) {
        dc = 0;
        int v = decode_bits(5);
        decis[0] = v%3; v /= 3;
        decis[1] = v%3; v /= 3;
        decis[2] = v;
    }
    return decis[dc++]-1;
}

void decode(int n, int h)
{
    for (int i = 1; i < n; ++i)
        par[i] = decode_bits(10);
    for (int i = 0; i < h; ++i) {
        for (int j = 1; j < n; ++j)
            chn[j] = decode_delta();
        fill(vis, vis+n, false);
        for (int j = 0; j < n; ++j)
            hops(i, j, solve(j)-solve(i));
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 11592 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4672 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 27 ms 5524 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 42 ms 5520 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 31 ms 5768 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 59 ms 6140 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 5532 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5512 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5496 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 38 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 30 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 6192 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5592 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 37 ms 5652 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6092 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 55 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 56 ms 5948 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 89 ms 6508 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 79 ms 6628 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 71 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 110 ms 6928 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 11592 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4672 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 27 ms 5524 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 42 ms 5520 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 31 ms 5768 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 59 ms 6140 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 5532 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5512 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5496 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 38 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 30 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 6192 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5592 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 37 ms 5652 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6092 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 55 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 56 ms 5948 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 89 ms 6508 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 79 ms 6628 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 71 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 110 ms 6928 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 11592 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4672 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 27 ms 5524 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 42 ms 5520 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 31 ms 5768 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 59 ms 6140 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 5532 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5512 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5496 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 38 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 30 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 6192 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5592 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 37 ms 5652 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6092 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 55 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 56 ms 5948 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 89 ms 6508 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 79 ms 6628 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 71 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 110 ms 6928 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 11592 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 4 ms 4672 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 27 ms 5524 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 42 ms 5520 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 31 ms 5768 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 59 ms 6140 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 5532 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 28 ms 5512 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5496 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 38 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 30 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 6192 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5592 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 37 ms 5652 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 6112 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 65 ms 6092 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 55 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 56 ms 5948 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 89 ms 6508 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 79 ms 6628 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 71 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 110 ms 6928 KB Output is correct - 69930 call(s) of encode_bit()