oj.uz

Submission #205221

# Submission time Handle Problem Language Result Execution time Memory
205221 2020-02-28T10:33:48 Z stefdasca Saveit (IOI10_saveit) C++14
0 / 100
 224 ms 11504 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;
        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:43: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 224 ms 11504 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 27 ms 5604 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 31 ms 5824 KB wrong parameter
7 Incorrect 46 ms 6284 KB wrong parameter
8 Incorrect 33 ms 5572 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 35 ms 5572 KB wrong parameter
11 Incorrect 34 ms 5788 KB wrong parameter
12 Incorrect 31 ms 5744 KB wrong parameter
13 Incorrect 54 ms 6372 KB wrong parameter
14 Incorrect 30 ms 5752 KB wrong parameter
15 Incorrect 36 ms 5828 KB wrong parameter
16 Incorrect 52 ms 6080 KB wrong parameter
17 Incorrect 47 ms 6212 KB wrong parameter
18 Incorrect 54 ms 6336 KB wrong parameter
19 Incorrect 39 ms 5952 KB wrong parameter
20 Incorrect 74 ms 6596 KB wrong parameter
21 Incorrect 71 ms 7004 KB wrong parameter
22 Incorrect 52 ms 6376 KB wrong parameter
23 Incorrect 70 ms 7132 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 11504 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 27 ms 5604 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 31 ms 5824 KB wrong parameter
7 Incorrect 46 ms 6284 KB wrong parameter
8 Incorrect 33 ms 5572 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 35 ms 5572 KB wrong parameter
11 Incorrect 34 ms 5788 KB wrong parameter
12 Incorrect 31 ms 5744 KB wrong parameter
13 Incorrect 54 ms 6372 KB wrong parameter
14 Incorrect 30 ms 5752 KB wrong parameter
15 Incorrect 36 ms 5828 KB wrong parameter
16 Incorrect 52 ms 6080 KB wrong parameter
17 Incorrect 47 ms 6212 KB wrong parameter
18 Incorrect 54 ms 6336 KB wrong parameter
19 Incorrect 39 ms 5952 KB wrong parameter
20 Incorrect 74 ms 6596 KB wrong parameter
21 Incorrect 71 ms 7004 KB wrong parameter
22 Incorrect 52 ms 6376 KB wrong parameter
23 Incorrect 70 ms 7132 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 11504 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 27 ms 5604 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 31 ms 5824 KB wrong parameter
7 Incorrect 46 ms 6284 KB wrong parameter
8 Incorrect 33 ms 5572 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 35 ms 5572 KB wrong parameter
11 Incorrect 34 ms 5788 KB wrong parameter
12 Incorrect 31 ms 5744 KB wrong parameter
13 Incorrect 54 ms 6372 KB wrong parameter
14 Incorrect 30 ms 5752 KB wrong parameter
15 Incorrect 36 ms 5828 KB wrong parameter
16 Incorrect 52 ms 6080 KB wrong parameter
17 Incorrect 47 ms 6212 KB wrong parameter
18 Incorrect 54 ms 6336 KB wrong parameter
19 Incorrect 39 ms 5952 KB wrong parameter
20 Incorrect 74 ms 6596 KB wrong parameter
21 Incorrect 71 ms 7004 KB wrong parameter
22 Incorrect 52 ms 6376 KB wrong parameter
23 Incorrect 70 ms 7132 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 11504 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 27 ms 5604 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 31 ms 5824 KB wrong parameter
7 Incorrect 46 ms 6284 KB wrong parameter
8 Incorrect 33 ms 5572 KB wrong parameter
9 Incorrect 31 ms 5568 KB wrong parameter
10 Incorrect 35 ms 5572 KB wrong parameter
11 Incorrect 34 ms 5788 KB wrong parameter
12 Incorrect 31 ms 5744 KB wrong parameter
13 Incorrect 54 ms 6372 KB wrong parameter
14 Incorrect 30 ms 5752 KB wrong parameter
15 Incorrect 36 ms 5828 KB wrong parameter
16 Incorrect 52 ms 6080 KB wrong parameter
17 Incorrect 47 ms 6212 KB wrong parameter
18 Incorrect 54 ms 6336 KB wrong parameter
19 Incorrect 39 ms 5952 KB wrong parameter
20 Incorrect 74 ms 6596 KB wrong parameter
21 Incorrect 71 ms 7004 KB wrong parameter
22 Incorrect 52 ms 6376 KB wrong parameter
23 Incorrect 70 ms 7132 KB wrong parameter