oj.uz

Submission #506161

# Submission time Handle Problem Language Result Execution time Memory
506161 2022-01-11T18:31:10 Z jerzyk Saveit (IOI10_saveit) C++17
0 / 100
 306 ms 11148 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 = 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 306 ms 11148 KB wrong parameter
2 Incorrect 2 ms 4844 KB Output isn't correct
3 Incorrect 24 ms 6168 KB wrong parameter
4 Incorrect 2 ms 4836 KB Output isn't correct
5 Incorrect 27 ms 6308 KB wrong parameter
6 Incorrect 27 ms 6436 KB wrong parameter
7 Incorrect 50 ms 6856 KB wrong parameter
8 Incorrect 19 ms 6364 KB wrong parameter
9 Incorrect 20 ms 6372 KB wrong parameter
10 Incorrect 25 ms 6184 KB wrong parameter
11 Incorrect 28 ms 6460 KB wrong parameter
12 Incorrect 25 ms 6276 KB wrong parameter
13 Incorrect 59 ms 6984 KB wrong parameter
14 Incorrect 20 ms 6356 KB wrong parameter
15 Incorrect 22 ms 6388 KB wrong parameter
16 Incorrect 57 ms 6784 KB Output isn't correct
17 Incorrect 37 ms 6940 KB wrong parameter
18 Incorrect 54 ms 7112 KB wrong parameter
19 Incorrect 43 ms 6668 KB wrong parameter
20 Incorrect 60 ms 7312 KB wrong parameter
21 Incorrect 90 ms 7436 KB wrong parameter
22 Incorrect 58 ms 6992 KB wrong parameter
23 Incorrect 94 ms 7692 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 11148 KB wrong parameter
2 Incorrect 2 ms 4844 KB Output isn't correct
3 Incorrect 24 ms 6168 KB wrong parameter
4 Incorrect 2 ms 4836 KB Output isn't correct
5 Incorrect 27 ms 6308 KB wrong parameter
6 Incorrect 27 ms 6436 KB wrong parameter
7 Incorrect 50 ms 6856 KB wrong parameter
8 Incorrect 19 ms 6364 KB wrong parameter
9 Incorrect 20 ms 6372 KB wrong parameter
10 Incorrect 25 ms 6184 KB wrong parameter
11 Incorrect 28 ms 6460 KB wrong parameter
12 Incorrect 25 ms 6276 KB wrong parameter
13 Incorrect 59 ms 6984 KB wrong parameter
14 Incorrect 20 ms 6356 KB wrong parameter
15 Incorrect 22 ms 6388 KB wrong parameter
16 Incorrect 57 ms 6784 KB Output isn't correct
17 Incorrect 37 ms 6940 KB wrong parameter
18 Incorrect 54 ms 7112 KB wrong parameter
19 Incorrect 43 ms 6668 KB wrong parameter
20 Incorrect 60 ms 7312 KB wrong parameter
21 Incorrect 90 ms 7436 KB wrong parameter
22 Incorrect 58 ms 6992 KB wrong parameter
23 Incorrect 94 ms 7692 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 11148 KB wrong parameter
2 Incorrect 2 ms 4844 KB Output isn't correct
3 Incorrect 24 ms 6168 KB wrong parameter
4 Incorrect 2 ms 4836 KB Output isn't correct
5 Incorrect 27 ms 6308 KB wrong parameter
6 Incorrect 27 ms 6436 KB wrong parameter
7 Incorrect 50 ms 6856 KB wrong parameter
8 Incorrect 19 ms 6364 KB wrong parameter
9 Incorrect 20 ms 6372 KB wrong parameter
10 Incorrect 25 ms 6184 KB wrong parameter
11 Incorrect 28 ms 6460 KB wrong parameter
12 Incorrect 25 ms 6276 KB wrong parameter
13 Incorrect 59 ms 6984 KB wrong parameter
14 Incorrect 20 ms 6356 KB wrong parameter
15 Incorrect 22 ms 6388 KB wrong parameter
16 Incorrect 57 ms 6784 KB Output isn't correct
17 Incorrect 37 ms 6940 KB wrong parameter
18 Incorrect 54 ms 7112 KB wrong parameter
19 Incorrect 43 ms 6668 KB wrong parameter
20 Incorrect 60 ms 7312 KB wrong parameter
21 Incorrect 90 ms 7436 KB wrong parameter
22 Incorrect 58 ms 6992 KB wrong parameter
23 Incorrect 94 ms 7692 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 11148 KB wrong parameter
2 Incorrect 2 ms 4844 KB Output isn't correct
3 Incorrect 24 ms 6168 KB wrong parameter
4 Incorrect 2 ms 4836 KB Output isn't correct
5 Incorrect 27 ms 6308 KB wrong parameter
6 Incorrect 27 ms 6436 KB wrong parameter
7 Incorrect 50 ms 6856 KB wrong parameter
8 Incorrect 19 ms 6364 KB wrong parameter
9 Incorrect 20 ms 6372 KB wrong parameter
10 Incorrect 25 ms 6184 KB wrong parameter
11 Incorrect 28 ms 6460 KB wrong parameter
12 Incorrect 25 ms 6276 KB wrong parameter
13 Incorrect 59 ms 6984 KB wrong parameter
14 Incorrect 20 ms 6356 KB wrong parameter
15 Incorrect 22 ms 6388 KB wrong parameter
16 Incorrect 57 ms 6784 KB Output isn't correct
17 Incorrect 37 ms 6940 KB wrong parameter
18 Incorrect 54 ms 7112 KB wrong parameter
19 Incorrect 43 ms 6668 KB wrong parameter
20 Incorrect 60 ms 7312 KB wrong parameter
21 Incorrect 90 ms 7436 KB wrong parameter
22 Incorrect 58 ms 6992 KB wrong parameter
23 Incorrect 94 ms 7692 KB wrong parameter