oj.uz

Submission #271202

# Submission time Handle Problem Language Result Execution time Memory
271202 2020-08-18T05:07:33 Z 최은수(#5096) Saveit (IOI10_saveit) C++14
0 / 100
 248 ms 11248 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[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[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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 11248 KB Output isn't correct
2 Correct 4 ms 4992 KB Output is correct - 64 call(s) of encode_bit()
3 Incorrect 22 ms 5628 KB wrong parameter
4 Correct 4 ms 4736 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 30 ms 5632 KB wrong parameter
6 Incorrect 31 ms 5632 KB wrong parameter
7 Incorrect 53 ms 6104 KB wrong parameter
8 Incorrect 26 ms 5408 KB wrong parameter
9 Incorrect 25 ms 5592 KB wrong parameter
10 Incorrect 33 ms 5760 KB Output isn't correct
11 Incorrect 36 ms 5708 KB wrong parameter
12 Incorrect 27 ms 5376 KB Output isn't correct
13 Incorrect 62 ms 6264 KB wrong parameter
14 Incorrect 25 ms 5596 KB wrong parameter
15 Incorrect 27 ms 5584 KB wrong parameter
16 Incorrect 46 ms 6148 KB wrong parameter
17 Incorrect 48 ms 5888 KB wrong parameter
18 Incorrect 59 ms 6376 KB wrong parameter
19 Incorrect 41 ms 5912 KB wrong parameter
20 Incorrect 71 ms 6716 KB wrong parameter
21 Incorrect 88 ms 6752 KB wrong parameter
22 Incorrect 51 ms 6192 KB wrong parameter
23 Incorrect 82 ms 7156 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 11248 KB Output isn't correct
2 Correct 4 ms 4992 KB Output is correct - 64 call(s) of encode_bit()
3 Incorrect 22 ms 5628 KB wrong parameter
4 Correct 4 ms 4736 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 30 ms 5632 KB wrong parameter
6 Incorrect 31 ms 5632 KB wrong parameter
7 Incorrect 53 ms 6104 KB wrong parameter
8 Incorrect 26 ms 5408 KB wrong parameter
9 Incorrect 25 ms 5592 KB wrong parameter
10 Incorrect 33 ms 5760 KB Output isn't correct
11 Incorrect 36 ms 5708 KB wrong parameter
12 Incorrect 27 ms 5376 KB Output isn't correct
13 Incorrect 62 ms 6264 KB wrong parameter
14 Incorrect 25 ms 5596 KB wrong parameter
15 Incorrect 27 ms 5584 KB wrong parameter
16 Incorrect 46 ms 6148 KB wrong parameter
17 Incorrect 48 ms 5888 KB wrong parameter
18 Incorrect 59 ms 6376 KB wrong parameter
19 Incorrect 41 ms 5912 KB wrong parameter
20 Incorrect 71 ms 6716 KB wrong parameter
21 Incorrect 88 ms 6752 KB wrong parameter
22 Incorrect 51 ms 6192 KB wrong parameter
23 Incorrect 82 ms 7156 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 11248 KB Output isn't correct
2 Correct 4 ms 4992 KB Output is correct - 64 call(s) of encode_bit()
3 Incorrect 22 ms 5628 KB wrong parameter
4 Correct 4 ms 4736 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 30 ms 5632 KB wrong parameter
6 Incorrect 31 ms 5632 KB wrong parameter
7 Incorrect 53 ms 6104 KB wrong parameter
8 Incorrect 26 ms 5408 KB wrong parameter
9 Incorrect 25 ms 5592 KB wrong parameter
10 Incorrect 33 ms 5760 KB Output isn't correct
11 Incorrect 36 ms 5708 KB wrong parameter
12 Incorrect 27 ms 5376 KB Output isn't correct
13 Incorrect 62 ms 6264 KB wrong parameter
14 Incorrect 25 ms 5596 KB wrong parameter
15 Incorrect 27 ms 5584 KB wrong parameter
16 Incorrect 46 ms 6148 KB wrong parameter
17 Incorrect 48 ms 5888 KB wrong parameter
18 Incorrect 59 ms 6376 KB wrong parameter
19 Incorrect 41 ms 5912 KB wrong parameter
20 Incorrect 71 ms 6716 KB wrong parameter
21 Incorrect 88 ms 6752 KB wrong parameter
22 Incorrect 51 ms 6192 KB wrong parameter
23 Incorrect 82 ms 7156 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 11248 KB Output isn't correct
2 Correct 4 ms 4992 KB Output is correct - 64 call(s) of encode_bit()
3 Incorrect 22 ms 5628 KB wrong parameter
4 Correct 4 ms 4736 KB Output is correct - 80 call(s) of encode_bit()
5 Incorrect 30 ms 5632 KB wrong parameter
6 Incorrect 31 ms 5632 KB wrong parameter
7 Incorrect 53 ms 6104 KB wrong parameter
8 Incorrect 26 ms 5408 KB wrong parameter
9 Incorrect 25 ms 5592 KB wrong parameter
10 Incorrect 33 ms 5760 KB Output isn't correct
11 Incorrect 36 ms 5708 KB wrong parameter
12 Incorrect 27 ms 5376 KB Output isn't correct
13 Incorrect 62 ms 6264 KB wrong parameter
14 Incorrect 25 ms 5596 KB wrong parameter
15 Incorrect 27 ms 5584 KB wrong parameter
16 Incorrect 46 ms 6148 KB wrong parameter
17 Incorrect 48 ms 5888 KB wrong parameter
18 Incorrect 59 ms 6376 KB wrong parameter
19 Incorrect 41 ms 5912 KB wrong parameter
20 Incorrect 71 ms 6716 KB wrong parameter
21 Incorrect 88 ms 6752 KB wrong parameter
22 Incorrect 51 ms 6192 KB wrong parameter
23 Incorrect 82 ms 7156 KB wrong parameter