oj.uz

Submission #254280

# Submission time Handle Problem Language Result Execution time Memory
254280 2020-07-29T17:38:25 Z MKopchev Saveit (IOI10_saveit) C++14
100 / 100
 530 ms 19528 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);

        //cout<<"adj "<<p<<" "<<q<<endl;
    }

    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);
    }

    int hsh=0,in=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]]+1;

            in++;

            hsh=hsh*3+delta;

            if(in==3)
            {
                in=0;
                for(int t=4;t>=0;t--)
                    if((hsh&(1<<t)))encode_bit(1);
                    else encode_bit(0);

                hsh=0;
            }
        }
    }

    if(in==0)return;

    while(in%3)
    {
        in++;
        hsh=hsh*3;
    }

    for(int t=4;t>=0;t--)
        if((hsh&(1<<t)))encode_bit(1);
        else 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*50];

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);
}

int HELP[nmax*nmax],pointer;

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;

        //cout<<i<<" -> "<<val<<endl;

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

    for(int i=0;i<nh;i++)
    {
        //cout<<"i= "<<i<<endl;

        for(int j=0;j<nv;j++)
            if((i*nv+j)%3==0)
            {
                int arr[5];
                arr[0]=decode_bit();
                arr[1]=decode_bit();
                arr[2]=decode_bit();
                arr[3]=decode_bit();
                arr[4]=decode_bit();

                int num=arr[0]*16+arr[1]*8+arr[2]*4+arr[3]*2+arr[4];

                HELP[pointer]=num/9-1;
                HELP[pointer+1]=num%9/3-1;
                HELP[pointer+2]=num%3-1;

                pointer+=3;
            }

        for(int j=0;j<nv;j++)
            DIFF[j]=HELP[i*nv+j];

        dfs_decode(0,0,0);

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

        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 530 ms 19528 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 5140 KB Output is correct - 75 call(s) of encode_bit()
3 Correct 27 ms 5632 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 2 ms 4776 KB Output is correct - 95 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 40 ms 5880 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 75 ms 6668 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 26 ms 5876 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 43 ms 5792 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 42 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 25 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 90 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 30 ms 5764 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 84 ms 6776 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 77 ms 6896 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 97 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 61 ms 6452 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 114 ms 7892 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 133 ms 8044 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 89 ms 7044 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 145 ms 8412 KB Output is correct - 70000 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 19528 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 5140 KB Output is correct - 75 call(s) of encode_bit()
3 Correct 27 ms 5632 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 2 ms 4776 KB Output is correct - 95 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 40 ms 5880 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 75 ms 6668 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 26 ms 5876 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 43 ms 5792 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 42 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 25 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 90 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 30 ms 5764 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 84 ms 6776 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 77 ms 6896 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 97 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 61 ms 6452 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 114 ms 7892 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 133 ms 8044 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 89 ms 7044 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 145 ms 8412 KB Output is correct - 70000 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 19528 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 5140 KB Output is correct - 75 call(s) of encode_bit()
3 Correct 27 ms 5632 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 2 ms 4776 KB Output is correct - 95 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 40 ms 5880 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 75 ms 6668 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 26 ms 5876 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 43 ms 5792 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 42 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 25 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 90 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 30 ms 5764 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 84 ms 6776 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 77 ms 6896 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 97 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 61 ms 6452 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 114 ms 7892 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 133 ms 8044 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 89 ms 7044 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 145 ms 8412 KB Output is correct - 70000 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 19528 KB Output is correct - 70000 call(s) of encode_bit()
2 Correct 2 ms 5140 KB Output is correct - 75 call(s) of encode_bit()
3 Correct 27 ms 5632 KB Output is correct - 63000 call(s) of encode_bit()
4 Correct 2 ms 4776 KB Output is correct - 95 call(s) of encode_bit()
5 Correct 39 ms 6016 KB Output is correct - 63000 call(s) of encode_bit()
6 Correct 40 ms 5880 KB Output is correct - 70000 call(s) of encode_bit()
7 Correct 75 ms 6668 KB Output is correct - 70000 call(s) of encode_bit()
8 Correct 26 ms 5876 KB Output is correct - 67270 call(s) of encode_bit()
9 Correct 28 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
10 Correct 43 ms 5792 KB Output is correct - 70000 call(s) of encode_bit()
11 Correct 42 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
12 Correct 25 ms 5760 KB Output is correct - 70000 call(s) of encode_bit()
13 Correct 90 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
14 Correct 30 ms 5764 KB Output is correct - 70000 call(s) of encode_bit()
15 Correct 34 ms 5888 KB Output is correct - 70000 call(s) of encode_bit()
16 Correct 84 ms 6776 KB Output is correct - 70000 call(s) of encode_bit()
17 Correct 77 ms 6896 KB Output is correct - 70000 call(s) of encode_bit()
18 Correct 97 ms 7132 KB Output is correct - 70000 call(s) of encode_bit()
19 Correct 61 ms 6452 KB Output is correct - 70000 call(s) of encode_bit()
20 Correct 114 ms 7892 KB Output is correct - 70000 call(s) of encode_bit()
21 Correct 133 ms 8044 KB Output is correct - 70000 call(s) of encode_bit()
22 Correct 89 ms 7044 KB Output is correct - 70000 call(s) of encode_bit()
23 Correct 145 ms 8412 KB Output is correct - 70000 call(s) of encode_bit()