oj.uz

답안 #64417

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64417 2018-08-04T11:22:15 Z Abelyan 저장 (Saveit) (IOI10_saveit) C++17
100 / 100
 333 ms 12240 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
 
#define fr first
#define sc second
#define cout cerr
 
const int N=1006,H=40,P3[6]={1,3,9,27,81,243};
vector<int> g[N],graph[N];
int pars[N],pr[H][N];
bool col[N];
queue<pair<int,int> > q;
int dist[N][H];
 
void to_bit(int k){
    for (int i=9;i>=0;i--){
        if (k&(1<<i)){
            encode_bit(1);
        }
        else{
            encode_bit(0);
        }
    }
}
 
void dfs(int v,int p=-1){
    col[v]=true;
    for (int i=0;i<g[v].size();i++){
        int to=g[v][i];
        if (!col[to]) dfs(to,v);
    }
    pars[v]=p;
}
 
void dfshub(int v,int hub,int p=-1){
    //cout<<v<<" "<<hub<<" "<<p<<endl;
    for (int i=0;i<graph[v].size();i++){
        int to=graph[v][i];
        if (to!=p)dfshub(to,hub,v);
    }
    if (p!=-1)
        pr[hub][v]=p;
}
 
void encode(int n, int h, int m, int *a, int *b){
    for (int i=0;i<m;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0);
    for (int i=0;i<h;i++){
        for (int j=0;j<n;j++)col[j]=false;
        q.push({i,0});
        col[i]=true;
        while(!q.empty()){
            int v=q.front().fr,len=q.front().sc;
            q.pop();
            dist[v][i]=len;
            for (int j=0;j<g[v].size();j++){
                int to=g[v][j];
                if (!col[to]){
                    q.push({to,len+1});
                    col[to]=true;
                }
            }
        }
    }
    /*
    for (int i=0;i<h;i++){
        for (int j=0;j<n;j++){
            cout<<dist[j][i]<<" ";
        }
        cout<<endl;
    }
    */
    for (int i=1;i<n;i++){
        to_bit(pars[i]);
        graph[i].push_back(pars[i]);
        graph[pars[i]].push_back(i);
    }
    for (int i=0;i<h;i++)dfshub(i,i);
    for (int i=0;i<n;i++){
        int ans=0;
        for (int j=0;j<36;j++){
            //if (j==2)cout<<dist[i][j]-dist[pr[j][i]][j]+1<<" ";
          	if (i!=j)
            	ans+=P3[(6-((j+1)%6))%6]*(dist[i][j]-dist[pr[j][i]][j]+1);
            if ((j+1)%6==0){
                to_bit(ans);
                //cout<<ans<<endl;
                ans=0;
            }
            //cout<<dist[i][j]-dist[pr[j][i]][j]+1<<" ";
        }
        //cout<<endl;
    }
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
 
#define fr first
#define sc second
#define cout cerr
 
const int N=1006,H=40,P3[6]={1,3,9,27,81,243};
vector<int> gr[N];
int tarb[N][H];
 
int to_dec(){
    int ans=0;
    for (int i=9;i>=0;i--){
        ans+=(1<<i)*decode_bit();
    }
    //cout<<ans<<endl;
    return ans;
}
 
void to_tr(int k,int arr[]){
    for (int i=5;i>=0;i--){
        arr[5-i]=k/P3[i];
        k%=P3[i];
    }
}
 
void dfsdec(int v,int ans,int hub,int par=-1){
    for (int i=0;i<gr[v].size();i++){
        int to=gr[v][i];
        if (to!=par)
            dfsdec(to,ans+tarb[to][hub]-1,hub,v);
    }
    hops(hub,v,ans);
}
 
void decode(int n, int h) {
    //cout<<"hi"<<endl;
    for (int i=1;i<n;i++){
        int p=to_dec();
        //cout<<p<<" ";
        gr[p].push_back(i);
        gr[i].push_back(p);
    }
    //cout<<endl;
    for (int i=0;i<n;i++){
        for (int j=0;j<6;j++){
            to_tr(to_dec(),tarb[i]+(j*6));
        }
        for (int j=0;j<36;j++){
            //cout<<tarb[i][j]<<" ";
        }
        //cout<<endl;
    }
    for (int i=0;i<h;i++){
        dfsdec(i,0,i);
    }
}

Compilation message

encoder.cpp: In function 'void dfs(int, int)':
encoder.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<g[v].size();i++){
                  ~^~~~~~~~~~~~
encoder.cpp: In function 'void dfshub(int, int, int)':
encoder.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<graph[v].size();i++){
                  ~^~~~~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=0;j<g[v].size();j++){
                          ~^~~~~~~~~~~~

decoder.cpp: In function 'void dfsdec(int, int, int, int)':
decoder.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<gr[v].size();i++){
                  ~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 12240 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 6 ms 4928 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 33 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 41 ms 6204 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 43 ms 6252 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 72 ms 6652 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 30 ms 6124 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 36 ms 6180 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 6076 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 41 ms 6156 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 32 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 73 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 33 ms 6204 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 36 ms 6248 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 74 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 90 ms 6876 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 88 ms 6940 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 59 ms 6460 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 85 ms 7240 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 109 ms 7408 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 90 ms 6844 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 123 ms 7460 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 12240 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 6 ms 4928 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 33 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 41 ms 6204 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 43 ms 6252 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 72 ms 6652 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 30 ms 6124 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 36 ms 6180 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 6076 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 41 ms 6156 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 32 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 73 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 33 ms 6204 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 36 ms 6248 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 74 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 90 ms 6876 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 88 ms 6940 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 59 ms 6460 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 85 ms 7240 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 109 ms 7408 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 90 ms 6844 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 123 ms 7460 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 12240 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 6 ms 4928 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 33 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 41 ms 6204 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 43 ms 6252 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 72 ms 6652 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 30 ms 6124 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 36 ms 6180 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 6076 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 41 ms 6156 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 32 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 73 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 33 ms 6204 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 36 ms 6248 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 74 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 90 ms 6876 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 88 ms 6940 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 59 ms 6460 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 85 ms 7240 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 109 ms 7408 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 90 ms 6844 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 123 ms 7460 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 12240 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 6 ms 4928 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 33 ms 5948 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 7 ms 4672 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 41 ms 6204 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 43 ms 6252 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 72 ms 6652 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 30 ms 6124 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 36 ms 6180 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 6076 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 41 ms 6156 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 32 ms 6000 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 73 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 33 ms 6204 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 36 ms 6248 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 74 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 90 ms 6876 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 88 ms 6940 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 59 ms 6460 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 85 ms 7240 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 109 ms 7408 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 90 ms 6844 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 123 ms 7460 KB Output is correct - 69990 call(s) of encode_bit()