oj.uz

Submission #895735

# Submission time Handle Problem Language Result Execution time Memory
895735 2023-12-30T17:01:00 Z abcvuitunggio Saveit (IOI10_saveit) C++17
100 / 100
 151 ms 16700 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
static vector <int> ke[1000];
static int p[1000],vis[1000],d[1000];
static void dfs(int u){
    vis[u]=1;
    for (int v:ke[u])
        if (!vis[v]){
            p[v]=u;
            dfs(v);
        }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
    for (int i=0;i<ne;i++){
        ke[v1[i]].push_back(v2[i]);
        ke[v2[i]].push_back(v1[i]);
    }
    dfs(0);
    for (int i=1;i<nv;i++)
        for (int j=9;j>=0;j--)
            encode_bit((p[i]>>j)&1);
    queue <int> q;
    for (int i=0;i<nh;i++){
        fill(d,d+nv,-1);
        q.push(i);
        d[i]=0;
        while (!q.empty()){
            int u=q.front();
            q.pop();
            for (int v:ke[u])
                if (d[v]==-1){
                    d[v]=d[u]+1;
                    q.push(v);
                }
        }
        for (int j=0;j*10<nv;j++){
            int val=0;
            for (int k=min(j*10+9,nv-1);k>=j*10;k--)
                val=val*3+d[k]-d[p[k]]+1;
            for (int j=15;j>=0;j--)
                encode_bit((val>>j)&1);
        }
    }
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
static int p[1000],d[1000];
static vector <int> ke[1000];
static int get(int i){
    int val=0;
    while (i--)
        val=val*2+decode_bit();
    return val;
}
static void dfs(int u, int par, int hub, int dist){
    hops(hub,u,dist);
    for (int v:ke[u])
        if (v!=par)
            dfs(v,u,hub,dist+d[v]);
    if (u&&p[u]!=par)
        dfs(p[u],u,hub,dist-d[u]);
}
void decode(int nv, int nh){
    for (int i=1;i<nv;i++){
        p[i]=get(10);
        ke[p[i]].push_back(i);
    }
    for (int i=0;i<nh;i++){
        for (int j=0;j*10<nv;j++){
            int val=get(16);
            for (int k=j*10;k<min(j*10+10,nv);k++,val/=3)
                d[k]=val%3-1;
        }
        dfs(i,i,i,0);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 16700 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 16 ms 11524 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 19 ms 12308 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 12324 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 28 ms 12048 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 16 ms 11660 KB Output is correct - 65472 call(s) of encode_bit()
9 Correct 17 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 17 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 22 ms 11748 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 18 ms 11520 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 36 ms 12264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 16 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 11708 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 12216 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 27 ms 12064 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 12480 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 24 ms 12092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 37 ms 14420 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 45 ms 14704 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 31 ms 12308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 48 ms 14720 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 16700 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 16 ms 11524 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 19 ms 12308 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 12324 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 28 ms 12048 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 16 ms 11660 KB Output is correct - 65472 call(s) of encode_bit()
9 Correct 17 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 17 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 22 ms 11748 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 18 ms 11520 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 36 ms 12264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 16 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 11708 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 12216 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 27 ms 12064 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 12480 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 24 ms 12092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 37 ms 14420 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 45 ms 14704 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 31 ms 12308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 48 ms 14720 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 16700 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 16 ms 11524 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 19 ms 12308 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 12324 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 28 ms 12048 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 16 ms 11660 KB Output is correct - 65472 call(s) of encode_bit()
9 Correct 17 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 17 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 22 ms 11748 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 18 ms 11520 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 36 ms 12264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 16 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 11708 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 12216 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 27 ms 12064 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 12480 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 24 ms 12092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 37 ms 14420 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 45 ms 14704 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 31 ms 12308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 48 ms 14720 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 16700 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 88 call(s) of encode_bit()
3 Correct 16 ms 11524 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 11264 KB Output is correct - 120 call(s) of encode_bit()
5 Correct 19 ms 12308 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 12324 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 28 ms 12048 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 16 ms 11660 KB Output is correct - 65472 call(s) of encode_bit()
9 Correct 17 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 17 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 22 ms 11748 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 18 ms 11520 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 36 ms 12264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 16 ms 11536 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 11708 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 12216 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 27 ms 12064 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 12480 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 24 ms 12092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 37 ms 14420 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 45 ms 14704 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 31 ms 12308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 48 ms 14720 KB Output is correct - 67590 call(s) of encode_bit()