oj.uz

Submission #266401

# Submission time Handle Problem Language Result Execution time Memory
266401 2020-08-15T08:29:37 Z Alexa2001 Saveit (IOI10_saveit) C++17
0 / 100
 240 ms 12016 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> v;
vector<int> t;
vector<bool> used;

int n;


void bfs(int node, vector<int> &dist)
{
    dist.resize(n, 1e9);
    dist[node] = 0;

    queue<int> q;
    q.push(node);

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : v[node])
            if(dist[node] + 1 < dist[it])
            {
                dist[it] = dist[node] + 1;
                q.push(it);
            }
    }
}

void dfs(int node)
{
    used[node] = 1;

    for(auto it : v[node])
        if(!used[it])
        {
            t[it] = node;
            dfs(it);
        }
}

void print(int x)
{
    if(x == 0) encode_bit(0);
        else if(x == 1) encode_bit(1), encode_bit(0);
            else if(x == 2) encode_bit(1), encode_bit(1);
                else assert(0);
}

void encode(int N, int H, int P, int *v1, int *v2)
{
    vector<vector<int>> dist(H);

    n = N;
    v.resize(n);

    int i, j;
    for(i=0; i<P; ++i)
    {
        v[v1[i]].push_back(v2[i]);
        v[v2[i]].push_back(v1[i]);
    }

    for(i=0; i<H; ++i)
        bfs(i, dist[i]);

    used.resize(n, 0);
    t.resize(n);
    dfs(0);

    for(i=1; i<n; ++i)
    {
        int b = 10;
        while(b--)
            encode_bit((t[i] >> b) & 1);
    }

    for(i=0; i<H; ++i)
        for(j=9; j>=0; --j)
            encode_bit((dist[i][0]>>j) & 1);

    vector<vector<int>> tip(n);
    for(auto &it : tip) it.resize(H);
    map<int, int> cnt;

    for(i=1; i<n; ++i)
        for(j=0; j<H; ++j)
        {
            tip[i][j] = dist[j][i] - dist[j][t[i]];
            ++cnt[tip[i][j]];
        }

    if(cnt[-1] >= cnt[0] && cnt[-1] >= cnt[1]) cnt[-1] = 0, cnt[0] = 1, cnt[1] = 2;
        else if(cnt[0] >= cnt[-1] && cnt[0] >= cnt[1]) cnt[0] = 0, cnt[-1] = 1, cnt[1] = 2;
            else cnt[1] = 0, cnt[0] = 1, cnt[-1] = 2;

    print(cnt[-1]);
    print(cnt[0]);
    print(cnt[1]);

    for(i=1; i<n; ++i)
        for(j=0; j<H; ++j)
            print(cnt[tip[i][j]]);
}

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

using namespace std;

void read(int &x)
{
    if(decode_bit() == 0) x = 0;
        else if(decode_bit() == 0) x = 1;
            else x = 2;
}

