oj.uz

Submission #598399

# Submission time Handle Problem Language Result Execution time Memory
598399 2022-07-18T08:49:26 Z mosiashvililuka Saveit (IOI10_saveit) C++14
100 / 100
 232 ms 12468 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
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;
    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){
    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);
    }
    for(i=0; i<H; i++){
        V=totwo(DIS[i][0]);
        apend(V);
        O=i;L.clear();
        dfs(0,-1);
        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]);
            }
            c=threetodec(V);
            V=totwo(c);
            while(V.size()<27) V.push_back(0);
            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,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);
   }
   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;
        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;
        }
        U=i;
        DFS2(0,-1);
   }
   for(i=0; i<H; i++){
        for(j=0; j<a; j++){
            hops(i,j,dis[i][j]);
        }
   }
}

Compilation message

encoder.cpp: In function 'std::vector<int> totwo(int)':
encoder.cpp:43:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     while(V.size()<J) V.push_back(0);
      |           ~~~~~~~~^~
encoder.cpp: In function 'int threetodec(std::vector<int>)':
encoder.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int h=0; h<V.size(); h++){
      |                  ~^~~~~~~~~
encoder.cpp: In function 'void apend(std::vector<int>)':
encoder.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     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:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(j=0; j<L.size(); j+=17){
      |                  ~^~~~~~~~~
encoder.cpp:59:15: warning: unused variable 'd' [-Wunused-variable]
   59 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |               ^
encoder.cpp:59:17: warning: unused variable 'e' [-Wunused-variable]
   59 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                 ^
encoder.cpp:59:23: warning: unused variable 'ii' [-Wunused-variable]
   59 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                       ^~
encoder.cpp:59:29: warning: unused variable 'zx' [-Wunused-variable]
   59 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                             ^~
encoder.cpp:59:32: warning: unused variable 'xc' [-Wunused-variable]
   59 |     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:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(j=0; j<R.size(); j+=27){
      |                  ~^~~~~~~~~
decoder.cpp:42:10: warning: unused variable 'b' [-Wunused-variable]
   42 |    int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
      |          ^
decoder.cpp:42:14: warning: unused variable 'd' [-Wunused-variable]
   42 |    int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
      |              ^
decoder.cpp:42:16: warning: unused variable 'e' [-Wunused-variable]
   42 |    int a,b,c,d,e,i,j,ii,jj,zx,xc,H;
      |                ^
decoder.cpp:42:31: warning: unused variable 'xc' [-Wunused-variable]
   42 |    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 232 ms 12468 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 20 ms 5872 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 28 ms 5880 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 28 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 65 ms 6468 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 23 ms 5756 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 25 ms 6020 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 27 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 23 ms 5872 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 51 ms 6832 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 27 ms 5804 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 26 ms 6088 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 43 ms 6488 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 46 ms 6444 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 46 ms 6728 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 35 ms 6420 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 76 ms 7188 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 66 ms 7376 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 49 ms 6680 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 95 ms 7552 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 12468 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 20 ms 5872 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 28 ms 5880 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 28 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 65 ms 6468 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 23 ms 5756 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 25 ms 6020 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 27 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 23 ms 5872 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 51 ms 6832 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 27 ms 5804 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 26 ms 6088 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 43 ms 6488 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 46 ms 6444 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 46 ms 6728 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 35 ms 6420 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 76 ms 7188 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 66 ms 7376 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 49 ms 6680 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 95 ms 7552 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 12468 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 20 ms 5872 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 28 ms 5880 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 28 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 65 ms 6468 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 23 ms 5756 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 25 ms 6020 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 27 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 23 ms 5872 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 51 ms 6832 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 27 ms 5804 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 26 ms 6088 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 43 ms 6488 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 46 ms 6444 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 46 ms 6728 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 35 ms 6420 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 76 ms 7188 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 66 ms 7376 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 49 ms 6680 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 95 ms 7552 KB Output is correct - 67698 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 12468 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 20 ms 5872 KB Output is correct - 60866 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 225 call(s) of encode_bit()
5 Correct 28 ms 5880 KB Output is correct - 60866 call(s) of encode_bit()
6 Correct 28 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
7 Correct 65 ms 6468 KB Output is correct - 67698 call(s) of encode_bit()
8 Correct 23 ms 5756 KB Output is correct - 65364 call(s) of encode_bit()
9 Correct 25 ms 6020 KB Output is correct - 67698 call(s) of encode_bit()
10 Correct 28 ms 5780 KB Output is correct - 67698 call(s) of encode_bit()
11 Correct 27 ms 5996 KB Output is correct - 67698 call(s) of encode_bit()
12 Correct 23 ms 5872 KB Output is correct - 67698 call(s) of encode_bit()
13 Correct 51 ms 6832 KB Output is correct - 67698 call(s) of encode_bit()
14 Correct 27 ms 5804 KB Output is correct - 67698 call(s) of encode_bit()
15 Correct 26 ms 6088 KB Output is correct - 67698 call(s) of encode_bit()
16 Correct 43 ms 6488 KB Output is correct - 67698 call(s) of encode_bit()
17 Correct 46 ms 6444 KB Output is correct - 67698 call(s) of encode_bit()
18 Correct 46 ms 6728 KB Output is correct - 67698 call(s) of encode_bit()
19 Correct 35 ms 6420 KB Output is correct - 67698 call(s) of encode_bit()
20 Correct 76 ms 7188 KB Output is correct - 67698 call(s) of encode_bit()
21 Correct 66 ms 7376 KB Output is correct - 67698 call(s) of encode_bit()
22 Correct 49 ms 6680 KB Output is correct - 67698 call(s) of encode_bit()
23 Correct 95 ms 7552 KB Output is correct - 67698 call(s) of encode_bit()