oj.uz

Submission #506200

# Submission time Handle Problem Language Result Execution time Memory
506200 2022-01-11T20:41:20 Z jerzyk Saveit (IOI10_saveit) C++17
0 / 100
 267 ms 10696 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1000 + 7;
vector<int>ed[N];
int tab[38][1000 + 7], wsk[N];

ll Return3(int v, int h)
{
    ll w = 0LL, m;
    for(int i = 1; i <= h; ++i)
    {
        m = 0LL;
        if(tab[i][v] == tab[i][wsk[i]])
            m = 1;
        if(tab[i][v] > tab[i][wsk[i]])
            m = 2;
        w += m * pow(3LL, (ll)i - 1);
    }
    return w;
}

void PrintBits(ll x, int l)
{
    for(int i = 1; i <= l; ++i)
    {
        encode_bit(x % 2LL);
        x /= 2LL;
    }
}

void DFS(int v)
{
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(wsk[ed[v][i]] == 0)
        {
            wsk[ed[v][i]] = v;
            DFS(ed[v][i]);
        }
    }
}

void BFS(int n, int s)
{
    int v;
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        tab[s][i] = N * 2;
    tab[s][s] = 0;
    q.push(s);
    while(q.size() > 0)
    {
        v = q.front();
        q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(tab[s][ed[v][i]] > tab[s][v] + 1)
            {
                tab[s][ed[v][i]] = tab[s][v] + 1;
                q.push(ed[v][i]);
            }
        }
    }
}

void encode(int n, int h, int m, int* a, int* b)
{
    for(int i = 0; i < m; ++i)
    {
        ed[a[i] + 1].push_back(b[i] + 1);
        ed[b[i] + 1].push_back(a[i] + 1);
    }
    for(int i = 1; i <= h; ++i)
        BFS(n, i);
    wsk[1] = 1;
    DFS(1);
    for(int i = 2; i <= h; ++i)
        PrintBits(tab[i][1], 10);
    for(int i = 2; i <= n; ++i)
    {
        PrintBits(wsk[i], 10);       
        PrintBits(Return3(i, h), 58);
    }
}

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

using namespace std;
typedef long long ll;
const int N = 1000 + 7;
int odl[37][N], dod[37][N], wsk[N];
vector<int>ed[N];

void DFS(int v, int h)
{
    for(int i = 1; i <= h; ++i)
        odl[i][v] = dod[i][v] + odl[i][wsk[v]];
    for(int i = 0; i < (int)ed[v].size(); ++i)
        DFS(ed[v][i], h);
}

void Dod(ll l, int v, int h)
{
    for(int i = 1; i <= h; ++i)
    {
        if(l % 3LL == 0)
            dod[i][v] = -1;
        if(l % 3LL == 2)
            dod[i][v] = 1;
        l /= 3;
    }
}

ll ReadBits(int n)
{
    int b;
    ll w = 0LL;
    for(int i = 0; i < n; ++i)
    {
        b = decode_bit();
        w += pow(2LL, (ll)i) * b;
    }
    return w;
}

