oj.uz

Submission #566817

# Submission time Handle Problem Language Result Execution time Memory
566817 2022-05-22T22:02:38 Z Uzouf Saveit (IOI10_saveit) C++14
100 / 100
 208 ms 18972 KB 
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "encoder.h"
 
void encode(int n,int h,int p,int a[],int b[]) {
  
  vector<vector<int> > v(n+5);
    int dis[n+5][n+5];

    for (int i=0;i<n+5;i++) {
      for (int j=0;j<n+5;j++) {
        dis[i][j]=2000;
      }
      dis[i][i]=0;
    }

    for (int i=0;i<p;i++) {
      v[a[i]].push_back(b[i]);
      v[b[i]].push_back(a[i]);
      dis[a[i]][b[i]]=dis[b[i]][a[i]]=1;
    }

    int par[n+5];
    for (int i=0;i<n+5;i++) par[i]=i;
    queue<int> q;
    q.push(0); par[0]=-1;

    while (!q.empty()) {
      int i=q.front();
      q.pop();
      for (int j:v[i]) {
        if (par[j]==j) {
          par[j]=i; q.push(j);
        }
      }
    }
    //tree:
    for (int i=0;i<n;i++) {
      if (par[i]==-1) par[i]=i;
      for (int pp=0;pp<10;pp++) {
        if (((1<<pp)&par[i])==0) encode_bit(0);
        else encode_bit(1);
      }
    }


    for (int hub=1;hub<h;hub++) {
      //cout<<hub<<":"<<endl;
      int dis[n+5];
      bool vis[n+5];
      for (int i=0;i<n+5;i++) {
        vis[i]=false;
      }
      queue<int> q;
      q.push(hub); dis[hub]=0; vis[hub]=true;

      while (!q.empty()) {
        int i=q.front();
        q.pop();
        for (int j:v[i]) {
          if (!vis[j]) {
            vis[j]=true; dis[j]=dis[i]+1; q.push(j);
          }
        }
      }

      string ss;
      for (int i=0;i<n;i++) {
        int nm=dis[i]-dis[par[i]];
        if (nm==0) ss+='0';
        else if (nm==1) ss+='1';
        else ss+='2';

        if (ss.size()==3) {
          int lol=((ss[0]-'0')*9)+((ss[1]-'0')*3)+(ss[2]-'0');
          //if (hub==2) cout<<ss<<' '<<lol<<endl;
          for (int j=4;j>=0;j--) {
            int bb=1;
            if ((lol&(1<<j))==0) bb=0;
            //if (hub==2) cout<<bb<<' ';
            encode_bit(bb);
          }
          ss=""; //cout<<endl;
        }
      }

      if (ss.size()==0) continue;
      int lol=((ss[0]-'0')*9);
      if (ss.size()==2) lol+=((ss[1]-'0')*3);
      while (ss.size()<3) ss+='0';
      //if (hub==2) cout<<ss<<' '<<lol<<endl;
      for (int j=4;j>=0;j--) {
        int bb=1;
        if ((lol&(1<<j))==0) bb=0;
        //if (hub==2) cout<<bb<<' ';
        encode_bit(bb);
      }//cout<<endl<<endl;

    }
  
}
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "encoder.h"

