oj.uz

Submission #598398

# Submission time Handle Problem Language Result Execution time Memory
598398 2022-07-18T08:47:00 Z mosiashvililuka Saveit (IOI10_saveit) C++14
100 / 100
 199 ms 12492 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
//#define c jdskaj
using namespace std;
//int a,b,c,d,e,i,j,ii,jj,zx,xc;
int J=10,O;
vector <int> v[1009],L,VA[1009];
int MSH[1009],DEP[1009],msh[1009],zm[1009],DIS[39][1009];
int fnd(int q){
    if(msh[q]==q) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
    int qq=q,ww=w;
    q=fnd(q);w=fnd(w);
    if(q==w) return;
    if(zm[q]<zm[w]) swap(q,w);
    msh[w]=q;
    v[qq].push_back(ww);v[ww].push_back(qq);
    if(zm[q]==zm[w]) zm[q]++;
}
void dfsst(int q, int w){
    MSH[q]=w;
    if(w!=-1) DEP[q]=DEP[w]+1; else DEP[q]=0;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfsst((*it),q);
    }
}
void dfs(int q, int w){
    if(w!=-1){
        L.push_back(DIS[O][q]-DIS[O][w]+1);
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs((*it),q);
    }
}
vector <int> totwo(int q){
    vector <int> V;
    /*for(int h=0; h<J; h++){
        if((q&(1<<h))!=0) V.push_back(1); else V.push_back(0);
    }*/
    while(q>0){
        V.push_back(q%2);
        q/=2;
    }
    while(V.size()<J) V.push_back(0);
    return V;
}
int threetodec(vector <int> V){
    int qw=0,we=1;
    for(int h=0; h<V.size(); h++){
        qw+=we*V[h];
        we*=3;
    }
    return qw;
}
void apend(vector <int> V){
    for(int j=0; j<V.size(); j++) encode_bit(V[j]);
}
pair <int, int> P[1000009];
void encode(int nv, int nh, int ne, int *v1, int *v2){
  /*encode_bit(1);
  encode_bit(0);
  return;*/
    int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
    deque <int> de;
    vector <int> V;
    a=nv;H=nh;b=ne;
    for(i=1; i<=b; i++){
        P[i].first=v1[i-1];P[i].second=v2[i-1];
        VA[v1[i-1]].push_back(v2[i-1]);
        VA[v2[i-1]].push_back(v1[i-1]);
    }
    for(i=0; i<a; i++){
        msh[i]=i;zm[i]=1;
    }
    for(i=1; i<=b; i++){
        mrg(P[i].first,P[i].second);
    }
    for(i=0; i<a; i++){
        sort(v[i].begin(),v[i].end());
    }
    for(i=0; i<H; i++){
        while(de.size()) de.pop_back();
        for(j=0; j<a; j++) dis[j]=a+4;
        de.push_back(i);dis[i]=0;
        while(de.size()){
            c=de.front();
            de.pop_front();
            for(vector <int>::iterator it=VA[c].begin(); it!=VA[c].end(); it++){
                if(dis[(*it)]>dis[c]+1){
                    dis[(*it)]=dis[c]+1;
                    de.push_back((*it));
                }
            }
        }
        for(j=0; j<a; j++){
            DIS[i][j]=dis[j];
        }
    }
    dfsst(0,-1);
    for(i=1; i<a; i++){
        c=MSH[i];
        V=totwo(c);
        apend(V);
    }
    //cout<<"DIS "<<DIS[1][0]<<" "<<DIS[1][2]<<"\n";
    for(i=0; i<H; i++){
        V=totwo(DIS[i][0]);
        //cout<<"DEP "<<i<<" "<<DIS[i][0]<<"\n";
        apend(V);
        O=i;L.clear();
        dfs(0,-1);
        /*cout<<"encoder "<<i<<"::\n";
        for(j=0; j<L.size(); j++){
            cout<<L[j]<<" ";
        }
        cout<<"\n";*/
        //cout<<i<<" L "<<L.size()<<"\n";
        for(j=0; j<L.size(); j+=17){
            V.clear();
            int qw=L.size();
            for(jj=j; jj<min(j+17,qw); jj++){
                V.push_back(L[jj]);
            }
            /*if(i==0){
                cout<<i<<" "<<j<<"::\n";
                for(int h=0; h<V.size(); h++) cout<<V[h]<<" ";
                cout<<"\n";
            }*/
            c=threetodec(V);
            V=totwo(c);
            while(V.size()<27) V.push_back(0);
            //cout<<i<<" "<<j<<" V27 "<<V.size()<<"\n";
            /*if(i==0){
                cout<<"####\n";
                for(int h=0; h<V.size(); h++) cout<<V[h]<<" ";
                cout<<"\n";
            }*/
            apend(V);
        }
    }
}

