oj.uz

Submission #566645

# Submission time Handle Problem Language Result Execution time Memory
566645 2022-05-22T13:50:25 Z RealSnake Saveit (IOI10_saveit) C++14
0 / 100
 219 ms 12372 KB 
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "encoder.h"

void encode(int n, int h, int p, int a[], int b[]) {
    vector<int> v[n];
    for(int i = 0; i < p; i++) {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    set<int> s;
    s.insert(0);
    int par[n] = {};
    par[0] = 1;
    vector<int> v2[n];
    while(s.size()) {
        int x = *s.begin();
        s.erase(s.begin());
        for(int i : v[x]) {
            if(!par[i]) {
                v2[x].push_back(i);
                v2[i].push_back(x);
                par[i] = x + 1;
                s.insert(i);
            }
        }
    }
    for(int i = 0; i < n; i++)
        sort(v2[i].begin(), v2[i].end());
    for(int i = 1; i < n; i++) {
        int x = par[i] - 1;
        for(int j = 0; j < 10; j++)
            encode_bit(((x & (1 << j)) > 0));
    }
    int ans[n][h];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < h; j++)
            ans[i][j] = 1e9;
    }
    set<pair<int, pair<int, int>>> ss;
    for(int i = 0; i < h; i++) {
        ss.insert({0, {i, i}});
        ans[i][i] = 0;
    }
    while(ss.size()) {
        pair<int, pair<int, int>> p = *ss.begin();
        ss.erase(ss.begin());
        int x = p.second.first, hub = p.second.second;
        int cost = p.first;
        if(cost > ans[x][hub])
            continue;
        for(int i : v[x]) {
            if(cost + 1 < ans[i][hub]) {
                ans[i][hub] = cost + 1;
                ss.insert({cost + 1, {i, hub}});
            }
        }
    }
    bool vis[n];
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < n; j++)
            vis[j] = 0;
        int x = 0;
        s.insert(i);
        vis[i] = 1;
        while(s.size()) {
            x = *s.begin();
            s.erase(s.begin());
            for(int j : v2[x]) {
                if(vis[j])
                    continue;
                vis[j] = 1;
                s.insert(j);
                if(j <= i)
                    continue;
                int dif = ans[j][i] - ans[x][i];
                if(dif == 0)
                    encode_bit(0);
                else {
                    encode_bit(1);
                    if(dif == 1)
                        encode_bit(1);
                    else
                        encode_bit(0);
                }
            }
        }
    }
}
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "decoder.h"

