oj.uz

Submission #254277

# Submission time Handle Problem Language Result Execution time Memory
254277 2020-07-29T17:12:24 Z MKopchev Saveit (IOI10_saveit) C++14
50 / 100
 519 ms 19448 KB 
#include "grader.h"
#include "encoder.h"

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e3+42;

queue< pair<int/*parent*/,int/*node*/> > q,idle;
int parent[nmax],dist[nmax];
vector< int > adj[nmax];

int PARENT[nmax];

void dfs(int node,int par)
{
    PARENT[node]=par;

    for(auto k:adj[node])
        if(k!=par)
            dfs(k,node);
}

int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}
void encode(int nv, int nh, int ne, int *v1, int *v2){

    for(int i=0;i<nv;i++)parent[i]=i;

    for(int i=0;i<ne;i++)
    {
        int p=v1[i],q=v2[i];

        if(root(p)==root(q))continue;

        parent[root(p)]=root(q);

        adj[p].push_back(q);
        adj[q].push_back(p);
    }

    dfs(0,0);

    //for(int i=0;i<nv;i++)cout<<PARENT[i]<<" ";cout<<endl;

    for(int i=0;i<nv;i++)adj[i]={};

    for(int i=0;i<ne;i++)
    {
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }

    for(int i=0;i<nv;i++)
    {
        for(int j=9;j>=0;j--)
            if((PARENT[i]&(1<<j)))encode_bit(1);
            else encode_bit(0);
    }

    for(int i=0;i<nh;i++)
    {
        for(int j=0;j<nv;j++)parent[j]=-1,dist[j]=-1;
        q=idle;
        q.push({-1,i});
        while(q.size())
        {
            pair<int/*parent*/,int/*node*/> now=q.front();
            q.pop();
            if(dist[now.second]!=-1)continue;
            if(now.first==-1)
            {
                dist[now.second]=0;
                parent[now.second]=-1;
            }
            else
            {
                dist[now.second]=dist[now.first]+1;
                parent[now.second]=now.first;
            }
            for(auto k:adj[now.second])
                q.push({now.second,k});
        }
        /*
        cout<<endl;
        cout<<i<<" -> ";for(int j=0;j<nv;j++)cout<<dist[j]<<" ";cout<<endl;
        */
        for(int k=0;k<nv;k++)
        {
            int delta=dist[k]-dist[PARENT[k]];
            if(delta==-1)
            {
                encode_bit(0);
                encode_bit(0);
            }
            else if(delta==0)
            {
                encode_bit(0);
                encode_bit(1);
            }
            else
            {
                encode_bit(1);
                encode_bit(0);
            }
        }
    }
}

#include "grader.h"
#include "decoder.h"

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e3+42;


vector<int> other_adj[nmax];
int par_decode[nmax];

int DIFF[nmax];

int actual[nmax];

