oj.uz

Submission #271205

# Submission time Handle Problem Language Result Execution time Memory
271205 2020-08-18T05:09:09 Z 최은수(#5096) Saveit (IOI10_saveit) C++14
100 / 100
 274 ms 11456 KB 
#include"grader.h"
#include"encoder.h"
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
static vector<int>adj[1010];
static vector<int>make(int n,int sc)
{
    vector<bool>chk(n,0);
    vector<int>pa(n,0);
    chk[sc]=1;
    pa[sc]=0;
    queue<int>q;
    q.ep(sc);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int&t:adj[x])
            if(!chk[t])
                chk[t]=1,pa[t]=x,q.ep(t);
    }
    return pa;
}
static vector<int>calc(int n,int sc)
{
    vector<bool>chk(n,0);
    vector<int>dis(n,0);
    chk[sc]=1;
    dis[sc]=0;
    queue<int>q;
    q.ep(sc);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int&t:adj[x])
            if(!chk[t])
                chk[t]=1,dis[t]=dis[x]+1,q.ep(t);
    }
    return dis;
}
void encode(int nv,int nh,int ne,int*v1,int*v2)
{
    for(int i=0;i<ne;i++)
        adj[v1[i]].eb(v2[i]),adj[v2[i]].eb(v1[i]);
    vector<int>pa=make(nv,0);
    for(int i=1;i<nv;i++)
        for(int j=0;j<10;j++)
            encode_bit(pa[i]>>j&1);
    for(int i=0;i<nh;i++)
    {
        vector<int>d=calc(nv,i);
        vector<int>w(nv,0);
        for(int i=1;i<nv;i++)
            w[i]=d[i]-d[pa[i]];
        for(int i=0;i<nv;i+=5)
        {
            int val=0;
            for(int j=0,p=1;j<5&&i+j<nv;j++,p*=3)
                val+=(w[i+j]+1)*p;
            for(int j=0;j<8;j++)
                encode_bit(val>>j&1);
        }
    }
    return;
}
#include"grader.h"
#include"decoder.h"
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
static int w[1010];
static vector<int>adj[1010];
static int dep[1010];
static void dfs(int x)
{
    for(int&t:adj[x])
        dep[t]=dep[x]+w[t],dfs(t);
    return;
}
void decode(int nv,int nh)
{
    for(int i=1;i<nv;i++)
    {
        int p=0;
        for(int j=0;j<10;j++)
            p|=decode_bit()<<j;
        adj[p].eb(i);
    }
    for(int sc=0;sc<nh;sc++)
    {
        for(int i=0;i<nv;i+=5)
        {
            int val=0;
            for(int j=0;j<8;j++)
                val|=decode_bit()<<j;
            for(int j=0;j<5&&i+j<nv;j++)
                w[i+j]=val%3-1,val/=3;
        }
        dep[0]=0;
        dfs(0);
        for(int i=0;i<nv;i++)
            hops(sc,i,dep[i]-dep[sc]);
    }
    return;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 11456 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4812 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 30 ms 5740 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4804 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 38 ms 5888 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 37 ms 5672 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 54 ms 6004 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5392 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 34 ms 5728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 28 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 37 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 28 ms 5588 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 68 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5720 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5664 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 65 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 47 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 57 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 61 ms 5916 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 74 ms 6596 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 108 ms 6648 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 53 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 91 ms 7036 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 11456 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4812 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 30 ms 5740 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4804 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 38 ms 5888 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 37 ms 5672 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 54 ms 6004 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5392 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 34 ms 5728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 28 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 37 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 28 ms 5588 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 68 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5720 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5664 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 65 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 47 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 57 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 61 ms 5916 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 74 ms 6596 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 108 ms 6648 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 53 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 91 ms 7036 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 11456 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4812 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 30 ms 5740 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4804 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 38 ms 5888 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 37 ms 5672 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 54 ms 6004 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5392 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 34 ms 5728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 28 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 37 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 28 ms 5588 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 68 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5720 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5664 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 65 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 47 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 57 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 61 ms 5916 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 74 ms 6596 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 108 ms 6648 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 53 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 91 ms 7036 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 11456 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4812 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 30 ms 5740 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4804 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 38 ms 5888 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 37 ms 5672 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 54 ms 6004 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 27 ms 5392 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 34 ms 5728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 28 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 37 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 28 ms 5588 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 68 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5720 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5664 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 65 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 47 ms 6024 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 57 ms 6264 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 61 ms 5916 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 74 ms 6596 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 108 ms 6648 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 53 ms 6272 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 91 ms 7036 KB Output is correct - 67590 call(s) of encode_bit()