oj.uz

Submission #597198

# Submission time Handle Problem Language Result Execution time Memory
597198 2022-07-15T17:18:27 Z Bench0310 Saveit (IOI10_saveit) C++17
100 / 100
 222 ms 10356 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;
typedef long long ll;

void encode(int n,int h,int m,int *A,int *B)
{
    vector<int> v[n];
    for(int i=0;i<m;i++)
    {
        int a=A[i],b=B[i];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<int> g[n];
    vector<int> p(n,-1);
    function<void(int)> dfs=[&](int a)
    {
        for(int to:v[a])
        {
            if(p[to]!=-1) continue;
            g[a].push_back(to);
            g[to].push_back(a);
            p[to]=a;
            dfs(to);
        }
    };
    p[0]=-2;
    dfs(0);
    for(int i=1;i<n;i++) for(int j=9;j>=0;j--) encode_bit((p[i]>>j)&1);
    for(int i=0;i<h;i++)
    {
        queue<int> q;
        vector<int> d(n,-1);
        auto add=[&](int a,int nd)
        {
            if(d[a]==-1)
            {
                d[a]=nd;
                q.push(a);
            }
        };
        add(i,0);
        while(!q.empty())
        {
            int a=q.front();
            q.pop();
            for(int to:v[a]) add(to,d[a]+1);
        }
        vector<int> x(n+2,0);
        function<void(int,int)> go=[&](int a,int u)
        {
            if(u!=-1) x[a]=(d[a]-d[u]+1);
            for(int to:g[a]) if(to!=u) go(to,a);
        };
        go(i,-1);
        vector<int> y;
        for(int j=0;j<n;j++) if(j!=i) y.push_back(x[j]);
        for(int j=0;j<n-1;j+=3)
        {
            int t=(9*y[j]+3*y[j+1]+y[j+2]);
            for(int k=4;k>=0;k--) encode_bit((t>>k)&1);
        }
    }
}

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

using namespace std;
typedef long long ll;

void decode(int n,int h)
{
    vector<int> v[n];
    auto dec=[&](int c)->int
    {
        int t=0;
        for(int i=0;i<c;i++) t=2*t+decode_bit();
        return t;
    };
    for(int i=1;i<n;i++)
    {
        int p=dec(10);
        v[i].push_back(p);
        v[p].push_back(i);
    }
    for(int i=0;i<h;i++)
    {
        vector<int> x(n+2,0);
        int pos=-1;
        for(int j=0;j<n-1;j+=3)
        {
            int t=dec(5);
            array<int,3> tmp={0,0,0};
            for(int k=2;k>=0;k--)
            {
                tmp[k]=(t%3)-1;
                t/=3;
            }
            for(int k=0;k<=2;k++)
            {
                pos++;
                if(pos==i) pos++;
                x[pos]=tmp[k];
            }
        }
        vector<int> d(n,0);
        function<void(int,int)> go=[&](int a,int p)
        {
            if(p!=-1) d[a]=d[p]+x[a];
            hops(i,a,d[a]);
            for(int to:v[a]) if(to!=p) go(to,a);
        };
        go(i,-1);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 10356 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 28 ms 5492 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 24 ms 5676 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 28 ms 5756 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 46 ms 6224 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5492 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 29 ms 5468 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 5664 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5628 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 49 ms 6212 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 25 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 56 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 36 ms 6076 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 62 ms 6176 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 36 ms 5792 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 61 ms 6456 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 89 ms 6568 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 47 ms 6172 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 10356 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 28 ms 5492 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 24 ms 5676 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 28 ms 5756 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 46 ms 6224 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5492 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 29 ms 5468 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 5664 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5628 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 49 ms 6212 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 25 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 56 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 36 ms 6076 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 62 ms 6176 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 36 ms 5792 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 61 ms 6456 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 89 ms 6568 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 47 ms 6172 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 10356 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 28 ms 5492 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 24 ms 5676 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 28 ms 5756 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 46 ms 6224 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5492 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 29 ms 5468 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 5664 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5628 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 49 ms 6212 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 25 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 56 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 36 ms 6076 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 62 ms 6176 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 36 ms 5792 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 61 ms 6456 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 89 ms 6568 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 47 ms 6172 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 10356 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 28 ms 5492 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 24 ms 5676 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 28 ms 5756 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 46 ms 6224 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5492 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 29 ms 5468 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 5504 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 5664 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5628 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 49 ms 6212 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 5712 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 25 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 56 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 36 ms 6076 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 62 ms 6176 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 36 ms 5792 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 61 ms 6456 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 89 ms 6568 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 47 ms 6172 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()