void decode(int n, int h)
{
    for(int i = 2; i <= h; ++i)
        odl[i][1] = ReadBits(10);
    for(int i = 2; i <= n; ++i)
    {
        wsk[i] = ReadBits(10);
        ed[wsk[i]].push_back(i);
        Dod(ReadBits(58), i, h);
    }
    DFS(1, h);
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= n; ++j)
            hops(i - 1, j - 1, odl[i][j]);
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 10696 KB wrong parameter
2 Incorrect 2 ms 4580 KB wrong parameter
3 Incorrect 19 ms 5836 KB wrong parameter
4 Incorrect 2 ms 4588 KB wrong parameter
5 Incorrect 27 ms 5876 KB wrong parameter
6 Incorrect 27 ms 6052 KB wrong parameter
7 Incorrect 50 ms 6480 KB wrong parameter
8 Incorrect 23 ms 5864 KB wrong parameter
9 Incorrect 22 ms 5864 KB wrong parameter
10 Incorrect 20 ms 5856 KB wrong parameter
11 Incorrect 23 ms 5860 KB wrong parameter
12 Incorrect 19 ms 5720 KB wrong parameter
13 Incorrect 44 ms 6388 KB wrong parameter
14 Incorrect 20 ms 5852 KB wrong parameter
15 Incorrect 27 ms 5956 KB wrong parameter
16 Incorrect 59 ms 6248 KB wrong parameter
17 Incorrect 47 ms 6228 KB wrong parameter
18 Incorrect 60 ms 6612 KB wrong parameter
19 Incorrect 31 ms 6196 KB wrong parameter
20 Incorrect 61 ms 6836 KB wrong parameter
21 Incorrect 67 ms 6984 KB wrong parameter
22 Incorrect 54 ms 6476 KB wrong parameter
23 Incorrect 88 ms 7192 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 10696 KB wrong parameter
2 Incorrect 2 ms 4580 KB wrong parameter
3 Incorrect 19 ms 5836 KB wrong parameter
4 Incorrect 2 ms 4588 KB wrong parameter
5 Incorrect 27 ms 5876 KB wrong parameter
6 Incorrect 27 ms 6052 KB wrong parameter
7 Incorrect 50 ms 6480 KB wrong parameter
8 Incorrect 23 ms 5864 KB wrong parameter
9 Incorrect 22 ms 5864 KB wrong parameter
10 Incorrect 20 ms 5856 KB wrong parameter
11 Incorrect 23 ms 5860 KB wrong parameter
12 Incorrect 19 ms 5720 KB wrong parameter
13 Incorrect 44 ms 6388 KB wrong parameter
14 Incorrect 20 ms 5852 KB wrong parameter
15 Incorrect 27 ms 5956 KB wrong parameter
16 Incorrect 59 ms 6248 KB wrong parameter
17 Incorrect 47 ms 6228 KB wrong parameter
18 Incorrect 60 ms 6612 KB wrong parameter
19 Incorrect 31 ms 6196 KB wrong parameter
20 Incorrect 61 ms 6836 KB wrong parameter
21 Incorrect 67 ms 6984 KB wrong parameter
22 Incorrect 54 ms 6476 KB wrong parameter
23 Incorrect 88 ms 7192 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 10696 KB wrong parameter
2 Incorrect 2 ms 4580 KB wrong parameter
3 Incorrect 19 ms 5836 KB wrong parameter
4 Incorrect 2 ms 4588 KB wrong parameter
5 Incorrect 27 ms 5876 KB wrong parameter
6 Incorrect 27 ms 6052 KB wrong parameter
7 Incorrect 50 ms 6480 KB wrong parameter
8 Incorrect 23 ms 5864 KB wrong parameter
9 Incorrect 22 ms 5864 KB wrong parameter
10 Incorrect 20 ms 5856 KB wrong parameter
11 Incorrect 23 ms 5860 KB wrong parameter
12 Incorrect 19 ms 5720 KB wrong parameter
13 Incorrect 44 ms 6388 KB wrong parameter
14 Incorrect 20 ms 5852 KB wrong parameter
15 Incorrect 27 ms 5956 KB wrong parameter
16 Incorrect 59 ms 6248 KB wrong parameter
17 Incorrect 47 ms 6228 KB wrong parameter
18 Incorrect 60 ms 6612 KB wrong parameter
19 Incorrect 31 ms 6196 KB wrong parameter
20 Incorrect 61 ms 6836 KB wrong parameter
21 Incorrect 67 ms 6984 KB wrong parameter
22 Incorrect 54 ms 6476 KB wrong parameter
23 Incorrect 88 ms 7192 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 10696 KB wrong parameter
2 Incorrect 2 ms 4580 KB wrong parameter
3 Incorrect 19 ms 5836 KB wrong parameter
4 Incorrect 2 ms 4588 KB wrong parameter
5 Incorrect 27 ms 5876 KB wrong parameter
6 Incorrect 27 ms 6052 KB wrong parameter
7 Incorrect 50 ms 6480 KB wrong parameter
8 Incorrect 23 ms 5864 KB wrong parameter
9 Incorrect 22 ms 5864 KB wrong parameter
10 Incorrect 20 ms 5856 KB wrong parameter
11 Incorrect 23 ms 5860 KB wrong parameter
12 Incorrect 19 ms 5720 KB wrong parameter
13 Incorrect 44 ms 6388 KB wrong parameter
14 Incorrect 20 ms 5852 KB wrong parameter
15 Incorrect 27 ms 5956 KB wrong parameter
16 Incorrect 59 ms 6248 KB wrong parameter
17 Incorrect 47 ms 6228 KB wrong parameter
18 Incorrect 60 ms 6612 KB wrong parameter
19 Incorrect 31 ms 6196 KB wrong parameter
20 Incorrect 61 ms 6836 KB wrong parameter
21 Incorrect 67 ms 6984 KB wrong parameter
22 Incorrect 54 ms 6476 KB wrong parameter
23 Incorrect 88 ms 7192 KB wrong parameter