oj.uz

답안 #254276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254276 2020-07-29T16:56:49 Z MKopchev 저장 (Saveit) (IOI10_saveit) C++14
0 / 100
 522 ms 19552 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<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
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 522 ms 19552 KB wrong parameter
2 Correct 2 ms 4800 KB Output is correct - 80 call(s) of encode_bit()
3 Incorrect 25 ms 5632 KB wrong parameter
4 Correct 2 ms 4792 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 37 ms 6016 KB wrong parameter
6 Incorrect 39 ms 5888 KB wrong parameter
7 Incorrect 80 ms 6520 KB wrong parameter
8 Incorrect 24 ms 5504 KB wrong parameter
9 Incorrect 27 ms 5760 KB wrong parameter
10 Incorrect 28 ms 5632 KB wrong parameter
11 Incorrect 39 ms 5880 KB wrong parameter
12 Incorrect 30 ms 5504 KB wrong parameter
13 Incorrect 89 ms 6968 KB wrong parameter
14 Incorrect 31 ms 5876 KB wrong parameter
15 Incorrect 32 ms 5632 KB wrong parameter
16 Incorrect 82 ms 6884 KB wrong parameter
17 Incorrect 69 ms 6568 KB wrong parameter
18 Incorrect 91 ms 6928 KB wrong parameter
19 Incorrect 54 ms 6288 KB wrong parameter
20 Incorrect 111 ms 7524 KB wrong parameter
21 Incorrect 194 ms 7876 KB wrong parameter
22 Incorrect 82 ms 6904 KB wrong parameter
23 Incorrect 136 ms 8092 KB wrong parameter

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 522 ms 19552 KB wrong parameter
2 Correct 2 ms 4800 KB Output is correct - 80 call(s) of encode_bit()
3 Incorrect 25 ms 5632 KB wrong parameter
4 Correct 2 ms 4792 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 37 ms 6016 KB wrong parameter
6 Incorrect 39 ms 5888 KB wrong parameter
7 Incorrect 80 ms 6520 KB wrong parameter
8 Incorrect 24 ms 5504 KB wrong parameter
9 Incorrect 27 ms 5760 KB wrong parameter
10 Incorrect 28 ms 5632 KB wrong parameter
11 Incorrect 39 ms 5880 KB wrong parameter
12 Incorrect 30 ms 5504 KB wrong parameter
13 Incorrect 89 ms 6968 KB wrong parameter
14 Incorrect 31 ms 5876 KB wrong parameter
15 Incorrect 32 ms 5632 KB wrong parameter
16 Incorrect 82 ms 6884 KB wrong parameter
17 Incorrect 69 ms 6568 KB wrong parameter
18 Incorrect 91 ms 6928 KB wrong parameter
19 Incorrect 54 ms 6288 KB wrong parameter
20 Incorrect 111 ms 7524 KB wrong parameter
21 Incorrect 194 ms 7876 KB wrong parameter
22 Incorrect 82 ms 6904 KB wrong parameter
23 Incorrect 136 ms 8092 KB wrong parameter

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 522 ms 19552 KB wrong parameter
2 Correct 2 ms 4800 KB Output is correct - 80 call(s) of encode_bit()
3 Incorrect 25 ms 5632 KB wrong parameter
4 Correct 2 ms 4792 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 37 ms 6016 KB wrong parameter
6 Incorrect 39 ms 5888 KB wrong parameter
7 Incorrect 80 ms 6520 KB wrong parameter
8 Incorrect 24 ms 5504 KB wrong parameter
9 Incorrect 27 ms 5760 KB wrong parameter
10 Incorrect 28 ms 5632 KB wrong parameter
11 Incorrect 39 ms 5880 KB wrong parameter
12 Incorrect 30 ms 5504 KB wrong parameter
13 Incorrect 89 ms 6968 KB wrong parameter
14 Incorrect 31 ms 5876 KB wrong parameter
15 Incorrect 32 ms 5632 KB wrong parameter
16 Incorrect 82 ms 6884 KB wrong parameter
17 Incorrect 69 ms 6568 KB wrong parameter
18 Incorrect 91 ms 6928 KB wrong parameter
19 Incorrect 54 ms 6288 KB wrong parameter
20 Incorrect 111 ms 7524 KB wrong parameter
21 Incorrect 194 ms 7876 KB wrong parameter
22 Incorrect 82 ms 6904 KB wrong parameter
23 Incorrect 136 ms 8092 KB wrong parameter

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 522 ms 19552 KB wrong parameter
2 Correct 2 ms 4800 KB Output is correct - 80 call(s) of encode_bit()
3 Incorrect 25 ms 5632 KB wrong parameter
4 Correct 2 ms 4792 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 37 ms 6016 KB wrong parameter
6 Incorrect 39 ms 5888 KB wrong parameter
7 Incorrect 80 ms 6520 KB wrong parameter
8 Incorrect 24 ms 5504 KB wrong parameter
9 Incorrect 27 ms 5760 KB wrong parameter
10 Incorrect 28 ms 5632 KB wrong parameter
11 Incorrect 39 ms 5880 KB wrong parameter
12 Incorrect 30 ms 5504 KB wrong parameter
13 Incorrect 89 ms 6968 KB wrong parameter
14 Incorrect 31 ms 5876 KB wrong parameter
15 Incorrect 32 ms 5632 KB wrong parameter
16 Incorrect 82 ms 6884 KB wrong parameter
17 Incorrect 69 ms 6568 KB wrong parameter
18 Incorrect 91 ms 6928 KB wrong parameter
19 Incorrect 54 ms 6288 KB wrong parameter
20 Incorrect 111 ms 7524 KB wrong parameter
21 Incorrect 194 ms 7876 KB wrong parameter
22 Incorrect 82 ms 6904 KB wrong parameter
23 Incorrect 136 ms 8092 KB wrong parameter