oj.uz

답안 #62159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62159 2018-07-27T15:51:55 Z reality 저장 (Saveit) (IOI10_saveit) C++17
100 / 100
 348 ms 11640 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()

#include "grader.h"

const int N = (int)(1e4) + 5;

void encode(int nv, int nh, int ne, int *a, int *b)
{
    static vi g[N];
    static int D[N];
    static int p[N];
    int n = nv;
    int nn = nh;
    int m = ne;
    for (int i = 1;i < n;++i)
        p[i] = -1,g[i].clear();
    for (int i = 0;i < m;++i)
        g[a[i]].pb(b[i]),g[b[i]].pb(a[i]);
    queue < int > Q;
    Q.push(0);
    while (!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        for (auto it : g[node])
            if (p[it] == -1)
                p[it] = node,Q.push(it);
    }
    for (int i = 1;i < n;++i)
        for (int j = 0;j < 10;++j)
            encode_bit((p[i] >> j) & 1);
    for (int i = 0;i < nn;++i)
    {
        queue < int > Q;
        for (int j = 0;j < n;++j)
            D[j] = 1e9;
        D[i] = 0;
        Q.push(i);
        while (!Q.empty())
        {
            int node = Q.front();
            Q.pop();
            for (auto it : g[node])
                if (D[it] > D[node] + 1)
                    D[it] = D[node] + 1,Q.push(it);
        }
        for (int j = 1;j < (n + 4);j += 5)
        {
            int t = 0,shit = 1;
            for (int k = j;k < min(n,j + 5);++k)
                t += (D[k] - D[p[k]] + 1) * shit,shit *= 3;
            for (int j = 0;j < 8;++j)
                encode_bit((t >> j) & 1);
        }
    }
}


#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()

#include "grader.h"

