oj.uz

Submission #205198

# Submission time Handle Problem Language Result Execution time Memory
205198 2020-02-28T09:43:09 Z stefdasca Saveit (IOI10_saveit) C++14
0 / 100
 219 ms 11760 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, j + 5); ++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 219 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 33 ms 5464 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 28 ms 6080 KB wrong parameter
6 Incorrect 33 ms 5828 KB wrong parameter
7 Incorrect 46 ms 6112 KB wrong parameter
8 Incorrect 28 ms 5440 KB wrong parameter
9 Incorrect 30 ms 5808 KB wrong parameter
10 Incorrect 30 ms 5572 KB wrong parameter
11 Incorrect 31 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5452 KB wrong parameter
13 Incorrect 54 ms 6340 KB wrong parameter
14 Incorrect 30 ms 5576 KB wrong parameter
15 Incorrect 37 ms 5844 KB wrong parameter
16 Incorrect 67 ms 6208 KB wrong parameter
17 Incorrect 44 ms 6104 KB wrong parameter
18 Incorrect 57 ms 6336 KB wrong parameter
19 Incorrect 44 ms 5876 KB wrong parameter
20 Incorrect 67 ms 6532 KB wrong parameter
21 Incorrect 72 ms 6976 KB wrong parameter
22 Incorrect 49 ms 6208 KB wrong parameter
23 Incorrect 73 ms 6956 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 33 ms 5464 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 28 ms 6080 KB wrong parameter
6 Incorrect 33 ms 5828 KB wrong parameter
7 Incorrect 46 ms 6112 KB wrong parameter
8 Incorrect 28 ms 5440 KB wrong parameter
9 Incorrect 30 ms 5808 KB wrong parameter
10 Incorrect 30 ms 5572 KB wrong parameter
11 Incorrect 31 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5452 KB wrong parameter
13 Incorrect 54 ms 6340 KB wrong parameter
14 Incorrect 30 ms 5576 KB wrong parameter
15 Incorrect 37 ms 5844 KB wrong parameter
16 Incorrect 67 ms 6208 KB wrong parameter
17 Incorrect 44 ms 6104 KB wrong parameter
18 Incorrect 57 ms 6336 KB wrong parameter
19 Incorrect 44 ms 5876 KB wrong parameter
20 Incorrect 67 ms 6532 KB wrong parameter
21 Incorrect 72 ms 6976 KB wrong parameter
22 Incorrect 49 ms 6208 KB wrong parameter
23 Incorrect 73 ms 6956 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 33 ms 5464 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 28 ms 6080 KB wrong parameter
6 Incorrect 33 ms 5828 KB wrong parameter
7 Incorrect 46 ms 6112 KB wrong parameter
8 Incorrect 28 ms 5440 KB wrong parameter
9 Incorrect 30 ms 5808 KB wrong parameter
10 Incorrect 30 ms 5572 KB wrong parameter
11 Incorrect 31 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5452 KB wrong parameter
13 Incorrect 54 ms 6340 KB wrong parameter
14 Incorrect 30 ms 5576 KB wrong parameter
15 Incorrect 37 ms 5844 KB wrong parameter
16 Incorrect 67 ms 6208 KB wrong parameter
17 Incorrect 44 ms 6104 KB wrong parameter
18 Incorrect 57 ms 6336 KB wrong parameter
19 Incorrect 44 ms 5876 KB wrong parameter
20 Incorrect 67 ms 6532 KB wrong parameter
21 Incorrect 72 ms 6976 KB wrong parameter
22 Incorrect 49 ms 6208 KB wrong parameter
23 Incorrect 73 ms 6956 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 33 ms 5464 KB wrong parameter
4 Incorrect 12 ms 4672 KB wrong parameter
5 Incorrect 28 ms 6080 KB wrong parameter
6 Incorrect 33 ms 5828 KB wrong parameter
7 Incorrect 46 ms 6112 KB wrong parameter
8 Incorrect 28 ms 5440 KB wrong parameter
9 Incorrect 30 ms 5808 KB wrong parameter
10 Incorrect 30 ms 5572 KB wrong parameter
11 Incorrect 31 ms 5696 KB wrong parameter
12 Incorrect 30 ms 5452 KB wrong parameter
13 Incorrect 54 ms 6340 KB wrong parameter
14 Incorrect 30 ms 5576 KB wrong parameter
15 Incorrect 37 ms 5844 KB wrong parameter
16 Incorrect 67 ms 6208 KB wrong parameter
17 Incorrect 44 ms 6104 KB wrong parameter
18 Incorrect 57 ms 6336 KB wrong parameter
19 Incorrect 44 ms 5876 KB wrong parameter
20 Incorrect 67 ms 6532 KB wrong parameter
21 Incorrect 72 ms 6976 KB wrong parameter
22 Incorrect 49 ms 6208 KB wrong parameter
23 Incorrect 73 ms 6956 KB wrong parameter