oj.uz

Submission #565000

# Submission time Handle Problem Language Result Execution time Memory
565000 2022-05-20T07:26:56 Z shrimb Saveit (IOI10_saveit) C++17
50 / 100
 224 ms 14152 KB 
#include "grader.h"
#include "encoder.h"
#include"bits/stdc++.h"
using namespace std;


void encode(int n, int h, int p, int *v1, int *v2){
    vector<pair<int,int>> adj[n + 1];
    for (int i = 0 ; i < p ; i++) {
        adj[v1[i]].emplace_back(v2[i],i);
        adj[v2[i]].emplace_back(v1[i],i);
    }
    vector<bool> ye(p);
    for (int i = 0 ; i < h ; i++) {
        int dist[n];
        for (int j = 0 ; j < n ; j++) dist[j] = 0;
        dist[i] = 1;
        queue<int> q;
        q.push(i);
        while (q.size()) {
            auto cur = q.front();
            q.pop();
            for (auto [j,k] : adj[cur]) {
                if (!dist[j]) {
                    dist[j] = 1;
                    ye[k] = 1;
                    q.push(j);
                }
            }
        }
    }
    vector<int> adj2[n];
    vector<int> cnt(n);
    for (int i = 0 ; i < p ; i++) {
        if (ye[i]) {
            cnt[v1[i]]++;
            cnt[v2[i]]++;
        }
    }
    for (int i = 0 ; i < p ; i++) {
        if (ye[i]) {
            if (cnt[v1[i]] > cnt[v2[i]]) {
                adj2[v1[i]].push_back(v2[i]);
            } else {
                adj2[v2[i]].push_back(v1[i]);
            }
        }
    }

    auto givenum = [&](int x) {
        for (int k = 0 ; k < 10 ; k++) encode_bit(bool(x & (1 << k)));
    };

    for (int i = 0 ; i < n ; i++) {
        if (adj2[i].size()) {
            givenum(i);
            for(int j : adj2[i]) givenum(j);
            for (int i = 0 ; i < 10 ; i++) encode_bit(1);
        }
    }
    for (int i = 0 ; i < 10 ; i++) encode_bit(1);
}