void decode(int n, int h)
{
    int i, j;
    vector<bool> marked(n, 0);
    vector<int> t(n);

    for(i=1; i<n; ++i)
    {
        int b = 10;
        int x = 0;
        while(b--)
            x = x * 2 + decode_bit();
        t[i] = x;
    }

    vector<vector<int>> dist(h);
    for(auto &it : dist) it.resize(n);

    for(i=0; i<h; ++i)
    {
        int x = 0;
        for(j=0; j<10; ++j)
            x = x * 2 + decode_bit();
        dist[i][0] = x;
    }

    map<int, int> cnt;

    read(cnt[-1]);
    read(cnt[0]);
    read(cnt[1]);

    for(i=1; i<n; ++i)
        for(j=0; j<h; ++j)
        {
            int x;
            read(x);

            for(int k=-1; k<=1; ++k)
                if(cnt[k] == x)
                    dist[j][i] = dist[j][t[i]] + k;
        }

    for(i=0; i<n; ++i)
        for(j=0; j<h; ++j)
            hops(j, i, dist[j][i]);
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 12016 KB wrong parameter
2 Correct 4 ms 4768 KB Output is correct - 93 call(s) of encode_bit()
3 Incorrect 27 ms 5968 KB wrong parameter
4 Correct 4 ms 4992 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 32 ms 6084 KB wrong parameter
6 Incorrect 35 ms 6220 KB wrong parameter
7 Incorrect 52 ms 6264 KB wrong parameter
8 Incorrect 22 ms 5968 KB wrong parameter
9 Incorrect 23 ms 5968 KB wrong parameter
10 Incorrect 22 ms 5760 KB wrong parameter
11 Incorrect 32 ms 6056 KB wrong parameter
12 Incorrect 26 ms 5992 KB wrong parameter
13 Incorrect 52 ms 6552 KB wrong parameter
14 Incorrect 26 ms 5888 KB wrong parameter
15 Incorrect 26 ms 6104 KB wrong parameter
16 Incorrect 61 ms 6592 KB wrong parameter
17 Incorrect 54 ms 6392 KB wrong parameter
18 Incorrect 103 ms 6648 KB wrong parameter
19 Incorrect 63 ms 6216 KB wrong parameter
20 Incorrect 63 ms 6904 KB wrong parameter
21 Incorrect 131 ms 7192 KB wrong parameter
22 Incorrect 51 ms 6392 KB wrong parameter
23 Incorrect 86 ms 7296 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 12016 KB wrong parameter
2 Correct 4 ms 4768 KB Output is correct - 93 call(s) of encode_bit()
3 Incorrect 27 ms 5968 KB wrong parameter
4 Correct 4 ms 4992 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 32 ms 6084 KB wrong parameter
6 Incorrect 35 ms 6220 KB wrong parameter
7 Incorrect 52 ms 6264 KB wrong parameter
8 Incorrect 22 ms 5968 KB wrong parameter
9 Incorrect 23 ms 5968 KB wrong parameter
10 Incorrect 22 ms 5760 KB wrong parameter
11 Incorrect 32 ms 6056 KB wrong parameter
12 Incorrect 26 ms 5992 KB wrong parameter
13 Incorrect 52 ms 6552 KB wrong parameter
14 Incorrect 26 ms 5888 KB wrong parameter
15 Incorrect 26 ms 6104 KB wrong parameter
16 Incorrect 61 ms 6592 KB wrong parameter
17 Incorrect 54 ms 6392 KB wrong parameter
18 Incorrect 103 ms 6648 KB wrong parameter
19 Incorrect 63 ms 6216 KB wrong parameter
20 Incorrect 63 ms 6904 KB wrong parameter
21 Incorrect 131 ms 7192 KB wrong parameter
22 Incorrect 51 ms 6392 KB wrong parameter
23 Incorrect 86 ms 7296 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 12016 KB wrong parameter
2 Correct 4 ms 4768 KB Output is correct - 93 call(s) of encode_bit()
3 Incorrect 27 ms 5968 KB wrong parameter
4 Correct 4 ms 4992 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 32 ms 6084 KB wrong parameter
6 Incorrect 35 ms 6220 KB wrong parameter
7 Incorrect 52 ms 6264 KB wrong parameter
8 Incorrect 22 ms 5968 KB wrong parameter
9 Incorrect 23 ms 5968 KB wrong parameter
10 Incorrect 22 ms 5760 KB wrong parameter
11 Incorrect 32 ms 6056 KB wrong parameter
12 Incorrect 26 ms 5992 KB wrong parameter
13 Incorrect 52 ms 6552 KB wrong parameter
14 Incorrect 26 ms 5888 KB wrong parameter
15 Incorrect 26 ms 6104 KB wrong parameter
16 Incorrect 61 ms 6592 KB wrong parameter
17 Incorrect 54 ms 6392 KB wrong parameter
18 Incorrect 103 ms 6648 KB wrong parameter
19 Incorrect 63 ms 6216 KB wrong parameter
20 Incorrect 63 ms 6904 KB wrong parameter
21 Incorrect 131 ms 7192 KB wrong parameter
22 Incorrect 51 ms 6392 KB wrong parameter
23 Incorrect 86 ms 7296 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 240 ms 12016 KB wrong parameter
2 Correct 4 ms 4768 KB Output is correct - 93 call(s) of encode_bit()
3 Incorrect 27 ms 5968 KB wrong parameter
4 Correct 4 ms 4992 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 32 ms 6084 KB wrong parameter
6 Incorrect 35 ms 6220 KB wrong parameter
7 Incorrect 52 ms 6264 KB wrong parameter
8 Incorrect 22 ms 5968 KB wrong parameter
9 Incorrect 23 ms 5968 KB wrong parameter
10 Incorrect 22 ms 5760 KB wrong parameter
11 Incorrect 32 ms 6056 KB wrong parameter
12 Incorrect 26 ms 5992 KB wrong parameter
13 Incorrect 52 ms 6552 KB wrong parameter
14 Incorrect 26 ms 5888 KB wrong parameter
15 Incorrect 26 ms 6104 KB wrong parameter
16 Incorrect 61 ms 6592 KB wrong parameter
17 Incorrect 54 ms 6392 KB wrong parameter
18 Incorrect 103 ms 6648 KB wrong parameter
19 Incorrect 63 ms 6216 KB wrong parameter
20 Incorrect 63 ms 6904 KB wrong parameter
21 Incorrect 131 ms 7192 KB wrong parameter
22 Incorrect 51 ms 6392 KB wrong parameter
23 Incorrect 86 ms 7296 KB wrong parameter