void dfs_decode(int node,int par,int sum)
{
    sum+=DIFF[node];

    actual[node]=sum;

    for(auto k:other_adj[node])
        if(k!=par)
            dfs_decode(k,node,sum);
}
void decode(int nv, int nh) {
    for(int i=0;i<nv;i++)
    {
        int val=0;
        for(int j=0;j<=9;j++)
            val=val*2+decode_bit();

        par_decode[i]=val;

        if(i!=val)
        {
            other_adj[i].push_back(val);
            other_adj[val].push_back(i);
        }
    }

    for(int i=0;i<nh;i++)
    {
        for(int j=0;j<nv;j++)
        {
            int p=decode_bit();
            int q=decode_bit();

            DIFF[j]=2*p+q-1;
        }

        dfs_decode(0,0,0);

        for(int j=0;j<nv;j++)
        {
            int sum=actual[j]-actual[i];

            hops(i,j,sum);
        }
        //cout<<"---"<<endl;
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 19448 KB Output is partially correct - 82000 call(s) of encode_bit()
2 Correct 3 ms 4792 KB Output is correct - 80 call(s) of encode_bit()
3 Correct 28 ms 5504 KB Output is partially correct - 73800 call(s) of encode_bit()
4 Correct 3 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is partially correct - 73800 call(s) of encode_bit()
6 Correct 45 ms 5880 KB Output is partially correct - 82000 call(s) of encode_bit()
7 Correct 113 ms 6736 KB Output is partially correct - 82000 call(s) of encode_bit()
8 Correct 26 ms 5672 KB Output is partially correct - 78802 call(s) of encode_bit()
9 Correct 32 ms 5784 KB Output is partially correct - 82000 call(s) of encode_bit()
10 Correct 33 ms 5860 KB Output is partially correct - 82000 call(s) of encode_bit()
11 Correct 46 ms 6076 KB Output is partially correct - 82000 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is partially correct - 82000 call(s) of encode_bit()
13 Correct 93 ms 6932 KB Output is partially correct - 82000 call(s) of encode_bit()
14 Correct 34 ms 5760 KB Output is partially correct - 82000 call(s) of encode_bit()
15 Correct 38 ms 5892 KB Output is partially correct - 82000 call(s) of encode_bit()
16 Correct 95 ms 7140 KB Output is partially correct - 82000 call(s) of encode_bit()
17 Correct 73 ms 6568 KB Output is partially correct - 82000 call(s) of encode_bit()
18 Correct 93 ms 7064 KB Output is partially correct - 82000 call(s) of encode_bit()
19 Correct 65 ms 6264 KB Output is partially correct - 82000 call(s) of encode_bit()
20 Correct 174 ms 7468 KB Output is partially correct - 82000 call(s) of encode_bit()
21 Correct 215 ms 7864 KB Output is partially correct - 82000 call(s) of encode_bit()
22 Correct 126 ms 6968 KB Output is partially correct - 82000 call(s) of encode_bit()
23 Correct 210 ms 8096 KB Output is partially correct - 82000 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 19448 KB Output is partially correct - 82000 call(s) of encode_bit()
2 Correct 3 ms 4792 KB Output is correct - 80 call(s) of encode_bit()
3 Correct 28 ms 5504 KB Output is partially correct - 73800 call(s) of encode_bit()
4 Correct 3 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is partially correct - 73800 call(s) of encode_bit()
6 Correct 45 ms 5880 KB Output is partially correct - 82000 call(s) of encode_bit()
7 Correct 113 ms 6736 KB Output is partially correct - 82000 call(s) of encode_bit()
8 Correct 26 ms 5672 KB Output is partially correct - 78802 call(s) of encode_bit()
9 Correct 32 ms 5784 KB Output is partially correct - 82000 call(s) of encode_bit()
10 Correct 33 ms 5860 KB Output is partially correct - 82000 call(s) of encode_bit()
11 Correct 46 ms 6076 KB Output is partially correct - 82000 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is partially correct - 82000 call(s) of encode_bit()
13 Correct 93 ms 6932 KB Output is partially correct - 82000 call(s) of encode_bit()
14 Correct 34 ms 5760 KB Output is partially correct - 82000 call(s) of encode_bit()
15 Correct 38 ms 5892 KB Output is partially correct - 82000 call(s) of encode_bit()
16 Correct 95 ms 7140 KB Output is partially correct - 82000 call(s) of encode_bit()
17 Correct 73 ms 6568 KB Output is partially correct - 82000 call(s) of encode_bit()
18 Correct 93 ms 7064 KB Output is partially correct - 82000 call(s) of encode_bit()
19 Correct 65 ms 6264 KB Output is partially correct - 82000 call(s) of encode_bit()
20 Correct 174 ms 7468 KB Output is partially correct - 82000 call(s) of encode_bit()
21 Correct 215 ms 7864 KB Output is partially correct - 82000 call(s) of encode_bit()
22 Correct 126 ms 6968 KB Output is partially correct - 82000 call(s) of encode_bit()
23 Correct 210 ms 8096 KB Output is partially correct - 82000 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 19448 KB Output is partially correct - 82000 call(s) of encode_bit()
2 Correct 3 ms 4792 KB Output is correct - 80 call(s) of encode_bit()
3 Correct 28 ms 5504 KB Output is partially correct - 73800 call(s) of encode_bit()
4 Correct 3 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is partially correct - 73800 call(s) of encode_bit()
6 Correct 45 ms 5880 KB Output is partially correct - 82000 call(s) of encode_bit()
7 Correct 113 ms 6736 KB Output is partially correct - 82000 call(s) of encode_bit()
8 Correct 26 ms 5672 KB Output is partially correct - 78802 call(s) of encode_bit()
9 Correct 32 ms 5784 KB Output is partially correct - 82000 call(s) of encode_bit()
10 Correct 33 ms 5860 KB Output is partially correct - 82000 call(s) of encode_bit()
11 Correct 46 ms 6076 KB Output is partially correct - 82000 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is partially correct - 82000 call(s) of encode_bit()
13 Correct 93 ms 6932 KB Output is partially correct - 82000 call(s) of encode_bit()
14 Correct 34 ms 5760 KB Output is partially correct - 82000 call(s) of encode_bit()
15 Correct 38 ms 5892 KB Output is partially correct - 82000 call(s) of encode_bit()
16 Correct 95 ms 7140 KB Output is partially correct - 82000 call(s) of encode_bit()
17 Correct 73 ms 6568 KB Output is partially correct - 82000 call(s) of encode_bit()
18 Correct 93 ms 7064 KB Output is partially correct - 82000 call(s) of encode_bit()
19 Correct 65 ms 6264 KB Output is partially correct - 82000 call(s) of encode_bit()
20 Correct 174 ms 7468 KB Output is partially correct - 82000 call(s) of encode_bit()
21 Correct 215 ms 7864 KB Output is partially correct - 82000 call(s) of encode_bit()
22 Correct 126 ms 6968 KB Output is partially correct - 82000 call(s) of encode_bit()
23 Correct 210 ms 8096 KB Output is partially correct - 82000 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 19448 KB Output is partially correct - 82000 call(s) of encode_bit()
2 Correct 3 ms 4792 KB Output is correct - 80 call(s) of encode_bit()
3 Correct 28 ms 5504 KB Output is partially correct - 73800 call(s) of encode_bit()
4 Correct 3 ms 4736 KB Output is correct - 100 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is partially correct - 73800 call(s) of encode_bit()
6 Correct 45 ms 5880 KB Output is partially correct - 82000 call(s) of encode_bit()
7 Correct 113 ms 6736 KB Output is partially correct - 82000 call(s) of encode_bit()
8 Correct 26 ms 5672 KB Output is partially correct - 78802 call(s) of encode_bit()
9 Correct 32 ms 5784 KB Output is partially correct - 82000 call(s) of encode_bit()
10 Correct 33 ms 5860 KB Output is partially correct - 82000 call(s) of encode_bit()
11 Correct 46 ms 6076 KB Output is partially correct - 82000 call(s) of encode_bit()
12 Correct 27 ms 5772 KB Output is partially correct - 82000 call(s) of encode_bit()
13 Correct 93 ms 6932 KB Output is partially correct - 82000 call(s) of encode_bit()
14 Correct 34 ms 5760 KB Output is partially correct - 82000 call(s) of encode_bit()
15 Correct 38 ms 5892 KB Output is partially correct - 82000 call(s) of encode_bit()
16 Correct 95 ms 7140 KB Output is partially correct - 82000 call(s) of encode_bit()
17 Correct 73 ms 6568 KB Output is partially correct - 82000 call(s) of encode_bit()
18 Correct 93 ms 7064 KB Output is partially correct - 82000 call(s) of encode_bit()
19 Correct 65 ms 6264 KB Output is partially correct - 82000 call(s) of encode_bit()
20 Correct 174 ms 7468 KB Output is partially correct - 82000 call(s) of encode_bit()
21 Correct 215 ms 7864 KB Output is partially correct - 82000 call(s) of encode_bit()
22 Correct 126 ms 6968 KB Output is partially correct - 82000 call(s) of encode_bit()
23 Correct 210 ms 8096 KB Output is partially correct - 82000 call(s) of encode_bit()