#include "grader.h"
#include "decoder.h"
#include "bits/stdc++.h"
using namespace std;
void decode(int n, int h) {

    auto getnum = [&]() -> int {
        int ret = 0;
        for (int k = 0 ; k < 10 ; k++) {
            ret |= (1 << k) * decode_bit();
        }
        return ret;
    };

    vector<int> adj[n];

    while (true) {
        int a = getnum();
        if (__builtin_popcount(a) == 10) break;
        while (true) {
            int b = getnum();
            if (__builtin_popcount(b) == 10) break;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }

    for (int i = 0 ; i < h ; i++) {
        int dist[n];
        for (int j = 0 ; j < n ; j++) dist[j] = INT_MAX;
        queue<int> q;
        q.push(i);
        dist[i] = 0;
        while (q.size()) {
            auto cur = q.front();
            q.pop();
            for (int j : adj[cur]) {
                if (dist[j] > dist[cur] + 1) {
                    dist[j] = dist[cur] + 1;
                    q.push(j);
                }
            }
        }
        for (int j = 0 ; j < n ; j++) hops(i, j, dist[j]);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 14152 KB Output is partially correct - 178030 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 26 ms 5424 KB Output is correct - 48690 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 160 call(s) of encode_bit()
5 Correct 39 ms 6144 KB Output is partially correct - 107970 call(s) of encode_bit()
6 Correct 35 ms 6048 KB Output is partially correct - 111990 call(s) of encode_bit()
7 Correct 62 ms 7448 KB Output is partially correct - 197690 call(s) of encode_bit()
8 Correct 19 ms 5212 KB Output is correct - 36670 call(s) of encode_bit()
9 Correct 23 ms 5252 KB Output is correct - 39460 call(s) of encode_bit()
10 Correct 19 ms 5252 KB Output is correct - 38140 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 64900 call(s) of encode_bit()
12 Correct 14 ms 5116 KB Output is correct - 29960 call(s) of encode_bit()
13 Correct 50 ms 7132 KB Output is partially correct - 132730 call(s) of encode_bit()
14 Correct 23 ms 5192 KB Output is correct - 41430 call(s) of encode_bit()
15 Correct 20 ms 5380 KB Output is correct - 42580 call(s) of encode_bit()
16 Correct 46 ms 6252 KB Output is correct - 68120 call(s) of encode_bit()
17 Correct 40 ms 6296 KB Output is correct - 64320 call(s) of encode_bit()
18 Correct 46 ms 6944 KB Output is partially correct - 93150 call(s) of encode_bit()
19 Correct 44 ms 6360 KB Output is partially correct - 100980 call(s) of encode_bit()
20 Correct 64 ms 7552 KB Output is partially correct - 114600 call(s) of encode_bit()
21 Correct 73 ms 7868 KB Output is partially correct - 120200 call(s) of encode_bit()
22 Correct 63 ms 7636 KB Output is partially correct - 183490 call(s) of encode_bit()
23 Correct 100 ms 8552 KB Output is partially correct - 163940 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 14152 KB Output is partially correct - 178030 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 26 ms 5424 KB Output is correct - 48690 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 160 call(s) of encode_bit()
5 Correct 39 ms 6144 KB Output is partially correct - 107970 call(s) of encode_bit()
6 Correct 35 ms 6048 KB Output is partially correct - 111990 call(s) of encode_bit()
7 Correct 62 ms 7448 KB Output is partially correct - 197690 call(s) of encode_bit()
8 Correct 19 ms 5212 KB Output is correct - 36670 call(s) of encode_bit()
9 Correct 23 ms 5252 KB Output is correct - 39460 call(s) of encode_bit()
10 Correct 19 ms 5252 KB Output is correct - 38140 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 64900 call(s) of encode_bit()
12 Correct 14 ms 5116 KB Output is correct - 29960 call(s) of encode_bit()
13 Correct 50 ms 7132 KB Output is partially correct - 132730 call(s) of encode_bit()
14 Correct 23 ms 5192 KB Output is correct - 41430 call(s) of encode_bit()
15 Correct 20 ms 5380 KB Output is correct - 42580 call(s) of encode_bit()
16 Correct 46 ms 6252 KB Output is correct - 68120 call(s) of encode_bit()
17 Correct 40 ms 6296 KB Output is correct - 64320 call(s) of encode_bit()
18 Correct 46 ms 6944 KB Output is partially correct - 93150 call(s) of encode_bit()
19 Correct 44 ms 6360 KB Output is partially correct - 100980 call(s) of encode_bit()
20 Correct 64 ms 7552 KB Output is partially correct - 114600 call(s) of encode_bit()
21 Correct 73 ms 7868 KB Output is partially correct - 120200 call(s) of encode_bit()
22 Correct 63 ms 7636 KB Output is partially correct - 183490 call(s) of encode_bit()
23 Correct 100 ms 8552 KB Output is partially correct - 163940 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 14152 KB Output is partially correct - 178030 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 26 ms 5424 KB Output is correct - 48690 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 160 call(s) of encode_bit()
5 Correct 39 ms 6144 KB Output is partially correct - 107970 call(s) of encode_bit()
6 Correct 35 ms 6048 KB Output is partially correct - 111990 call(s) of encode_bit()
7 Correct 62 ms 7448 KB Output is partially correct - 197690 call(s) of encode_bit()
8 Correct 19 ms 5212 KB Output is correct - 36670 call(s) of encode_bit()
9 Correct 23 ms 5252 KB Output is correct - 39460 call(s) of encode_bit()
10 Correct 19 ms 5252 KB Output is correct - 38140 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 64900 call(s) of encode_bit()
12 Correct 14 ms 5116 KB Output is correct - 29960 call(s) of encode_bit()
13 Correct 50 ms 7132 KB Output is partially correct - 132730 call(s) of encode_bit()
14 Correct 23 ms 5192 KB Output is correct - 41430 call(s) of encode_bit()
15 Correct 20 ms 5380 KB Output is correct - 42580 call(s) of encode_bit()
16 Correct 46 ms 6252 KB Output is correct - 68120 call(s) of encode_bit()
17 Correct 40 ms 6296 KB Output is correct - 64320 call(s) of encode_bit()
18 Correct 46 ms 6944 KB Output is partially correct - 93150 call(s) of encode_bit()
19 Correct 44 ms 6360 KB Output is partially correct - 100980 call(s) of encode_bit()
20 Correct 64 ms 7552 KB Output is partially correct - 114600 call(s) of encode_bit()
21 Correct 73 ms 7868 KB Output is partially correct - 120200 call(s) of encode_bit()
22 Correct 63 ms 7636 KB Output is partially correct - 183490 call(s) of encode_bit()
23 Correct 100 ms 8552 KB Output is partially correct - 163940 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 14152 KB Output is partially correct - 178030 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 26 ms 5424 KB Output is correct - 48690 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 160 call(s) of encode_bit()
5 Correct 39 ms 6144 KB Output is partially correct - 107970 call(s) of encode_bit()
6 Correct 35 ms 6048 KB Output is partially correct - 111990 call(s) of encode_bit()
7 Correct 62 ms 7448 KB Output is partially correct - 197690 call(s) of encode_bit()
8 Correct 19 ms 5212 KB Output is correct - 36670 call(s) of encode_bit()
9 Correct 23 ms 5252 KB Output is correct - 39460 call(s) of encode_bit()
10 Correct 19 ms 5252 KB Output is correct - 38140 call(s) of encode_bit()
11 Correct 28 ms 5736 KB Output is correct - 64900 call(s) of encode_bit()
12 Correct 14 ms 5116 KB Output is correct - 29960 call(s) of encode_bit()
13 Correct 50 ms 7132 KB Output is partially correct - 132730 call(s) of encode_bit()
14 Correct 23 ms 5192 KB Output is correct - 41430 call(s) of encode_bit()
15 Correct 20 ms 5380 KB Output is correct - 42580 call(s) of encode_bit()
16 Correct 46 ms 6252 KB Output is correct - 68120 call(s) of encode_bit()
17 Correct 40 ms 6296 KB Output is correct - 64320 call(s) of encode_bit()
18 Correct 46 ms 6944 KB Output is partially correct - 93150 call(s) of encode_bit()
19 Correct 44 ms 6360 KB Output is partially correct - 100980 call(s) of encode_bit()
20 Correct 64 ms 7552 KB Output is partially correct - 114600 call(s) of encode_bit()
21 Correct 73 ms 7868 KB Output is partially correct - 120200 call(s) of encode_bit()
22 Correct 63 ms 7636 KB Output is partially correct - 183490 call(s) of encode_bit()
23 Correct 100 ms 8552 KB Output is partially correct - 163940 call(s) of encode_bit()