oj.uz

Submission #506160

# Submission time Handle Problem Language Result Execution time Memory
506160 2022-01-11T18:26:48 Z jerzyk Saveit (IOI10_saveit) C++17
0 / 100
 302 ms 10848 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 % 2);
        x /= 2;
    }
}

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[a[i] + 1].push_back(b[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 = 10000 + 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;
    }
}

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 302 ms 10848 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 26 ms 5928 KB Output isn't correct
4 Incorrect 2 ms 4844 KB Output isn't correct
5 Incorrect 29 ms 6228 KB wrong parameter
6 Incorrect 31 ms 6148 KB Output isn't correct
7 Incorrect 56 ms 6400 KB Output isn't correct
8 Incorrect 20 ms 6252 KB wrong parameter
9 Incorrect 26 ms 6144 KB wrong parameter
10 Incorrect 19 ms 6272 KB wrong parameter
11 Incorrect 37 ms 6088 KB Output isn't correct
12 Incorrect 19 ms 6372 KB wrong parameter
13 Incorrect 46 ms 6820 KB wrong parameter
14 Incorrect 29 ms 6300 KB Output isn't correct
15 Incorrect 28 ms 6152 KB wrong parameter
16 Incorrect 51 ms 6736 KB wrong parameter
17 Incorrect 57 ms 6652 KB wrong parameter
18 Incorrect 52 ms 6928 KB wrong parameter
19 Incorrect 47 ms 6388 KB wrong parameter
20 Incorrect 90 ms 7104 KB Output isn't correct
21 Incorrect 99 ms 7260 KB Output isn't correct
22 Incorrect 43 ms 6728 KB wrong parameter
23 Incorrect 91 ms 7244 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 10848 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 26 ms 5928 KB Output isn't correct
4 Incorrect 2 ms 4844 KB Output isn't correct
5 Incorrect 29 ms 6228 KB wrong parameter
6 Incorrect 31 ms 6148 KB Output isn't correct
7 Incorrect 56 ms 6400 KB Output isn't correct
8 Incorrect 20 ms 6252 KB wrong parameter
9 Incorrect 26 ms 6144 KB wrong parameter
10 Incorrect 19 ms 6272 KB wrong parameter
11 Incorrect 37 ms 6088 KB Output isn't correct
12 Incorrect 19 ms 6372 KB wrong parameter
13 Incorrect 46 ms 6820 KB wrong parameter
14 Incorrect 29 ms 6300 KB Output isn't correct
15 Incorrect 28 ms 6152 KB wrong parameter
16 Incorrect 51 ms 6736 KB wrong parameter
17 Incorrect 57 ms 6652 KB wrong parameter
18 Incorrect 52 ms 6928 KB wrong parameter
19 Incorrect 47 ms 6388 KB wrong parameter
20 Incorrect 90 ms 7104 KB Output isn't correct
21 Incorrect 99 ms 7260 KB Output isn't correct
22 Incorrect 43 ms 6728 KB wrong parameter
23 Incorrect 91 ms 7244 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 10848 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 26 ms 5928 KB Output isn't correct
4 Incorrect 2 ms 4844 KB Output isn't correct
5 Incorrect 29 ms 6228 KB wrong parameter
6 Incorrect 31 ms 6148 KB Output isn't correct
7 Incorrect 56 ms 6400 KB Output isn't correct
8 Incorrect 20 ms 6252 KB wrong parameter
9 Incorrect 26 ms 6144 KB wrong parameter
10 Incorrect 19 ms 6272 KB wrong parameter
11 Incorrect 37 ms 6088 KB Output isn't correct
12 Incorrect 19 ms 6372 KB wrong parameter
13 Incorrect 46 ms 6820 KB wrong parameter
14 Incorrect 29 ms 6300 KB Output isn't correct
15 Incorrect 28 ms 6152 KB wrong parameter
16 Incorrect 51 ms 6736 KB wrong parameter
17 Incorrect 57 ms 6652 KB wrong parameter
18 Incorrect 52 ms 6928 KB wrong parameter
19 Incorrect 47 ms 6388 KB wrong parameter
20 Incorrect 90 ms 7104 KB Output isn't correct
21 Incorrect 99 ms 7260 KB Output isn't correct
22 Incorrect 43 ms 6728 KB wrong parameter
23 Incorrect 91 ms 7244 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 10848 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 26 ms 5928 KB Output isn't correct
4 Incorrect 2 ms 4844 KB Output isn't correct
5 Incorrect 29 ms 6228 KB wrong parameter
6 Incorrect 31 ms 6148 KB Output isn't correct
7 Incorrect 56 ms 6400 KB Output isn't correct
8 Incorrect 20 ms 6252 KB wrong parameter
9 Incorrect 26 ms 6144 KB wrong parameter
10 Incorrect 19 ms 6272 KB wrong parameter
11 Incorrect 37 ms 6088 KB Output isn't correct
12 Incorrect 19 ms 6372 KB wrong parameter
13 Incorrect 46 ms 6820 KB wrong parameter
14 Incorrect 29 ms 6300 KB Output isn't correct
15 Incorrect 28 ms 6152 KB wrong parameter
16 Incorrect 51 ms 6736 KB wrong parameter
17 Incorrect 57 ms 6652 KB wrong parameter
18 Incorrect 52 ms 6928 KB wrong parameter
19 Incorrect 47 ms 6388 KB wrong parameter
20 Incorrect 90 ms 7104 KB Output isn't correct
21 Incorrect 99 ms 7260 KB Output isn't correct
22 Incorrect 43 ms 6728 KB wrong parameter
23 Incorrect 91 ms 7244 KB wrong parameter