void decode(int n,int h) {
  vector<vector<int> > v(n+5);
  bool done[n+5][n+5];
  int par[n+5];
  for (int i=0;i<n;i++) {
    int tmp=0;
    for (int p=0;p<10;p++) {
      tmp+=(decode_bit()*(1<<p));
    }
    par[i]=tmp;
    v[i].push_back(tmp); v[tmp].push_back(i);
  }

  for (int hub=0;hub<h;hub++) {
    int dis[n+5][n+5];
    memset(done,false,sizeof done);

    if (hub>0) {
      string ss;
      int tt=n/3;
      if (n%3!=0) tt++;
      int i=-1;
      while (tt--) {
        for (int i5=0;i5<5;i5++) ss+=(decode_bit()+'0');

        i+=3;
        int dec=0,ii=0;
        for (int j=4;j>=0;j--) {
          int rn=ss[ii]-'0';
          int cl=rn*(1<<j);
          dec+=cl; ii++;
        }
        //if (hub==1) cout<<ss<<' '<<dec<<endl;

        int l[3];
        l[0]=0; l[1]=0; l[2]=0;
        if (dec-9>=0) {dec-=9; l[0]=1; if (dec-9>=0) {dec-=9; l[0]=2;} }
        if (dec-3>=0) {dec-=3; l[1]=1; if (dec-3>=0) {dec-=3; l[1]=2;} }
        if (dec-1>=0) {dec-=1; l[2]=1; if (dec-1>=0) {dec-=9; l[2]=2;} }

        //if (hub==2) cout<<i<<"  "<<l[0]<<' '<<l[1]<<' '<<l[2]<<endl;

        int indx=2;
        for (int j=i;j>=i-2;j--) {
          if (j>n-1 || done[j][par[j]]) {indx--; continue;}
          done[j][par[j]]=true; done[par[j]][j]=true;
          if (l[indx]==0) {
            dis[j][par[j]]=0; dis[par[j]][j]=0;
          }
          else if (l[indx]==1) {
            dis[par[j]][j]=1; dis[j][par[j]]=-1;
          }
          else {
            dis[j][par[j]]=1; dis[par[j]][j]=-1;
          }
          //if (hub==2) cout<<j<<' '<<par[j]<<' '<<dis[j][par[j]]<<' '<<dis[par[j]][j]<<endl;
          indx--;
        }
        ss="";

      }

    }
    else {
      for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) dis[i][j]=1;
      }
    }

    queue<int> q;
    int ans[n+5];
    bool vis[n+5];
    memset(vis,false,sizeof vis);
    ans[hub]=0; q.push(hub); vis[hub]=true;

    while (!q.empty()) {
      int i=q.front();
      q.pop();
      hops(hub,i,ans[i]);

      for (int j:v[i]) {
        if (!vis[j]) {
          q.push(j); ans[j]=ans[i]+dis[i][j]; vis[j]=true;
        }
      }
    }

  }

}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 18972 KB Output is correct - 68450 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 12580 KB Output is correct - 61500 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 39 ms 12684 KB Output is correct - 61500 call(s) of encode_bit()
6 Correct 38 ms 14468 KB Output is correct - 68450 call(s) of encode_bit()
7 Correct 43 ms 14832 KB Output is correct - 68450 call(s) of encode_bit()
8 Correct 27 ms 13572 KB Output is correct - 65785 call(s) of encode_bit()
9 Correct 28 ms 14200 KB Output is correct - 68450 call(s) of encode_bit()
10 Correct 28 ms 14192 KB Output is correct - 68450 call(s) of encode_bit()
11 Correct 32 ms 14524 KB Output is correct - 68450 call(s) of encode_bit()
12 Correct 32 ms 14204 KB Output is correct - 68450 call(s) of encode_bit()
13 Correct 58 ms 14860 KB Output is correct - 68450 call(s) of encode_bit()
14 Correct 34 ms 14208 KB Output is correct - 68450 call(s) of encode_bit()
15 Correct 38 ms 14336 KB Output is correct - 68450 call(s) of encode_bit()
16 Correct 61 ms 14696 KB Output is correct - 68450 call(s) of encode_bit()
17 Correct 55 ms 14684 KB Output is correct - 68450 call(s) of encode_bit()
18 Correct 58 ms 14872 KB Output is correct - 68450 call(s) of encode_bit()
19 Correct 40 ms 14648 KB Output is correct - 68450 call(s) of encode_bit()
20 Correct 66 ms 15276 KB Output is correct - 68450 call(s) of encode_bit()
21 Correct 83 ms 15372 KB Output is correct - 68450 call(s) of encode_bit()
22 Correct 68 ms 14852 KB Output is correct - 68450 call(s) of encode_bit()
23 Correct 90 ms 15660 KB Output is correct - 68450 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 18972 KB Output is correct - 68450 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 12580 KB Output is correct - 61500 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 39 ms 12684 KB Output is correct - 61500 call(s) of encode_bit()
6 Correct 38 ms 14468 KB Output is correct - 68450 call(s) of encode_bit()
7 Correct 43 ms 14832 KB Output is correct - 68450 call(s) of encode_bit()
8 Correct 27 ms 13572 KB Output is correct - 65785 call(s) of encode_bit()
9 Correct 28 ms 14200 KB Output is correct - 68450 call(s) of encode_bit()
10 Correct 28 ms 14192 KB Output is correct - 68450 call(s) of encode_bit()
11 Correct 32 ms 14524 KB Output is correct - 68450 call(s) of encode_bit()
12 Correct 32 ms 14204 KB Output is correct - 68450 call(s) of encode_bit()
13 Correct 58 ms 14860 KB Output is correct - 68450 call(s) of encode_bit()
14 Correct 34 ms 14208 KB Output is correct - 68450 call(s) of encode_bit()
15 Correct 38 ms 14336 KB Output is correct - 68450 call(s) of encode_bit()
16 Correct 61 ms 14696 KB Output is correct - 68450 call(s) of encode_bit()
17 Correct 55 ms 14684 KB Output is correct - 68450 call(s) of encode_bit()
18 Correct 58 ms 14872 KB Output is correct - 68450 call(s) of encode_bit()
19 Correct 40 ms 14648 KB Output is correct - 68450 call(s) of encode_bit()
20 Correct 66 ms 15276 KB Output is correct - 68450 call(s) of encode_bit()
21 Correct 83 ms 15372 KB Output is correct - 68450 call(s) of encode_bit()
22 Correct 68 ms 14852 KB Output is correct - 68450 call(s) of encode_bit()
23 Correct 90 ms 15660 KB Output is correct - 68450 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 18972 KB Output is correct - 68450 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 12580 KB Output is correct - 61500 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 39 ms 12684 KB Output is correct - 61500 call(s) of encode_bit()
6 Correct 38 ms 14468 KB Output is correct - 68450 call(s) of encode_bit()
7 Correct 43 ms 14832 KB Output is correct - 68450 call(s) of encode_bit()
8 Correct 27 ms 13572 KB Output is correct - 65785 call(s) of encode_bit()
9 Correct 28 ms 14200 KB Output is correct - 68450 call(s) of encode_bit()
10 Correct 28 ms 14192 KB Output is correct - 68450 call(s) of encode_bit()
11 Correct 32 ms 14524 KB Output is correct - 68450 call(s) of encode_bit()
12 Correct 32 ms 14204 KB Output is correct - 68450 call(s) of encode_bit()
13 Correct 58 ms 14860 KB Output is correct - 68450 call(s) of encode_bit()
14 Correct 34 ms 14208 KB Output is correct - 68450 call(s) of encode_bit()
15 Correct 38 ms 14336 KB Output is correct - 68450 call(s) of encode_bit()
16 Correct 61 ms 14696 KB Output is correct - 68450 call(s) of encode_bit()
17 Correct 55 ms 14684 KB Output is correct - 68450 call(s) of encode_bit()
18 Correct 58 ms 14872 KB Output is correct - 68450 call(s) of encode_bit()
19 Correct 40 ms 14648 KB Output is correct - 68450 call(s) of encode_bit()
20 Correct 66 ms 15276 KB Output is correct - 68450 call(s) of encode_bit()
21 Correct 83 ms 15372 KB Output is correct - 68450 call(s) of encode_bit()
22 Correct 68 ms 14852 KB Output is correct - 68450 call(s) of encode_bit()
23 Correct 90 ms 15660 KB Output is correct - 68450 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 18972 KB Output is correct - 68450 call(s) of encode_bit()
2 Correct 2 ms 4608 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 12580 KB Output is correct - 61500 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 39 ms 12684 KB Output is correct - 61500 call(s) of encode_bit()
6 Correct 38 ms 14468 KB Output is correct - 68450 call(s) of encode_bit()
7 Correct 43 ms 14832 KB Output is correct - 68450 call(s) of encode_bit()
8 Correct 27 ms 13572 KB Output is correct - 65785 call(s) of encode_bit()
9 Correct 28 ms 14200 KB Output is correct - 68450 call(s) of encode_bit()
10 Correct 28 ms 14192 KB Output is correct - 68450 call(s) of encode_bit()
11 Correct 32 ms 14524 KB Output is correct - 68450 call(s) of encode_bit()
12 Correct 32 ms 14204 KB Output is correct - 68450 call(s) of encode_bit()
13 Correct 58 ms 14860 KB Output is correct - 68450 call(s) of encode_bit()
14 Correct 34 ms 14208 KB Output is correct - 68450 call(s) of encode_bit()
15 Correct 38 ms 14336 KB Output is correct - 68450 call(s) of encode_bit()
16 Correct 61 ms 14696 KB Output is correct - 68450 call(s) of encode_bit()
17 Correct 55 ms 14684 KB Output is correct - 68450 call(s) of encode_bit()
18 Correct 58 ms 14872 KB Output is correct - 68450 call(s) of encode_bit()
19 Correct 40 ms 14648 KB Output is correct - 68450 call(s) of encode_bit()
20 Correct 66 ms 15276 KB Output is correct - 68450 call(s) of encode_bit()
21 Correct 83 ms 15372 KB Output is correct - 68450 call(s) of encode_bit()
22 Correct 68 ms 14852 KB Output is correct - 68450 call(s) of encode_bit()
23 Correct 90 ms 15660 KB Output is correct - 68450 call(s) of encode_bit()