oj.uz

Submission #598254

# Submission time Handle Problem Language Result Execution time Memory
598254 2022-07-17T21:05:18 Z mosiashvililuka Saveit (IOI10_saveit) C++14
0 / 100
 321 ms 12488 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);
    }
    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";*/
        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 = 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 '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:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(j=0; j<L.size(); j+=17){
      |                  ~^~~~~~~~~
encoder.cpp:62:15: warning: unused variable 'd' [-Wunused-variable]
   62 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |               ^
encoder.cpp:62:17: warning: unused variable 'e' [-Wunused-variable]
   62 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                 ^
encoder.cpp:62:23: warning: unused variable 'ii' [-Wunused-variable]
   62 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                       ^~
encoder.cpp:62:29: warning: unused variable 'zx' [-Wunused-variable]
   62 |     int a,b,c,d,e,i,j,ii,jj,zx,xc,H,dis[1009];
      |                             ^~
encoder.cpp:62:32: warning: unused variable 'xc' [-Wunused-variable]
   62 |     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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 12488 KB wrong parameter
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Incorrect 18 ms 5536 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 225 call(s) of encode_bit()
5 Incorrect 24 ms 5920 KB wrong parameter
6 Incorrect 29 ms 6040 KB wrong parameter
7 Incorrect 52 ms 6508 KB wrong parameter
8 Incorrect 20 ms 5652 KB wrong parameter
9 Incorrect 25 ms 5880 KB wrong parameter
10 Incorrect 24 ms 5736 KB wrong parameter
11 Incorrect 27 ms 6000 KB wrong parameter
12 Incorrect 19 ms 5832 KB wrong parameter
13 Incorrect 60 ms 6648 KB wrong parameter
14 Incorrect 23 ms 5896 KB wrong parameter
15 Incorrect 26 ms 5820 KB wrong parameter
16 Incorrect 42 ms 6492 KB wrong parameter
17 Incorrect 40 ms 6372 KB wrong parameter
18 Incorrect 51 ms 6816 KB wrong parameter
19 Incorrect 32 ms 6268 KB wrong parameter
20 Incorrect 81 ms 7028 KB wrong parameter
21 Incorrect 57 ms 7288 KB wrong parameter
22 Incorrect 65 ms 6548 KB wrong parameter
23 Incorrect 76 ms 7680 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 12488 KB wrong parameter
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Incorrect 18 ms 5536 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 225 call(s) of encode_bit()
5 Incorrect 24 ms 5920 KB wrong parameter
6 Incorrect 29 ms 6040 KB wrong parameter
7 Incorrect 52 ms 6508 KB wrong parameter
8 Incorrect 20 ms 5652 KB wrong parameter
9 Incorrect 25 ms 5880 KB wrong parameter
10 Incorrect 24 ms 5736 KB wrong parameter
11 Incorrect 27 ms 6000 KB wrong parameter
12 Incorrect 19 ms 5832 KB wrong parameter
13 Incorrect 60 ms 6648 KB wrong parameter
14 Incorrect 23 ms 5896 KB wrong parameter
15 Incorrect 26 ms 5820 KB wrong parameter
16 Incorrect 42 ms 6492 KB wrong parameter
17 Incorrect 40 ms 6372 KB wrong parameter
18 Incorrect 51 ms 6816 KB wrong parameter
19 Incorrect 32 ms 6268 KB wrong parameter
20 Incorrect 81 ms 7028 KB wrong parameter
21 Incorrect 57 ms 7288 KB wrong parameter
22 Incorrect 65 ms 6548 KB wrong parameter
23 Incorrect 76 ms 7680 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 12488 KB wrong parameter
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Incorrect 18 ms 5536 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 225 call(s) of encode_bit()
5 Incorrect 24 ms 5920 KB wrong parameter
6 Incorrect 29 ms 6040 KB wrong parameter
7 Incorrect 52 ms 6508 KB wrong parameter
8 Incorrect 20 ms 5652 KB wrong parameter
9 Incorrect 25 ms 5880 KB wrong parameter
10 Incorrect 24 ms 5736 KB wrong parameter
11 Incorrect 27 ms 6000 KB wrong parameter
12 Incorrect 19 ms 5832 KB wrong parameter
13 Incorrect 60 ms 6648 KB wrong parameter
14 Incorrect 23 ms 5896 KB wrong parameter
15 Incorrect 26 ms 5820 KB wrong parameter
16 Incorrect 42 ms 6492 KB wrong parameter
17 Incorrect 40 ms 6372 KB wrong parameter
18 Incorrect 51 ms 6816 KB wrong parameter
19 Incorrect 32 ms 6268 KB wrong parameter
20 Incorrect 81 ms 7028 KB wrong parameter
21 Incorrect 57 ms 7288 KB wrong parameter
22 Incorrect 65 ms 6548 KB wrong parameter
23 Incorrect 76 ms 7680 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 12488 KB wrong parameter
2 Correct 2 ms 4608 KB Output is correct - 151 call(s) of encode_bit()
3 Incorrect 18 ms 5536 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 225 call(s) of encode_bit()
5 Incorrect 24 ms 5920 KB wrong parameter
6 Incorrect 29 ms 6040 KB wrong parameter
7 Incorrect 52 ms 6508 KB wrong parameter
8 Incorrect 20 ms 5652 KB wrong parameter
9 Incorrect 25 ms 5880 KB wrong parameter
10 Incorrect 24 ms 5736 KB wrong parameter
11 Incorrect 27 ms 6000 KB wrong parameter
12 Incorrect 19 ms 5832 KB wrong parameter
13 Incorrect 60 ms 6648 KB wrong parameter
14 Incorrect 23 ms 5896 KB wrong parameter
15 Incorrect 26 ms 5820 KB wrong parameter
16 Incorrect 42 ms 6492 KB wrong parameter
17 Incorrect 40 ms 6372 KB wrong parameter
18 Incorrect 51 ms 6816 KB wrong parameter
19 Incorrect 32 ms 6268 KB wrong parameter
20 Incorrect 81 ms 7028 KB wrong parameter
21 Incorrect 57 ms 7288 KB wrong parameter
22 Incorrect 65 ms 6548 KB wrong parameter
23 Incorrect 76 ms 7680 KB wrong parameter