oj.uz

답안 #205184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205184 2020-02-28T09:06:54 Z stefdasca 저장 (Saveit) (IOI10_saveit) C++14
0 / 100
 225 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)
    {
        for(int j = 0; j < n; ++j)
            dist[i][j] = (1<<30);
        dist[i][i] = 0;
        deque<int> d;
        while(!d.empty())
        {
            int nod = d[0];
            d.pop_front();
            for(int i = 0; i < v[nod].size(); ++i)
            {
                int vecin = v[nod][i];
                if(dist[i][vecin] > dist[i][nod] + 1)
                {
                    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 * 3 + decode_bit();
            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:27:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v[nod].size(); ++i)
                            ~~^~~~~~~~~~~~~~~

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 225 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 32 ms 5476 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5696 KB wrong parameter
7 Incorrect 48 ms 6080 KB wrong parameter
8 Incorrect 30 ms 5652 KB wrong parameter
9 Incorrect 28 ms 5580 KB wrong parameter
10 Incorrect 32 ms 5568 KB wrong parameter
11 Incorrect 33 ms 5696 KB wrong parameter
12 Incorrect 28 ms 5440 KB wrong parameter
13 Incorrect 60 ms 6312 KB wrong parameter
14 Incorrect 30 ms 5584 KB wrong parameter
15 Incorrect 36 ms 5744 KB wrong parameter
16 Incorrect 55 ms 6336 KB wrong parameter
17 Incorrect 54 ms 6300 KB wrong parameter
18 Incorrect 55 ms 6448 KB wrong parameter
19 Incorrect 47 ms 5824 KB wrong parameter
20 Incorrect 77 ms 6556 KB wrong parameter
21 Incorrect 76 ms 6648 KB wrong parameter
22 Incorrect 55 ms 6212 KB wrong parameter
23 Incorrect 77 ms 6980 KB wrong parameter

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 225 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 32 ms 5476 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5696 KB wrong parameter
7 Incorrect 48 ms 6080 KB wrong parameter
8 Incorrect 30 ms 5652 KB wrong parameter
9 Incorrect 28 ms 5580 KB wrong parameter
10 Incorrect 32 ms 5568 KB wrong parameter
11 Incorrect 33 ms 5696 KB wrong parameter
12 Incorrect 28 ms 5440 KB wrong parameter
13 Incorrect 60 ms 6312 KB wrong parameter
14 Incorrect 30 ms 5584 KB wrong parameter
15 Incorrect 36 ms 5744 KB wrong parameter
16 Incorrect 55 ms 6336 KB wrong parameter
17 Incorrect 54 ms 6300 KB wrong parameter
18 Incorrect 55 ms 6448 KB wrong parameter
19 Incorrect 47 ms 5824 KB wrong parameter
20 Incorrect 77 ms 6556 KB wrong parameter
21 Incorrect 76 ms 6648 KB wrong parameter
22 Incorrect 55 ms 6212 KB wrong parameter
23 Incorrect 77 ms 6980 KB wrong parameter

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 225 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 32 ms 5476 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5696 KB wrong parameter
7 Incorrect 48 ms 6080 KB wrong parameter
8 Incorrect 30 ms 5652 KB wrong parameter
9 Incorrect 28 ms 5580 KB wrong parameter
10 Incorrect 32 ms 5568 KB wrong parameter
11 Incorrect 33 ms 5696 KB wrong parameter
12 Incorrect 28 ms 5440 KB wrong parameter
13 Incorrect 60 ms 6312 KB wrong parameter
14 Incorrect 30 ms 5584 KB wrong parameter
15 Incorrect 36 ms 5744 KB wrong parameter
16 Incorrect 55 ms 6336 KB wrong parameter
17 Incorrect 54 ms 6300 KB wrong parameter
18 Incorrect 55 ms 6448 KB wrong parameter
19 Incorrect 47 ms 5824 KB wrong parameter
20 Incorrect 77 ms 6556 KB wrong parameter
21 Incorrect 76 ms 6648 KB wrong parameter
22 Incorrect 55 ms 6212 KB wrong parameter
23 Incorrect 77 ms 6980 KB wrong parameter

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 225 ms 11760 KB wrong parameter
2 Incorrect 12 ms 4672 KB wrong parameter
3 Incorrect 32 ms 5476 KB wrong parameter
4 Incorrect 12 ms 4676 KB wrong parameter
5 Incorrect 33 ms 5700 KB wrong parameter
6 Incorrect 33 ms 5696 KB wrong parameter
7 Incorrect 48 ms 6080 KB wrong parameter
8 Incorrect 30 ms 5652 KB wrong parameter
9 Incorrect 28 ms 5580 KB wrong parameter
10 Incorrect 32 ms 5568 KB wrong parameter
11 Incorrect 33 ms 5696 KB wrong parameter
12 Incorrect 28 ms 5440 KB wrong parameter
13 Incorrect 60 ms 6312 KB wrong parameter
14 Incorrect 30 ms 5584 KB wrong parameter
15 Incorrect 36 ms 5744 KB wrong parameter
16 Incorrect 55 ms 6336 KB wrong parameter
17 Incorrect 54 ms 6300 KB wrong parameter
18 Incorrect 55 ms 6448 KB wrong parameter
19 Incorrect 47 ms 5824 KB wrong parameter
20 Incorrect 77 ms 6556 KB wrong parameter
21 Incorrect 76 ms 6648 KB wrong parameter
22 Incorrect 55 ms 6212 KB wrong parameter
23 Incorrect 77 ms 6980 KB wrong parameter