oj.uz

Submission #513653

# Submission time Handle Problem Language Result Execution time Memory
513653 2022-01-17T11:17:41 Z jerzyk Saveit (IOI10_saveit) C++17
0 / 100
 302 ms 10648 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, pot = 1LL;
    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 * pot;
        pot *= 3LL;
    }
    return w;
}

void PrintBits(ll x, int l)
{
    for(int i = 1; i <= l; ++i)
    {
        encode_bit((int)(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, pot = 1LL;
    for(int i = 0; i < n; ++i)
    {
        b = decode_bit();
        w += pot * b;
        pot *= 2LL;
    }
    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 302 ms 10648 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 19 ms 5860 KB Output isn't correct
4 Incorrect 2 ms 4528 KB Output isn't correct
5 Incorrect 31 ms 6024 KB Output isn't correct
6 Incorrect 30 ms 5956 KB Output isn't correct
7 Incorrect 45 ms 6648 KB Output isn't correct
8 Incorrect 17 ms 5836 KB wrong parameter
9 Incorrect 25 ms 5916 KB Output isn't correct
10 Incorrect 26 ms 5832 KB Output isn't correct
11 Incorrect 27 ms 5908 KB Output isn't correct
12 Incorrect 17 ms 5860 KB wrong parameter
13 Incorrect 59 ms 6404 KB wrong parameter
14 Incorrect 25 ms 5908 KB Output isn't correct
15 Incorrect 24 ms 5860 KB wrong parameter
16 Incorrect 50 ms 6400 KB wrong parameter
17 Incorrect 52 ms 6272 KB wrong parameter
18 Incorrect 68 ms 6732 KB wrong parameter
19 Incorrect 40 ms 6100 KB wrong parameter
20 Incorrect 76 ms 6892 KB wrong parameter
21 Incorrect 65 ms 6964 KB wrong parameter
22 Incorrect 59 ms 6492 KB Output isn't correct
23 Incorrect 96 ms 7252 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 10648 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 19 ms 5860 KB Output isn't correct
4 Incorrect 2 ms 4528 KB Output isn't correct
5 Incorrect 31 ms 6024 KB Output isn't correct
6 Incorrect 30 ms 5956 KB Output isn't correct
7 Incorrect 45 ms 6648 KB Output isn't correct
8 Incorrect 17 ms 5836 KB wrong parameter
9 Incorrect 25 ms 5916 KB Output isn't correct
10 Incorrect 26 ms 5832 KB Output isn't correct
11 Incorrect 27 ms 5908 KB Output isn't correct
12 Incorrect 17 ms 5860 KB wrong parameter
13 Incorrect 59 ms 6404 KB wrong parameter
14 Incorrect 25 ms 5908 KB Output isn't correct
15 Incorrect 24 ms 5860 KB wrong parameter
16 Incorrect 50 ms 6400 KB wrong parameter
17 Incorrect 52 ms 6272 KB wrong parameter
18 Incorrect 68 ms 6732 KB wrong parameter
19 Incorrect 40 ms 6100 KB wrong parameter
20 Incorrect 76 ms 6892 KB wrong parameter
21 Incorrect 65 ms 6964 KB wrong parameter
22 Incorrect 59 ms 6492 KB Output isn't correct
23 Incorrect 96 ms 7252 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 10648 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 19 ms 5860 KB Output isn't correct
4 Incorrect 2 ms 4528 KB Output isn't correct
5 Incorrect 31 ms 6024 KB Output isn't correct
6 Incorrect 30 ms 5956 KB Output isn't correct
7 Incorrect 45 ms 6648 KB Output isn't correct
8 Incorrect 17 ms 5836 KB wrong parameter
9 Incorrect 25 ms 5916 KB Output isn't correct
10 Incorrect 26 ms 5832 KB Output isn't correct
11 Incorrect 27 ms 5908 KB Output isn't correct
12 Incorrect 17 ms 5860 KB wrong parameter
13 Incorrect 59 ms 6404 KB wrong parameter
14 Incorrect 25 ms 5908 KB Output isn't correct
15 Incorrect 24 ms 5860 KB wrong parameter
16 Incorrect 50 ms 6400 KB wrong parameter
17 Incorrect 52 ms 6272 KB wrong parameter
18 Incorrect 68 ms 6732 KB wrong parameter
19 Incorrect 40 ms 6100 KB wrong parameter
20 Incorrect 76 ms 6892 KB wrong parameter
21 Incorrect 65 ms 6964 KB wrong parameter
22 Incorrect 59 ms 6492 KB Output isn't correct
23 Incorrect 96 ms 7252 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 10648 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 19 ms 5860 KB Output isn't correct
4 Incorrect 2 ms 4528 KB Output isn't correct
5 Incorrect 31 ms 6024 KB Output isn't correct
6 Incorrect 30 ms 5956 KB Output isn't correct
7 Incorrect 45 ms 6648 KB Output isn't correct
8 Incorrect 17 ms 5836 KB wrong parameter
9 Incorrect 25 ms 5916 KB Output isn't correct
10 Incorrect 26 ms 5832 KB Output isn't correct
11 Incorrect 27 ms 5908 KB Output isn't correct
12 Incorrect 17 ms 5860 KB wrong parameter
13 Incorrect 59 ms 6404 KB wrong parameter
14 Incorrect 25 ms 5908 KB Output isn't correct
15 Incorrect 24 ms 5860 KB wrong parameter
16 Incorrect 50 ms 6400 KB wrong parameter
17 Incorrect 52 ms 6272 KB wrong parameter
18 Incorrect 68 ms 6732 KB wrong parameter
19 Incorrect 40 ms 6100 KB wrong parameter
20 Incorrect 76 ms 6892 KB wrong parameter
21 Incorrect 65 ms 6964 KB wrong parameter
22 Incorrect 59 ms 6492 KB Output isn't correct
23 Incorrect 96 ms 7252 KB wrong parameter