void decode(int n, int h) {
    vector<int> v[n];
    for(int i = 1; i < n; i++) {
        int x = 0;
        for(int j = 0; j < 10; j++) {
            if(decode_bit())
                x += (1 << j);
        }
        v[x].push_back(i);
        v[i].push_back(x);
    }
    for(int i = 0; i < n; i++)
        sort(v[i].begin(), v[i].end());
    int ans[n][h];
    bool vis[n];
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < n; j++)
            vis[j] = 0;
        ans[i][i] = 0;
        set<int> s;
        s.insert(i);
        vis[i] = 1;
        while(s.size()) {
            int x = *s.begin();
            s.erase(s.begin());
            if(x >= i) {
                hops(i, x, ans[x][i]);
                if(x < h && x != i)
                    hops(x, i, ans[x][i]);
            }
            for(int j : v[x]) {
                if(vis[j])
                    continue;
                vis[j] = 1;
                s.insert(j);
                if(j <= i)
                    continue;
                int dif = decode_bit();
                if(dif) {
                    if(!decode_bit())
                        dif = -1;
                }
                ans[j][i] = ans[i][j] = ans[x][i] + dif;
            }
        }
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 12372 KB Output isn't correct
2 Correct 2 ms 4604 KB Output is correct - 55 call(s) of encode_bit()
3 Incorrect 37 ms 6772 KB Output isn't correct
4 Correct 2 ms 4616 KB Output is correct - 55 call(s) of encode_bit()
5 Incorrect 38 ms 7252 KB Output isn't correct
6 Incorrect 43 ms 7688 KB Output isn't correct
7 Incorrect 55 ms 8088 KB Output isn't correct
8 Incorrect 37 ms 5988 KB Output isn't correct
9 Incorrect 34 ms 5868 KB Output isn't correct
10 Incorrect 32 ms 5940 KB Output isn't correct
11 Incorrect 39 ms 6060 KB Output isn't correct
12 Correct 33 ms 5780 KB Output is partially correct - 80658 call(s) of encode_bit()
13 Incorrect 55 ms 7644 KB Output isn't correct
14 Incorrect 35 ms 5960 KB Output isn't correct
15 Incorrect 36 ms 5956 KB Output isn't correct
16 Incorrect 53 ms 6448 KB Output isn't correct
17 Incorrect 57 ms 6560 KB Output isn't correct
18 Incorrect 61 ms 6856 KB Output isn't correct
19 Incorrect 48 ms 6620 KB Output isn't correct
20 Incorrect 62 ms 7720 KB wrong parameter
21 Incorrect 84 ms 7564 KB Output isn't correct
22 Incorrect 61 ms 8032 KB Output isn't correct
23 Incorrect 71 ms 8796 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 12372 KB Output isn't correct
2 Correct 2 ms 4604 KB Output is correct - 55 call(s) of encode_bit()
3 Incorrect 37 ms 6772 KB Output isn't correct
4 Correct 2 ms 4616 KB Output is correct - 55 call(s) of encode_bit()
5 Incorrect 38 ms 7252 KB Output isn't correct
6 Incorrect 43 ms 7688 KB Output isn't correct
7 Incorrect 55 ms 8088 KB Output isn't correct
8 Incorrect 37 ms 5988 KB Output isn't correct
9 Incorrect 34 ms 5868 KB Output isn't correct
10 Incorrect 32 ms 5940 KB Output isn't correct
11 Incorrect 39 ms 6060 KB Output isn't correct
12 Correct 33 ms 5780 KB Output is partially correct - 80658 call(s) of encode_bit()
13 Incorrect 55 ms 7644 KB Output isn't correct
14 Incorrect 35 ms 5960 KB Output isn't correct
15 Incorrect 36 ms 5956 KB Output isn't correct
16 Incorrect 53 ms 6448 KB Output isn't correct
17 Incorrect 57 ms 6560 KB Output isn't correct
18 Incorrect 61 ms 6856 KB Output isn't correct
19 Incorrect 48 ms 6620 KB Output isn't correct
20 Incorrect 62 ms 7720 KB wrong parameter
21 Incorrect 84 ms 7564 KB Output isn't correct
22 Incorrect 61 ms 8032 KB Output isn't correct
23 Incorrect 71 ms 8796 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 12372 KB Output isn't correct
2 Correct 2 ms 4604 KB Output is correct - 55 call(s) of encode_bit()
3 Incorrect 37 ms 6772 KB Output isn't correct
4 Correct 2 ms 4616 KB Output is correct - 55 call(s) of encode_bit()
5 Incorrect 38 ms 7252 KB Output isn't correct
6 Incorrect 43 ms 7688 KB Output isn't correct
7 Incorrect 55 ms 8088 KB Output isn't correct
8 Incorrect 37 ms 5988 KB Output isn't correct
9 Incorrect 34 ms 5868 KB Output isn't correct
10 Incorrect 32 ms 5940 KB Output isn't correct
11 Incorrect 39 ms 6060 KB Output isn't correct
12 Correct 33 ms 5780 KB Output is partially correct - 80658 call(s) of encode_bit()
13 Incorrect 55 ms 7644 KB Output isn't correct
14 Incorrect 35 ms 5960 KB Output isn't correct
15 Incorrect 36 ms 5956 KB Output isn't correct
16 Incorrect 53 ms 6448 KB Output isn't correct
17 Incorrect 57 ms 6560 KB Output isn't correct
18 Incorrect 61 ms 6856 KB Output isn't correct
19 Incorrect 48 ms 6620 KB Output isn't correct
20 Incorrect 62 ms 7720 KB wrong parameter
21 Incorrect 84 ms 7564 KB Output isn't correct
22 Incorrect 61 ms 8032 KB Output isn't correct
23 Incorrect 71 ms 8796 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 12372 KB Output isn't correct
2 Correct 2 ms 4604 KB Output is correct - 55 call(s) of encode_bit()
3 Incorrect 37 ms 6772 KB Output isn't correct
4 Correct 2 ms 4616 KB Output is correct - 55 call(s) of encode_bit()
5 Incorrect 38 ms 7252 KB Output isn't correct
6 Incorrect 43 ms 7688 KB Output isn't correct
7 Incorrect 55 ms 8088 KB Output isn't correct
8 Incorrect 37 ms 5988 KB Output isn't correct
9 Incorrect 34 ms 5868 KB Output isn't correct
10 Incorrect 32 ms 5940 KB Output isn't correct
11 Incorrect 39 ms 6060 KB Output isn't correct
12 Correct 33 ms 5780 KB Output is partially correct - 80658 call(s) of encode_bit()
13 Incorrect 55 ms 7644 KB Output isn't correct
14 Incorrect 35 ms 5960 KB Output isn't correct
15 Incorrect 36 ms 5956 KB Output isn't correct
16 Incorrect 53 ms 6448 KB Output isn't correct
17 Incorrect 57 ms 6560 KB Output isn't correct
18 Incorrect 61 ms 6856 KB Output isn't correct
19 Incorrect 48 ms 6620 KB Output isn't correct
20 Incorrect 62 ms 7720 KB wrong parameter
21 Incorrect 84 ms 7564 KB Output isn't correct
22 Incorrect 61 ms 8032 KB Output isn't correct
23 Incorrect 71 ms 8796 KB wrong parameter