oj.uz

답안 #271291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
271291 2020-08-18T05:32:59 Z 반딧불(#5113) 저장 (Saveit) (IOI10_saveit) C++14
75 / 100
 278 ms 11680 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;

namespace{
    int n, k, m;
    vector<int> link[1002];
    int dist[40][1002];
    int par[1002];

    void makeTree(int x, int p = 1004){
        par[x] = p;
        for(auto &y: link[x]){
            if(par[y] != 1004 || y==0) continue;
            makeTree(y, x);
        }
    }

    void bfs(int h){
        bool visited[1002] = {0};
        queue<pair<int, int> > que;
        que.push({h, 0});
        visited[h] = 1;

        while(!que.empty()){
            pair<int, int> tmp = que.front();
            int x = tmp.first, d = tmp.second;
            que.pop();
            for(auto &y: link[x]){
                if(visited[y]) continue;
                visited[y] = 1;
                dist[h][y] = d+1;
                que.push({y, d+1});
            }
        }
    }
}

void encode(int N, int K, int M, int *U, int *V){
    n = N, k = K, m = M;
    for(int i=0; i<m; i++){
        link[U[i]].push_back(V[i]);
        link[V[i]].push_back(U[i]);
    }

    for(int i=0; i<n; i++) par[i] = 1004;
    makeTree(0);

    for(int x=0; x<k; x++){
        bfs(x);
    }

    for(int i=1; i<n; i++){
        for(int j=0; j<10; j++) encode_bit(!!(par[i] & (1<<j)));
    }

    int kxx[]={1, 3, 9};
    for(int d=0; d<k; d++){
        for(int j=0; j<10; j++) encode_bit(!!(dist[d][0] & (1<<j)));
        for(int i=1; i<n; i+=3){
            int tmp = 0;
            for(int x=i; x<i+3 && x<n; x++){
                tmp += kxx[x-i] * (dist[d][x] - dist[d][par[x]] + 1);
            }
            for(int j=0; j<5; j++) encode_bit(!!(tmp & (1<<j)));
        }
    }
}

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

using namespace std;

namespace{
    int n, k;
    int par[1002];
    vector<int> childs[1002];
    int weight[1002];
}

void dfs(int x, int sum = 0){
    weight[x] += sum;
    for(auto &y: childs[x]){
        dfs(y, weight[x]);
    }
}

void decode(int N, int K){
    n = N, k = K;
    for(int i=1; i<n; i++){
        int tmp = 0;
        for(int j=0; j<10; j++){
            tmp += (1<<j) * decode_bit();
        }
        par[i] = tmp;
        childs[tmp].push_back(i);
    }

    for(int d=0; d<k; d++){
        int base = 0;
        for(int j=0; j<10; j++) base += (1<<j) * decode_bit();
        for(int i=1; i<n; i+=3){
            int tmp = 0;
            for(int j=0; j<5; j++) tmp += (1<<j) * decode_bit();

            weight[i] = tmp%3, weight[i+1] = (tmp/3)%3, weight[i+2] = tmp/9;
            weight[i]--, weight[i+1]--, weight[i+2]--;
        }

        dfs(0);
        for(int i=0; i<n; i++){
            hops(d, i, base + weight[i]);
        }
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 11680 KB Output is partially correct - 70290 call(s) of encode_bit()
2 Correct 4 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 63350 call(s) of encode_bit()
4 Correct 3 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 31 ms 6024 KB Output is correct - 63350 call(s) of encode_bit()
6 Correct 38 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
7 Correct 57 ms 6276 KB Output is partially correct - 70290 call(s) of encode_bit()
8 Correct 27 ms 5760 KB Output is correct - 67560 call(s) of encode_bit()
9 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
10 Correct 33 ms 5760 KB Output is partially correct - 70290 call(s) of encode_bit()
11 Correct 41 ms 5772 KB Output is partially correct - 70290 call(s) of encode_bit()
12 Correct 31 ms 5892 KB Output is partially correct - 70290 call(s) of encode_bit()
13 Correct 70 ms 6308 KB Output is partially correct - 70290 call(s) of encode_bit()
14 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
16 Correct 61 ms 6264 KB Output is partially correct - 70290 call(s) of encode_bit()
17 Correct 52 ms 6304 KB Output is partially correct - 70290 call(s) of encode_bit()
18 Correct 73 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
19 Correct 46 ms 6224 KB Output is partially correct - 70290 call(s) of encode_bit()
20 Correct 70 ms 6940 KB Output is partially correct - 70290 call(s) of encode_bit()
21 Correct 81 ms 6904 KB Output is partially correct - 70290 call(s) of encode_bit()
22 Correct 62 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
23 Correct 97 ms 7360 KB Output is partially correct - 70290 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 11680 KB Output is partially correct - 70290 call(s) of encode_bit()
2 Correct 4 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 63350 call(s) of encode_bit()
4 Correct 3 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 31 ms 6024 KB Output is correct - 63350 call(s) of encode_bit()
6 Correct 38 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
7 Correct 57 ms 6276 KB Output is partially correct - 70290 call(s) of encode_bit()
8 Correct 27 ms 5760 KB Output is correct - 67560 call(s) of encode_bit()
9 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
10 Correct 33 ms 5760 KB Output is partially correct - 70290 call(s) of encode_bit()
11 Correct 41 ms 5772 KB Output is partially correct - 70290 call(s) of encode_bit()
12 Correct 31 ms 5892 KB Output is partially correct - 70290 call(s) of encode_bit()
13 Correct 70 ms 6308 KB Output is partially correct - 70290 call(s) of encode_bit()
14 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
16 Correct 61 ms 6264 KB Output is partially correct - 70290 call(s) of encode_bit()
17 Correct 52 ms 6304 KB Output is partially correct - 70290 call(s) of encode_bit()
18 Correct 73 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
19 Correct 46 ms 6224 KB Output is partially correct - 70290 call(s) of encode_bit()
20 Correct 70 ms 6940 KB Output is partially correct - 70290 call(s) of encode_bit()
21 Correct 81 ms 6904 KB Output is partially correct - 70290 call(s) of encode_bit()
22 Correct 62 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
23 Correct 97 ms 7360 KB Output is partially correct - 70290 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 11680 KB Output is partially correct - 70290 call(s) of encode_bit()
2 Correct 4 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 63350 call(s) of encode_bit()
4 Correct 3 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 31 ms 6024 KB Output is correct - 63350 call(s) of encode_bit()
6 Correct 38 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
7 Correct 57 ms 6276 KB Output is partially correct - 70290 call(s) of encode_bit()
8 Correct 27 ms 5760 KB Output is correct - 67560 call(s) of encode_bit()
9 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
10 Correct 33 ms 5760 KB Output is partially correct - 70290 call(s) of encode_bit()
11 Correct 41 ms 5772 KB Output is partially correct - 70290 call(s) of encode_bit()
12 Correct 31 ms 5892 KB Output is partially correct - 70290 call(s) of encode_bit()
13 Correct 70 ms 6308 KB Output is partially correct - 70290 call(s) of encode_bit()
14 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
16 Correct 61 ms 6264 KB Output is partially correct - 70290 call(s) of encode_bit()
17 Correct 52 ms 6304 KB Output is partially correct - 70290 call(s) of encode_bit()
18 Correct 73 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
19 Correct 46 ms 6224 KB Output is partially correct - 70290 call(s) of encode_bit()
20 Correct 70 ms 6940 KB Output is partially correct - 70290 call(s) of encode_bit()
21 Correct 81 ms 6904 KB Output is partially correct - 70290 call(s) of encode_bit()
22 Correct 62 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
23 Correct 97 ms 7360 KB Output is partially correct - 70290 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 11680 KB Output is partially correct - 70290 call(s) of encode_bit()
2 Correct 4 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
3 Correct 28 ms 5760 KB Output is correct - 63350 call(s) of encode_bit()
4 Correct 3 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 31 ms 6024 KB Output is correct - 63350 call(s) of encode_bit()
6 Correct 38 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
7 Correct 57 ms 6276 KB Output is partially correct - 70290 call(s) of encode_bit()
8 Correct 27 ms 5760 KB Output is correct - 67560 call(s) of encode_bit()
9 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
10 Correct 33 ms 5760 KB Output is partially correct - 70290 call(s) of encode_bit()
11 Correct 41 ms 5772 KB Output is partially correct - 70290 call(s) of encode_bit()
12 Correct 31 ms 5892 KB Output is partially correct - 70290 call(s) of encode_bit()
13 Correct 70 ms 6308 KB Output is partially correct - 70290 call(s) of encode_bit()
14 Correct 30 ms 5824 KB Output is partially correct - 70290 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is partially correct - 70290 call(s) of encode_bit()
16 Correct 61 ms 6264 KB Output is partially correct - 70290 call(s) of encode_bit()
17 Correct 52 ms 6304 KB Output is partially correct - 70290 call(s) of encode_bit()
18 Correct 73 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
19 Correct 46 ms 6224 KB Output is partially correct - 70290 call(s) of encode_bit()
20 Correct 70 ms 6940 KB Output is partially correct - 70290 call(s) of encode_bit()
21 Correct 81 ms 6904 KB Output is partially correct - 70290 call(s) of encode_bit()
22 Correct 62 ms 6392 KB Output is partially correct - 70290 call(s) of encode_bit()
23 Correct 97 ms 7360 KB Output is partially correct - 70290 call(s) of encode_bit()