void decode(int nv, int nh)
{
    int n = nv;
    int nn = nh;
    static int p[1 << 10];
    for (int i = 1;i < n;++i)
        for (int j = 0;j < 10;++j)
            p[i] += (1 << j) * decode_bit();
    for (int i = 0;i < nn;++i)
    {
        static vector < pii > g[1 << 10];
        for (int j = 0;j < n;++j)
            g[j].clear();
        static int d[1 << 10];
        for (int j = 0;j < n;++j)
            d[j] = -1e9;
        for (int j = 1;j < (n + 4);j += 5)
        {
            int t = 0;
            for (int k = 0;k < 8;++k)
                t += (1 << k) * decode_bit();
            for (int k = j;k < min(j + 5,n);++k)
            {
                g[k].pb(mp(p[k],1 - (t % 3)));
                g[p[k]].pb(mp(k,(t % 3) - 1));
                t /= 3;
            }
        }
        queue < int > Q;
        Q.push(0);
        d[0] = 0;
        while (!Q.empty())
        {
            int node = Q.front();
            Q.pop();
            for (auto it : g[node])
                if (d[it.fi] == -1e9)
                    d[it.fi] = d[node] + it.se,Q.push(it.fi);
        }
        int mn = *min_element(d,d + n);
        for (int j = 0;j < n;++j)
            d[j] -= mn;
        for (int j = 0;j < n;++j)
            hops(i,j,d[j]);
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 11640 KB Output is correct - 67878 call(s) of encode_bit()
2 Correct 6 ms 4940 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 32 ms 5836 KB Output is correct - 61118 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 33 ms 5904 KB Output is correct - 61118 call(s) of encode_bit()
6 Correct 35 ms 5884 KB Output is correct - 67878 call(s) of encode_bit()
7 Correct 54 ms 6300 KB Output is correct - 67878 call(s) of encode_bit()
8 Correct 27 ms 5608 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 31 ms 5696 KB Output is correct - 67878 call(s) of encode_bit()
10 Correct 36 ms 5708 KB Output is correct - 67878 call(s) of encode_bit()
11 Correct 42 ms 5868 KB Output is correct - 67878 call(s) of encode_bit()
12 Correct 31 ms 5780 KB Output is correct - 67878 call(s) of encode_bit()
13 Correct 71 ms 6476 KB Output is correct - 67878 call(s) of encode_bit()
14 Correct 34 ms 5692 KB Output is correct - 67878 call(s) of encode_bit()
15 Correct 34 ms 5848 KB Output is correct - 67878 call(s) of encode_bit()
16 Correct 81 ms 6204 KB Output is correct - 67878 call(s) of encode_bit()
17 Correct 56 ms 6188 KB Output is correct - 67878 call(s) of encode_bit()
18 Correct 72 ms 6596 KB Output is correct - 67878 call(s) of encode_bit()
19 Correct 68 ms 6028 KB Output is correct - 67878 call(s) of encode_bit()
20 Correct 91 ms 6576 KB Output is correct - 67878 call(s) of encode_bit()
21 Correct 121 ms 6848 KB Output is correct - 67878 call(s) of encode_bit()
22 Correct 71 ms 6436 KB Output is correct - 67878 call(s) of encode_bit()
23 Correct 72 ms 7144 KB Output is correct - 67878 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 11640 KB Output is correct - 67878 call(s) of encode_bit()
2 Correct 6 ms 4940 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 32 ms 5836 KB Output is correct - 61118 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 33 ms 5904 KB Output is correct - 61118 call(s) of encode_bit()
6 Correct 35 ms 5884 KB Output is correct - 67878 call(s) of encode_bit()
7 Correct 54 ms 6300 KB Output is correct - 67878 call(s) of encode_bit()
8 Correct 27 ms 5608 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 31 ms 5696 KB Output is correct - 67878 call(s) of encode_bit()
10 Correct 36 ms 5708 KB Output is correct - 67878 call(s) of encode_bit()
11 Correct 42 ms 5868 KB Output is correct - 67878 call(s) of encode_bit()
12 Correct 31 ms 5780 KB Output is correct - 67878 call(s) of encode_bit()
13 Correct 71 ms 6476 KB Output is correct - 67878 call(s) of encode_bit()
14 Correct 34 ms 5692 KB Output is correct - 67878 call(s) of encode_bit()
15 Correct 34 ms 5848 KB Output is correct - 67878 call(s) of encode_bit()
16 Correct 81 ms 6204 KB Output is correct - 67878 call(s) of encode_bit()
17 Correct 56 ms 6188 KB Output is correct - 67878 call(s) of encode_bit()
18 Correct 72 ms 6596 KB Output is correct - 67878 call(s) of encode_bit()
19 Correct 68 ms 6028 KB Output is correct - 67878 call(s) of encode_bit()
20 Correct 91 ms 6576 KB Output is correct - 67878 call(s) of encode_bit()
21 Correct 121 ms 6848 KB Output is correct - 67878 call(s) of encode_bit()
22 Correct 71 ms 6436 KB Output is correct - 67878 call(s) of encode_bit()
23 Correct 72 ms 7144 KB Output is correct - 67878 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 11640 KB Output is correct - 67878 call(s) of encode_bit()
2 Correct 6 ms 4940 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 32 ms 5836 KB Output is correct - 61118 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 33 ms 5904 KB Output is correct - 61118 call(s) of encode_bit()
6 Correct 35 ms 5884 KB Output is correct - 67878 call(s) of encode_bit()
7 Correct 54 ms 6300 KB Output is correct - 67878 call(s) of encode_bit()
8 Correct 27 ms 5608 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 31 ms 5696 KB Output is correct - 67878 call(s) of encode_bit()
10 Correct 36 ms 5708 KB Output is correct - 67878 call(s) of encode_bit()
11 Correct 42 ms 5868 KB Output is correct - 67878 call(s) of encode_bit()
12 Correct 31 ms 5780 KB Output is correct - 67878 call(s) of encode_bit()
13 Correct 71 ms 6476 KB Output is correct - 67878 call(s) of encode_bit()
14 Correct 34 ms 5692 KB Output is correct - 67878 call(s) of encode_bit()
15 Correct 34 ms 5848 KB Output is correct - 67878 call(s) of encode_bit()
16 Correct 81 ms 6204 KB Output is correct - 67878 call(s) of encode_bit()
17 Correct 56 ms 6188 KB Output is correct - 67878 call(s) of encode_bit()
18 Correct 72 ms 6596 KB Output is correct - 67878 call(s) of encode_bit()
19 Correct 68 ms 6028 KB Output is correct - 67878 call(s) of encode_bit()
20 Correct 91 ms 6576 KB Output is correct - 67878 call(s) of encode_bit()
21 Correct 121 ms 6848 KB Output is correct - 67878 call(s) of encode_bit()
22 Correct 71 ms 6436 KB Output is correct - 67878 call(s) of encode_bit()
23 Correct 72 ms 7144 KB Output is correct - 67878 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 11640 KB Output is correct - 67878 call(s) of encode_bit()
2 Correct 6 ms 4940 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 32 ms 5836 KB Output is correct - 61118 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 33 ms 5904 KB Output is correct - 61118 call(s) of encode_bit()
6 Correct 35 ms 5884 KB Output is correct - 67878 call(s) of encode_bit()
7 Correct 54 ms 6300 KB Output is correct - 67878 call(s) of encode_bit()
8 Correct 27 ms 5608 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 31 ms 5696 KB Output is correct - 67878 call(s) of encode_bit()
10 Correct 36 ms 5708 KB Output is correct - 67878 call(s) of encode_bit()
11 Correct 42 ms 5868 KB Output is correct - 67878 call(s) of encode_bit()
12 Correct 31 ms 5780 KB Output is correct - 67878 call(s) of encode_bit()
13 Correct 71 ms 6476 KB Output is correct - 67878 call(s) of encode_bit()
14 Correct 34 ms 5692 KB Output is correct - 67878 call(s) of encode_bit()
15 Correct 34 ms 5848 KB Output is correct - 67878 call(s) of encode_bit()
16 Correct 81 ms 6204 KB Output is correct - 67878 call(s) of encode_bit()
17 Correct 56 ms 6188 KB Output is correct - 67878 call(s) of encode_bit()
18 Correct 72 ms 6596 KB Output is correct - 67878 call(s) of encode_bit()
19 Correct 68 ms 6028 KB Output is correct - 67878 call(s) of encode_bit()
20 Correct 91 ms 6576 KB Output is correct - 67878 call(s) of encode_bit()
21 Correct 121 ms 6848 KB Output is correct - 67878 call(s) of encode_bit()
22 Correct 71 ms 6436 KB Output is correct - 67878 call(s) of encode_bit()
23 Correct 72 ms 7144 KB Output is correct - 67878 call(s) of encode_bit()