#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
int I=10,p[1009],pi,dis[39][1009],U;
int MS[1009],VE[1009];
vector <int> vv[1009],R;
int twotodec(vector <int> V){
    int qw=0,we=1;
    for(int h=0; h<V.size(); h++){
        qw+=we*V[h];
        we*=2;
    }
    return qw;
}
vector <int> tothree(int q){
    vector <int> V;
    while(q>0){
        V.push_back(q%3);
        q/=3;
    }
    return V;
}
void DFS(int q, int w){
    if(w!=-1){pi++;p[pi]=q;}
    MS[q]=w;
    for(vector <int>::iterator it=vv[q].begin(); it!=vv[q].end(); it++){
        if((*it)==w) continue;
        DFS((*it),q);
    }
}
void DFS2(int q, int w){
    if(w!=-1){
        dis[U][q]=dis[U][w]+VE[q];
    }
    for(vector <int>::iterator it=vv[q].begin(); it!=vv[q].end(); it++){
        if((*it)==w) continue;
        DFS2((*it),q);
    }
}
void decode(int nv, int nh) {
/*   int a = decode_bit();
   int b = decode_bit();
   hops(0,0,0);
   hops(1,2,3);*/
   int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
   vector <int> V;
   a=nv;H=nh;
   for(i=1; i<a; i++){
        V.clear();
        for(j=0; j<I; j++){
            V.push_back(decode_bit());
        }
        c=twotodec(V);
        vv[c].push_back(i);vv[i].push_back(c);
        //cout<<c<<" "<<i<<"\n";
   }
   for(i=0; i<a; i++){
        sort(vv[i].begin(),vv[i].end());
   }
   for(i=0; i<H; i++){
        V.clear();
        for(j=0; j<I; j++){
            V.push_back(decode_bit());
        }
        dis[i][0]=twotodec(V);pi=0;
        //cout<<"dis["<<i<<"][0]="<<dis[i][0]<<"\n";
        DFS(0,-1);
        R.clear();
        int QW=(a-1)/17;
        if((a-1)%17!=0) QW++;
        QW*=27;
        for(j=0; j<QW; j++) R.push_back(decode_bit());
        int id=1;
        for(j=0; j<R.size(); j+=27){
            V.clear();
            int qw=R.size();
            for(jj=j; jj<min(j+27,qw); jj++) V.push_back(R[jj]);
            zx=twotodec(V);
            V=tothree(zx);
            while(V.size()<17) V.push_back(0);
            for(ii=id; ii<min(id+17,a); ii++){
                VE[/*ii*/p[ii]]=V[ii-id]-1;
            }
            id+=17;
        }
        /*cout<<i<<"::\n";
        for(j=1; j<=pi; j++) cout<<p[j]<<" ";
        cout<<"\n";
        for(j=1; j<=a; j++) cout<<VE[j]<<" ";
        cout<<"\n";*/
        U=i;
        DFS2(0,-1);
   }
   for(i=0; i<H; i++){
        for(j=0; j<a; j++){
            hops(i,j,dis[i][j]);
            //cout<<i<<" "<<j<<": "<<dis[i][j]<<"\n";
        }
   }
}

