oj.uz

답안 #894858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894858 2023-12-29T06:17:17 Z 12345678 저장 (Saveit) (IOI10_saveit) C++17
75 / 100
 137 ms 16452 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)
{
    if (x==0) encode_bit(0), encode_bit(0);
    if (x==1) encode_bit(0), encode_bit(1);
    if (x==-1) encode_bit(1), encode_bit(1);
}

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<n; i++) send_value(res[i]);
}

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<N; i++)
        {
            int a=decode_bit(), b=2*a+decode_bit();
            vl[i]=(b==3)?-1:b;
            //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

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 16452 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 19 ms 11292 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 22 ms 12084 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 20 ms 12052 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 32 ms 11940 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 19 ms 11616 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 18 ms 11544 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 18 ms 11552 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 19 ms 11592 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 23 ms 11560 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 34 ms 12048 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 18 ms 11564 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 19 ms 11720 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 36 ms 12084 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 30 ms 12032 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 40 ms 12100 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 25 ms 11924 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 43 ms 14412 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 53 ms 14416 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 36 ms 12028 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 48 ms 14424 KB Output is partially correct - 79920 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 16452 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 19 ms 11292 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 22 ms 12084 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 20 ms 12052 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 32 ms 11940 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 19 ms 11616 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 18 ms 11544 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 18 ms 11552 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 19 ms 11592 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 23 ms 11560 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 34 ms 12048 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 18 ms 11564 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 19 ms 11720 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 36 ms 12084 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 30 ms 12032 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 40 ms 12100 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 25 ms 11924 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 43 ms 14412 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 53 ms 14416 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 36 ms 12028 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 48 ms 14424 KB Output is partially correct - 79920 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 16452 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 19 ms 11292 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 22 ms 12084 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 20 ms 12052 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 32 ms 11940 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 19 ms 11616 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 18 ms 11544 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 18 ms 11552 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 19 ms 11592 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 23 ms 11560 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 34 ms 12048 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 18 ms 11564 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 19 ms 11720 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 36 ms 12084 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 30 ms 12032 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 40 ms 12100 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 25 ms 11924 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 43 ms 14412 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 53 ms 14416 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 36 ms 12028 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 48 ms 14424 KB Output is partially correct - 79920 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 16452 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 19 ms 11292 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 22 ms 12084 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 20 ms 12052 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 32 ms 11940 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 19 ms 11616 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 18 ms 11544 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 18 ms 11552 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 19 ms 11592 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 23 ms 11560 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 34 ms 12048 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 18 ms 11564 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 19 ms 11720 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 36 ms 12084 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 30 ms 12032 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 40 ms 12100 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 25 ms 11924 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 43 ms 14412 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 53 ms 14416 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 36 ms 12028 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 48 ms 14424 KB Output is partially correct - 79920 call(s) of encode_bit()