oj.uz

Submission #205227

# Submission time Handle Problem Language Result Execution time Memory
205227 2020-02-28T10:46:10 Z stefdasca Saveit (IOI10_saveit) C++14
100 / 100
 263 ms 11496 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;

vector<int> v[1002];

int dist[40][1002], tt[1002], state[1002];

bool viz[1002];

void dfs(int dad, int nod)
{
    viz[nod] = 1;
    tt[nod] = dad;
    for(int i = 0; i < v[nod].size(); ++i)
        if(!viz[v[nod][i]])
            dfs(nod, v[nod][i]);
}
void encode(int n, int h, int m, int *a, int *b)
{
    for(int i = 0; i < m; ++i)
    {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    dfs(0, 0);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j <= 9; ++j)
            if(tt[i] & (1<<j))
                encode_bit(1);
            else
                encode_bit(0);
    for(int i = 0; i < h; ++i)
    {
        dist[i][i] = 1;
        deque<int> d;
        d.push_back(i);
        while(!d.empty())
        {
            int nod = d[0];
            d.pop_front();
            for(int x = 0; x < v[nod].size(); ++x)
            {
                int vecin = v[nod][x];
                if(!dist[i][vecin])
                {
                    dist[i][vecin] = dist[i][nod] + 1;
                    d.push_back(vecin);
                }
            }
        }
        for(int j = 0; j < n; ++j)
        {
            if(dist[i][j] == dist[i][tt[j]])
                state[j] = 0;
            else
                if(dist[i][j] > dist[i][tt[j]])
                    state[j] = 1;
                else
                    state[j] = 2;
        }
        // 5 states with 8 bits
        for(int j = 0; j < n; j += 5)
        {
            int msk = 0;
            for(int x = j; x < min(n, j + 5); ++x)
                msk = msk * 3 + state[x];
            for(int pw = 0; pw <= 7; ++pw)
                if(msk & (1<<pw))
                    encode_bit(1);
                else
                    encode_bit(0);
        }
    }
}


#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

using namespace std;

vector<int> v[1002];

int tt[1002], dist[40][1002], state[1002];

void dfs(int h, int dad, int nod)
{
    dist[h][nod] = dist[h][tt[nod]] + (state[nod] + 1) % 3 - 1;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        dfs(h, nod, vecin);
    }
}
void decode(int n, int h)
{
    for(int i = 0; i < n; ++i)
    {
        int wh = 0;
        for(int j = 0; j <= 9; ++j)
            wh = wh + (1<<j) * decode_bit();
        tt[i] = wh;
        v[wh].push_back(i);
    }
    for(int i = 0; i < h; ++i)
    {
        for(int j = 0; j < n; j += 5)
        {
            int val = 0;
            for(int xx = 0; xx <= 7; ++xx)
                val = val + decode_bit() * (1<<xx);
            for(int xx = min(n - 1, j + 4); xx >= j; --xx)
            {
                state[xx] = val % 3;
                val /= 3;
            }
        }

        int nd = i;
        while(nd != tt[nd])
        {
            dist[i][tt[nd]] = dist[i][nd] - (state[nd] + 1) % 3 + 1;
            nd = tt[nd];
        }
        dfs(i, 0, 0);
        for(int j = 0; j < n; ++j)
            hops(i, j, dist[i][j]);
    }

}

Compilation message

encoder.cpp: In function 'void dfs(int, int)':
encoder.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:44:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int x = 0; x < v[nod].size(); ++x)
                            ~~^~~~~~~~~~~~~~~

decoder.cpp: In function 'void dfs(int, int, int)':
decoder.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 11496 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 12 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 36 ms 5952 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 6084 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 52 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 40 ms 5864 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 40 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 37 ms 5968 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 39 ms 6044 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 37 ms 5828 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 61 ms 6680 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 39 ms 5700 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 39 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 56 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 52 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 65 ms 6592 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 57 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 73 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 84 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 59 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 87 ms 7200 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 11496 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 12 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 36 ms 5952 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 6084 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 52 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 40 ms 5864 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 40 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 37 ms 5968 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 39 ms 6044 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 37 ms 5828 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 61 ms 6680 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 39 ms 5700 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 39 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 56 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 52 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 65 ms 6592 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 57 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 73 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 84 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 59 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 87 ms 7200 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 11496 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 12 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 36 ms 5952 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 6084 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 52 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 40 ms 5864 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 40 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 37 ms 5968 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 39 ms 6044 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 37 ms 5828 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 61 ms 6680 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 39 ms 5700 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 39 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 56 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 52 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 65 ms 6592 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 57 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 73 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 84 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 59 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 87 ms 7200 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 11496 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 12 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 5568 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 12 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 36 ms 5952 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 6084 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 52 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 40 ms 5864 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 40 ms 5864 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 37 ms 5968 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 39 ms 6044 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 37 ms 5828 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 61 ms 6680 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 39 ms 5700 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 39 ms 5956 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 56 ms 6336 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 52 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 65 ms 6592 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 57 ms 6212 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 73 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 84 ms 6980 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 59 ms 6464 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 87 ms 7200 KB Output is correct - 67600 call(s) of encode_bit()