oj.uz

Submission #205186

# Submission time Handle Problem Language Result Execution time Memory
205186 2020-02-28T09:14:09 Z stefdasca Saveit (IOI10_saveit) C++14
0 / 100
 217 ms 11600 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;

vector<int> v[1002];

int dist[40][1002], tt[40][1002], state[1002];
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]);
    }
    for(int i = 0; i < h; ++i)
    {
        dist[i][i] = 1;
        deque<int> d;
        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;
                    tt[i][vecin] = nod;
                    d.push_back(vecin);
                }
            }
        }
        if(i == 0)
            for(int j = 1; j < n; ++j)
                for(int x = 0; x < 10; ++x)
                    encode_bit((tt[0][j] & (1<<x)) != 0);
        for(int j = 0; j < n; ++j)
        {
            if(dist[i][j] == dist[i][tt[0][j]])
                state[j] = 0;
            else
                if(dist[i][j] > dist[i][tt[0][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-1, j + 4); ++x)
                msk = msk * 3 + state[x];
            for(int pw = 0; pw <= 7; ++pw)
                encode_bit((msk & (1<<pw)) != 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 = 1; 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, -1, 0);
        for(int j = 0; j < n; ++j)
            hops(i, j, dist[i][j]);
    }

}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:25: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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 11600 KB wrong parameter
2 Incorrect 11 ms 4676 KB wrong parameter
3 Incorrect 27 ms 5440 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 30 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5816 KB wrong parameter
7 Incorrect 44 ms 6336 KB wrong parameter
8 Incorrect 27 ms 5440 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 31 ms 5568 KB wrong parameter
11 Incorrect 32 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5440 KB wrong parameter
13 Incorrect 55 ms 6240 KB wrong parameter
14 Incorrect 28 ms 5568 KB wrong parameter
15 Incorrect 30 ms 5828 KB wrong parameter
16 Incorrect 49 ms 6208 KB wrong parameter
17 Incorrect 46 ms 5952 KB wrong parameter
18 Incorrect 53 ms 6336 KB wrong parameter
19 Incorrect 45 ms 5952 KB wrong parameter
20 Incorrect 57 ms 6720 KB wrong parameter
21 Incorrect 67 ms 6720 KB wrong parameter
22 Incorrect 48 ms 6152 KB wrong parameter
23 Incorrect 73 ms 6848 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 11600 KB wrong parameter
2 Incorrect 11 ms 4676 KB wrong parameter
3 Incorrect 27 ms 5440 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 30 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5816 KB wrong parameter
7 Incorrect 44 ms 6336 KB wrong parameter
8 Incorrect 27 ms 5440 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 31 ms 5568 KB wrong parameter
11 Incorrect 32 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5440 KB wrong parameter
13 Incorrect 55 ms 6240 KB wrong parameter
14 Incorrect 28 ms 5568 KB wrong parameter
15 Incorrect 30 ms 5828 KB wrong parameter
16 Incorrect 49 ms 6208 KB wrong parameter
17 Incorrect 46 ms 5952 KB wrong parameter
18 Incorrect 53 ms 6336 KB wrong parameter
19 Incorrect 45 ms 5952 KB wrong parameter
20 Incorrect 57 ms 6720 KB wrong parameter
21 Incorrect 67 ms 6720 KB wrong parameter
22 Incorrect 48 ms 6152 KB wrong parameter
23 Incorrect 73 ms 6848 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 11600 KB wrong parameter
2 Incorrect 11 ms 4676 KB wrong parameter
3 Incorrect 27 ms 5440 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 30 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5816 KB wrong parameter
7 Incorrect 44 ms 6336 KB wrong parameter
8 Incorrect 27 ms 5440 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 31 ms 5568 KB wrong parameter
11 Incorrect 32 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5440 KB wrong parameter
13 Incorrect 55 ms 6240 KB wrong parameter
14 Incorrect 28 ms 5568 KB wrong parameter
15 Incorrect 30 ms 5828 KB wrong parameter
16 Incorrect 49 ms 6208 KB wrong parameter
17 Incorrect 46 ms 5952 KB wrong parameter
18 Incorrect 53 ms 6336 KB wrong parameter
19 Incorrect 45 ms 5952 KB wrong parameter
20 Incorrect 57 ms 6720 KB wrong parameter
21 Incorrect 67 ms 6720 KB wrong parameter
22 Incorrect 48 ms 6152 KB wrong parameter
23 Incorrect 73 ms 6848 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 11600 KB wrong parameter
2 Incorrect 11 ms 4676 KB wrong parameter
3 Incorrect 27 ms 5440 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 30 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5816 KB wrong parameter
7 Incorrect 44 ms 6336 KB wrong parameter
8 Incorrect 27 ms 5440 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 31 ms 5568 KB wrong parameter
11 Incorrect 32 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5440 KB wrong parameter
13 Incorrect 55 ms 6240 KB wrong parameter
14 Incorrect 28 ms 5568 KB wrong parameter
15 Incorrect 30 ms 5828 KB wrong parameter
16 Incorrect 49 ms 6208 KB wrong parameter
17 Incorrect 46 ms 5952 KB wrong parameter
18 Incorrect 53 ms 6336 KB wrong parameter
19 Incorrect 45 ms 5952 KB wrong parameter
20 Incorrect 57 ms 6720 KB wrong parameter
21 Incorrect 67 ms 6720 KB wrong parameter
22 Incorrect 48 ms 6152 KB wrong parameter
23 Incorrect 73 ms 6848 KB wrong parameter