oj.uz

Submission #894860

# Submission time Handle Problem Language Result Execution time Memory
894860 2023-12-29T06:27:09 Z 12345678 Saveit (IOI10_saveit) C++17
100 / 100
 135 ms 16444 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;
int n, hub, m, pa[nx], vs[nx], dp[nx], res[nx];
vector<int> d[nx], tree[nx];

void send_number(int x)
{
    for (int i=0; i<10; i++) encode_bit((x&(1<<i)?1:0));
}

void send_value(int x)
{
    for (int i=0; i<8; i++) encode_bit((x&(1<<i)?1:0));
}

void build()
{
    queue<int> q;
    q.push(0);
    vs[0]=1;
    while (!q.empty())
    {
        auto u=q.front();
        q.pop();
        for (auto v:d[u]) if (!vs[v]) pa[v]=u, q.push(v), vs[v]=1;
    }
    for (int i=1; i<n; i++) send_number(pa[i]);
    for (int i=1; i<n; i++) tree[pa[i]].push_back(i);
}

void dfsdp(int u)
{
    for (auto v:tree[u]) res[v]=dp[v]-dp[u], dfsdp(v);
}

void bfs(int x)
{
    for (int i=0; i<n; i++) dp[i]=-1;
    queue<int> q;
    q.push(x);
    dp[x]=0;
    while (!q.empty())
    {
        auto u=q.front();
        q.pop();
        for (auto v:d[u]) if (dp[v]==-1) dp[v]=dp[u]+1, q.push(v);
    }
    dfsdp(0);
    for (int i=1; i<=1000; i+=5) 
    {
        int tmp=0;
        for (int j=i+4; j>=i; j--) tmp=3*tmp+res[j]+1;
        //printf("%d %d %d\n", x, i, tmp);
        send_value(tmp);
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n=nv;
    hub=nh;
    m=ne;
    for (int i=0; i<m; i++) d[v1[i]].push_back(v2[i]), d[v2[i]].push_back(v1[i]);
    build();
    for (int i=1; i<hub; i++) bfs(i);
}

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

using namespace std;

int N, H, vl[1005], ans[1005], mn;
vector<int> t[1005];

void dfsans(int u)
{
    for (auto v:t[u]) ans[v]=ans[u]+vl[v], dfsans(v);
    mn=min(mn, ans[u]);
}

void solve(int x)
{
    mn=INT_MAX;
    if (x==0) for (int i=1; i<N; i++) vl[i]=1;
    else
    {
        for (int i=1; i<=1000; i+=5)
        {
            int res=0;
            for (int k=0; k<8; k++) if (decode_bit()) res|=(1<<k);
            for (int j=i; j<i+5; j++) vl[j]=res%3-1, res/=3;
            //printf("read %d %d %d\n", x, i, vl[i]);
        }
    }
    ans[0]=0;
    dfsans(0);
    for (int i=0; i<N; i++) ans[i]=ans[i]-mn;
    //printf("min %d\n", mn);
    for (int i=0; i<N; i++) hops(x, i, ans[i]);
}

void decode(int nv, int nh) {
    N=nv;
    H=nh;
    for (int i=1; i<N; i++)
    {
        int res=0;
        for (int k=0; k<10; k++) if (decode_bit()) res|=(1<<k);
        t[res].push_back(i);
    }
    for (int i=0; i<H; i++) solve(i);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16444 KB Output is correct - 65990 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 3240 call(s) of encode_bit()
3 Correct 16 ms 11308 KB Output is correct - 64990 call(s) of encode_bit()
4 Correct 2 ms 11320 KB Output is correct - 6440 call(s) of encode_bit()
5 Correct 19 ms 11520 KB Output is correct - 64990 call(s) of encode_bit()
6 Correct 18 ms 12020 KB Output is correct - 65990 call(s) of encode_bit()
7 Correct 28 ms 12604 KB Output is correct - 65990 call(s) of encode_bit()
8 Correct 17 ms 11524 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 17 ms 11816 KB Output is correct - 65990 call(s) of encode_bit()
10 Correct 19 ms 11672 KB Output is correct - 65990 call(s) of encode_bit()
11 Correct 20 ms 11584 KB Output is correct - 65990 call(s) of encode_bit()
12 Correct 16 ms 11652 KB Output is correct - 65990 call(s) of encode_bit()
13 Correct 32 ms 11804 KB Output is correct - 65990 call(s) of encode_bit()
14 Correct 19 ms 11628 KB Output is correct - 65990 call(s) of encode_bit()
15 Correct 17 ms 11564 KB Output is correct - 65990 call(s) of encode_bit()
16 Correct 37 ms 12128 KB Output is correct - 65990 call(s) of encode_bit()
17 Correct 27 ms 12132 KB Output is correct - 65990 call(s) of encode_bit()
18 Correct 36 ms 12288 KB Output is correct - 65990 call(s) of encode_bit()
19 Correct 24 ms 12140 KB Output is correct - 65990 call(s) of encode_bit()
20 Correct 41 ms 14436 KB Output is correct - 65990 call(s) of encode_bit()
21 Correct 49 ms 14832 KB Output is correct - 65990 call(s) of encode_bit()
22 Correct 35 ms 12532 KB Output is correct - 65990 call(s) of encode_bit()
23 Correct 45 ms 14424 KB Output is correct - 65990 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16444 KB Output is correct - 65990 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 3240 call(s) of encode_bit()
3 Correct 16 ms 11308 KB Output is correct - 64990 call(s) of encode_bit()
4 Correct 2 ms 11320 KB Output is correct - 6440 call(s) of encode_bit()
5 Correct 19 ms 11520 KB Output is correct - 64990 call(s) of encode_bit()
6 Correct 18 ms 12020 KB Output is correct - 65990 call(s) of encode_bit()
7 Correct 28 ms 12604 KB Output is correct - 65990 call(s) of encode_bit()
8 Correct 17 ms 11524 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 17 ms 11816 KB Output is correct - 65990 call(s) of encode_bit()
10 Correct 19 ms 11672 KB Output is correct - 65990 call(s) of encode_bit()
11 Correct 20 ms 11584 KB Output is correct - 65990 call(s) of encode_bit()
12 Correct 16 ms 11652 KB Output is correct - 65990 call(s) of encode_bit()
13 Correct 32 ms 11804 KB Output is correct - 65990 call(s) of encode_bit()
14 Correct 19 ms 11628 KB Output is correct - 65990 call(s) of encode_bit()
15 Correct 17 ms 11564 KB Output is correct - 65990 call(s) of encode_bit()
16 Correct 37 ms 12128 KB Output is correct - 65990 call(s) of encode_bit()
17 Correct 27 ms 12132 KB Output is correct - 65990 call(s) of encode_bit()
18 Correct 36 ms 12288 KB Output is correct - 65990 call(s) of encode_bit()
19 Correct 24 ms 12140 KB Output is correct - 65990 call(s) of encode_bit()
20 Correct 41 ms 14436 KB Output is correct - 65990 call(s) of encode_bit()
21 Correct 49 ms 14832 KB Output is correct - 65990 call(s) of encode_bit()
22 Correct 35 ms 12532 KB Output is correct - 65990 call(s) of encode_bit()
23 Correct 45 ms 14424 KB Output is correct - 65990 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16444 KB Output is correct - 65990 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 3240 call(s) of encode_bit()
3 Correct 16 ms 11308 KB Output is correct - 64990 call(s) of encode_bit()
4 Correct 2 ms 11320 KB Output is correct - 6440 call(s) of encode_bit()
5 Correct 19 ms 11520 KB Output is correct - 64990 call(s) of encode_bit()
6 Correct 18 ms 12020 KB Output is correct - 65990 call(s) of encode_bit()
7 Correct 28 ms 12604 KB Output is correct - 65990 call(s) of encode_bit()
8 Correct 17 ms 11524 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 17 ms 11816 KB Output is correct - 65990 call(s) of encode_bit()
10 Correct 19 ms 11672 KB Output is correct - 65990 call(s) of encode_bit()
11 Correct 20 ms 11584 KB Output is correct - 65990 call(s) of encode_bit()
12 Correct 16 ms 11652 KB Output is correct - 65990 call(s) of encode_bit()
13 Correct 32 ms 11804 KB Output is correct - 65990 call(s) of encode_bit()
14 Correct 19 ms 11628 KB Output is correct - 65990 call(s) of encode_bit()
15 Correct 17 ms 11564 KB Output is correct - 65990 call(s) of encode_bit()
16 Correct 37 ms 12128 KB Output is correct - 65990 call(s) of encode_bit()
17 Correct 27 ms 12132 KB Output is correct - 65990 call(s) of encode_bit()
18 Correct 36 ms 12288 KB Output is correct - 65990 call(s) of encode_bit()
19 Correct 24 ms 12140 KB Output is correct - 65990 call(s) of encode_bit()
20 Correct 41 ms 14436 KB Output is correct - 65990 call(s) of encode_bit()
21 Correct 49 ms 14832 KB Output is correct - 65990 call(s) of encode_bit()
22 Correct 35 ms 12532 KB Output is correct - 65990 call(s) of encode_bit()
23 Correct 45 ms 14424 KB Output is correct - 65990 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16444 KB Output is correct - 65990 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 3240 call(s) of encode_bit()
3 Correct 16 ms 11308 KB Output is correct - 64990 call(s) of encode_bit()
4 Correct 2 ms 11320 KB Output is correct - 6440 call(s) of encode_bit()
5 Correct 19 ms 11520 KB Output is correct - 64990 call(s) of encode_bit()
6 Correct 18 ms 12020 KB Output is correct - 65990 call(s) of encode_bit()
7 Correct 28 ms 12604 KB Output is correct - 65990 call(s) of encode_bit()
8 Correct 17 ms 11524 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 17 ms 11816 KB Output is correct - 65990 call(s) of encode_bit()
10 Correct 19 ms 11672 KB Output is correct - 65990 call(s) of encode_bit()
11 Correct 20 ms 11584 KB Output is correct - 65990 call(s) of encode_bit()
12 Correct 16 ms 11652 KB Output is correct - 65990 call(s) of encode_bit()
13 Correct 32 ms 11804 KB Output is correct - 65990 call(s) of encode_bit()
14 Correct 19 ms 11628 KB Output is correct - 65990 call(s) of encode_bit()
15 Correct 17 ms 11564 KB Output is correct - 65990 call(s) of encode_bit()
16 Correct 37 ms 12128 KB Output is correct - 65990 call(s) of encode_bit()
17 Correct 27 ms 12132 KB Output is correct - 65990 call(s) of encode_bit()
18 Correct 36 ms 12288 KB Output is correct - 65990 call(s) of encode_bit()
19 Correct 24 ms 12140 KB Output is correct - 65990 call(s) of encode_bit()
20 Correct 41 ms 14436 KB Output is correct - 65990 call(s) of encode_bit()
21 Correct 49 ms 14832 KB Output is correct - 65990 call(s) of encode_bit()
22 Correct 35 ms 12532 KB Output is correct - 65990 call(s) of encode_bit()
23 Correct 45 ms 14424 KB Output is correct - 65990 call(s) of encode_bit()