oj.uz

Submission #507311

# Submission time Handle Problem Language Result Execution time Memory
507311 2022-01-12T10:46:51 Z jerzyk Saveit (IOI10_saveit) C++14
0 / 100
 296 ms 10888 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][N], 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 = 1LL;
        if(tab[i][v] > tab[i][wsk[i]])
            m = 2LL;
        w += m * pow(3LL, (ll)i - 1LL);
    }
    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)
        if(v != 1)
            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 == 0LL)
            dod[i][v] = -1;
        if(l % 3LL == 2LL)
            dod[i][v] = 1;
        l /= 3LL;
    }
}

ll ReadBits(int n)
{
    ll w = 0LL, b;
    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 296 ms 10888 KB wrong parameter
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 20 ms 5860 KB wrong parameter
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 21 ms 6060 KB wrong parameter
6 Incorrect 24 ms 5952 KB wrong parameter
7 Incorrect 41 ms 6344 KB wrong parameter
8 Incorrect 19 ms 5852 KB wrong parameter
9 Incorrect 22 ms 5796 KB wrong parameter
10 Incorrect 28 ms 5756 KB wrong parameter
11 Incorrect 27 ms 5976 KB wrong parameter
12 Incorrect 20 ms 5840 KB wrong parameter
13 Incorrect 46 ms 6428 KB wrong parameter
14 Incorrect 22 ms 5896 KB wrong parameter
15 Incorrect 25 ms 5852 KB wrong parameter
16 Incorrect 56 ms 6336 KB wrong parameter
17 Incorrect 38 ms 6176 KB wrong parameter
18 Incorrect 47 ms 6592 KB wrong parameter
19 Incorrect 36 ms 6160 KB wrong parameter
20 Incorrect 65 ms 6856 KB wrong parameter
21 Incorrect 63 ms 6988 KB wrong parameter
22 Incorrect 49 ms 6596 KB wrong parameter
23 Incorrect 90 ms 7128 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 10888 KB wrong parameter
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 20 ms 5860 KB wrong parameter
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 21 ms 6060 KB wrong parameter
6 Incorrect 24 ms 5952 KB wrong parameter
7 Incorrect 41 ms 6344 KB wrong parameter
8 Incorrect 19 ms 5852 KB wrong parameter
9 Incorrect 22 ms 5796 KB wrong parameter
10 Incorrect 28 ms 5756 KB wrong parameter
11 Incorrect 27 ms 5976 KB wrong parameter
12 Incorrect 20 ms 5840 KB wrong parameter
13 Incorrect 46 ms 6428 KB wrong parameter
14 Incorrect 22 ms 5896 KB wrong parameter
15 Incorrect 25 ms 5852 KB wrong parameter
16 Incorrect 56 ms 6336 KB wrong parameter
17 Incorrect 38 ms 6176 KB wrong parameter
18 Incorrect 47 ms 6592 KB wrong parameter
19 Incorrect 36 ms 6160 KB wrong parameter
20 Incorrect 65 ms 6856 KB wrong parameter
21 Incorrect 63 ms 6988 KB wrong parameter
22 Incorrect 49 ms 6596 KB wrong parameter
23 Incorrect 90 ms 7128 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 10888 KB wrong parameter
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 20 ms 5860 KB wrong parameter
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 21 ms 6060 KB wrong parameter
6 Incorrect 24 ms 5952 KB wrong parameter
7 Incorrect 41 ms 6344 KB wrong parameter
8 Incorrect 19 ms 5852 KB wrong parameter
9 Incorrect 22 ms 5796 KB wrong parameter
10 Incorrect 28 ms 5756 KB wrong parameter
11 Incorrect 27 ms 5976 KB wrong parameter
12 Incorrect 20 ms 5840 KB wrong parameter
13 Incorrect 46 ms 6428 KB wrong parameter
14 Incorrect 22 ms 5896 KB wrong parameter
15 Incorrect 25 ms 5852 KB wrong parameter
16 Incorrect 56 ms 6336 KB wrong parameter
17 Incorrect 38 ms 6176 KB wrong parameter
18 Incorrect 47 ms 6592 KB wrong parameter
19 Incorrect 36 ms 6160 KB wrong parameter
20 Incorrect 65 ms 6856 KB wrong parameter
21 Incorrect 63 ms 6988 KB wrong parameter
22 Incorrect 49 ms 6596 KB wrong parameter
23 Incorrect 90 ms 7128 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 10888 KB wrong parameter
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 20 ms 5860 KB wrong parameter
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 21 ms 6060 KB wrong parameter
6 Incorrect 24 ms 5952 KB wrong parameter
7 Incorrect 41 ms 6344 KB wrong parameter
8 Incorrect 19 ms 5852 KB wrong parameter
9 Incorrect 22 ms 5796 KB wrong parameter
10 Incorrect 28 ms 5756 KB wrong parameter
11 Incorrect 27 ms 5976 KB wrong parameter
12 Incorrect 20 ms 5840 KB wrong parameter
13 Incorrect 46 ms 6428 KB wrong parameter
14 Incorrect 22 ms 5896 KB wrong parameter
15 Incorrect 25 ms 5852 KB wrong parameter
16 Incorrect 56 ms 6336 KB wrong parameter
17 Incorrect 38 ms 6176 KB wrong parameter
18 Incorrect 47 ms 6592 KB wrong parameter
19 Incorrect 36 ms 6160 KB wrong parameter
20 Incorrect 65 ms 6856 KB wrong parameter
21 Incorrect 63 ms 6988 KB wrong parameter
22 Incorrect 49 ms 6596 KB wrong parameter
23 Incorrect 90 ms 7128 KB wrong parameter