oj.uz

답안 #205204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205204 2020-02-28T09:55:41 Z stefdasca 저장 (Saveit) (IOI10_saveit) C++14
0 / 100
 10000 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(-1, 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10007 ms 11504 KB Time limit exceeded
2 Execution timed out 10027 ms 4776 KB Time limit exceeded
3 Execution timed out 10011 ms 5648 KB Time limit exceeded
4 Execution timed out 10011 ms 4676 KB Time limit exceeded
5 Execution timed out 10020 ms 5696 KB Time limit exceeded
6 Execution timed out 10071 ms 5700 KB Time limit exceeded
7 Execution timed out 10050 ms 6336 KB Time limit exceeded
8 Execution timed out 10035 ms 5448 KB Time limit exceeded
9 Execution timed out 10032 ms 5700 KB Time limit exceeded
10 Execution timed out 10044 ms 5568 KB Time limit exceeded
11 Execution timed out 10017 ms 5780 KB Time limit exceeded
12 Execution timed out 10065 ms 5564 KB Time limit exceeded
13 Execution timed out 10065 ms 6288 KB Time limit exceeded
14 Execution timed out 10007 ms 5712 KB Time limit exceeded
15 Execution timed out 10016 ms 5600 KB Time limit exceeded
16 Execution timed out 10012 ms 6332 KB Time limit exceeded
17 Execution timed out 10070 ms 6084 KB Time limit exceeded
18 Execution timed out 10059 ms 6340 KB Time limit exceeded
19 Execution timed out 10020 ms 5960 KB Time limit exceeded
20 Execution timed out 10015 ms 6652 KB Time limit exceeded
21 Execution timed out 10088 ms 6720 KB Time limit exceeded
22 Execution timed out 10013 ms 6340 KB Time limit exceeded
23 Execution timed out 10075 ms 7104 KB Time limit exceeded

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10007 ms 11504 KB Time limit exceeded
2 Execution timed out 10027 ms 4776 KB Time limit exceeded
3 Execution timed out 10011 ms 5648 KB Time limit exceeded
4 Execution timed out 10011 ms 4676 KB Time limit exceeded
5 Execution timed out 10020 ms 5696 KB Time limit exceeded
6 Execution timed out 10071 ms 5700 KB Time limit exceeded
7 Execution timed out 10050 ms 6336 KB Time limit exceeded
8 Execution timed out 10035 ms 5448 KB Time limit exceeded
9 Execution timed out 10032 ms 5700 KB Time limit exceeded
10 Execution timed out 10044 ms 5568 KB Time limit exceeded
11 Execution timed out 10017 ms 5780 KB Time limit exceeded
12 Execution timed out 10065 ms 5564 KB Time limit exceeded
13 Execution timed out 10065 ms 6288 KB Time limit exceeded
14 Execution timed out 10007 ms 5712 KB Time limit exceeded
15 Execution timed out 10016 ms 5600 KB Time limit exceeded
16 Execution timed out 10012 ms 6332 KB Time limit exceeded
17 Execution timed out 10070 ms 6084 KB Time limit exceeded
18 Execution timed out 10059 ms 6340 KB Time limit exceeded
19 Execution timed out 10020 ms 5960 KB Time limit exceeded
20 Execution timed out 10015 ms 6652 KB Time limit exceeded
21 Execution timed out 10088 ms 6720 KB Time limit exceeded
22 Execution timed out 10013 ms 6340 KB Time limit exceeded
23 Execution timed out 10075 ms 7104 KB Time limit exceeded

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10007 ms 11504 KB Time limit exceeded
2 Execution timed out 10027 ms 4776 KB Time limit exceeded
3 Execution timed out 10011 ms 5648 KB Time limit exceeded
4 Execution timed out 10011 ms 4676 KB Time limit exceeded
5 Execution timed out 10020 ms 5696 KB Time limit exceeded
6 Execution timed out 10071 ms 5700 KB Time limit exceeded
7 Execution timed out 10050 ms 6336 KB Time limit exceeded
8 Execution timed out 10035 ms 5448 KB Time limit exceeded
9 Execution timed out 10032 ms 5700 KB Time limit exceeded
10 Execution timed out 10044 ms 5568 KB Time limit exceeded
11 Execution timed out 10017 ms 5780 KB Time limit exceeded
12 Execution timed out 10065 ms 5564 KB Time limit exceeded
13 Execution timed out 10065 ms 6288 KB Time limit exceeded
14 Execution timed out 10007 ms 5712 KB Time limit exceeded
15 Execution timed out 10016 ms 5600 KB Time limit exceeded
16 Execution timed out 10012 ms 6332 KB Time limit exceeded
17 Execution timed out 10070 ms 6084 KB Time limit exceeded
18 Execution timed out 10059 ms 6340 KB Time limit exceeded
19 Execution timed out 10020 ms 5960 KB Time limit exceeded
20 Execution timed out 10015 ms 6652 KB Time limit exceeded
21 Execution timed out 10088 ms 6720 KB Time limit exceeded
22 Execution timed out 10013 ms 6340 KB Time limit exceeded
23 Execution timed out 10075 ms 7104 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10007 ms 11504 KB Time limit exceeded
2 Execution timed out 10027 ms 4776 KB Time limit exceeded
3 Execution timed out 10011 ms 5648 KB Time limit exceeded
4 Execution timed out 10011 ms 4676 KB Time limit exceeded
5 Execution timed out 10020 ms 5696 KB Time limit exceeded
6 Execution timed out 10071 ms 5700 KB Time limit exceeded
7 Execution timed out 10050 ms 6336 KB Time limit exceeded
8 Execution timed out 10035 ms 5448 KB Time limit exceeded
9 Execution timed out 10032 ms 5700 KB Time limit exceeded
10 Execution timed out 10044 ms 5568 KB Time limit exceeded
11 Execution timed out 10017 ms 5780 KB Time limit exceeded
12 Execution timed out 10065 ms 5564 KB Time limit exceeded
13 Execution timed out 10065 ms 6288 KB Time limit exceeded
14 Execution timed out 10007 ms 5712 KB Time limit exceeded
15 Execution timed out 10016 ms 5600 KB Time limit exceeded
16 Execution timed out 10012 ms 6332 KB Time limit exceeded
17 Execution timed out 10070 ms 6084 KB Time limit exceeded
18 Execution timed out 10059 ms 6340 KB Time limit exceeded
19 Execution timed out 10020 ms 5960 KB Time limit exceeded
20 Execution timed out 10015 ms 6652 KB Time limit exceeded
21 Execution timed out 10088 ms 6720 KB Time limit exceeded
22 Execution timed out 10013 ms 6340 KB Time limit exceeded
23 Execution timed out 10075 ms 7104 KB Time limit exceeded