Compilation message

encoder.cpp: In function 'std::vector<int> totwo(int)':
encoder.cpp:48:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     while(V.size()<J) V.push_back(0);
      |           ~~~~~~~~^~
encoder.cpp: In function 'int threetodec(std::vector<int>)':
encoder.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int h=0; h<V.size(); h++){
      |                  ~^~~~~~~~~
encoder.cpp: In function 'void apend(std::vector<int>)':
encoder.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int j=0; j<V.size(); j++) encode_bit(V[j]);
      |                  ~^~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(j=0; j<L.size(); j+=17){
      |                  ~^~~~~~~~~
encoder.cpp:67:15: warning: unused variable 'd' [-Wunused-variable]
   67 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |               ^
encoder.cpp:67:17: warning: unused variable 'e' [-Wunused-variable]
   67 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                 ^
encoder.cpp:67:23: warning: unused variable 'ii' [-Wunused-variable]
   67 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                       ^~
encoder.cpp:67:29: warning: unused variable 'zx' [-Wunused-variable]
   67 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                             ^~
encoder.cpp:67:32: warning: unused variable 'xc' [-Wunused-variable]
   67 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                                ^~

decoder.cpp: In function 'int twotodec(std::vector<int>)':
decoder.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int h=0; h<V.size(); h++){
      |                  ~^~~~~~~~~
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(j=0; j<R.size(); j+=27){
      |                  ~^~~~~~~~~
decoder.cpp:46:10: warning: unused variable 'b' [-Wunused-variable]
   46 |    int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
      |          ^
decoder.cpp:46:14: warning: unused variable 'd' [-Wunused-variable]
   46 |    int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
      |              ^
decoder.cpp:46:16: warning: unused variable 'e' [-Wunused-variable]
   46 |    int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
      |                ^
decoder.cpp:46:31: warning: unused variable 'xc' [-Wunused-variable]
   46 |    int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
      |                               ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 12492 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Correct 24 ms 5604 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 22 ms 6000 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 24 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 36 ms 6432 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 20 ms 5764 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 26 ms 5888 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5768 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 28 ms 6100 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 26 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 53 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 25 ms 5820 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 25 ms 5972 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 59 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 36 ms 6636 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 49 ms 6756 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 34 ms 6292 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 72 ms 7148 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 68 ms 7312 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 65 ms 6620 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 61 ms 7644 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 12492 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Correct 24 ms 5604 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 22 ms 6000 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 24 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 36 ms 6432 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 20 ms 5764 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 26 ms 5888 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5768 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 28 ms 6100 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 26 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 53 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 25 ms 5820 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 25 ms 5972 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 59 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 36 ms 6636 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 49 ms 6756 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 34 ms 6292 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 72 ms 7148 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 68 ms 7312 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 65 ms 6620 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 61 ms 7644 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 12492 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Correct 24 ms 5604 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 22 ms 6000 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 24 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 36 ms 6432 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 20 ms 5764 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 26 ms 5888 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5768 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 28 ms 6100 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 26 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 53 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 25 ms 5820 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 25 ms 5972 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 59 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 36 ms 6636 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 49 ms 6756 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 34 ms 6292 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 72 ms 7148 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 68 ms 7312 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 65 ms 6620 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 61 ms 7644 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 12492 KB Output is correct - 67698 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Correct 24 ms 5604 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 3 ms 4608 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 22 ms 6000 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 24 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 36 ms 6432 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 20 ms 5764 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 26 ms 5888 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5768 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 28 ms 6100 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 26 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 53 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 25 ms 5820 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 25 ms 5972 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 59 ms 6596 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 36 ms 6636 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 49 ms 6756 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 34 ms 6292 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 72 ms 7148 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 68 ms 7312 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 65 ms 6620 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 61 ms 7644 KB Output is correct - 67698 call(s) of encode_bit()