oj.uz

Submission #771556

# Submission time Handle Problem Language Result Execution time Memory
771556 2023-07-03T06:21:05 Z canadavid1 Saveit (IOI10_saveit) C++14
100 / 100
 316 ms 14336 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
void encode_number(int n,int N, int H)
{
  for(int i = 1<<9; i > 0; i>>=1)
  {
    encode_bit((n&i)>0);
  }
}

int count1 = 0;
int count0 = 0;
int countm1 = 0;

void encode(int N, int H, int P, int *A, int *B)
{
  vector<vector<int>> neigh(N);
  for(int i = 0; i < P; i++)
  {
    neigh[A[i]].push_back(B[i]);
    neigh[B[i]].push_back(A[i]);
  }
  // BFS from all H
  vector<vector<int>> distance(H,vector<int>(N,INT_MAX));
  for(int h = 0; h < H; h++)
  {
    queue<pair<int,int>> q;
    q.push({h,0});
    while(q.size())
    {
      auto v = q.front();q.pop();
      if(distance[h][v.first]!=INT_MAX) continue;
      distance[h][v.first] = v.second;
      for(auto i : neigh[v.first]) q.push({i,v.second+1});
    }
  }
  vector<int> treep(N,-1);
  queue<int> q;
  q.push(0);
  while(q.size())
  {
    auto v = q.front();q.pop();
    for(auto i : neigh[v]) 
    {
      if(treep[i]!=-1) continue;
      treep[i] = v;
      q.push(i);
    }
  }


  for(int i = 1; i < N; i++)
  {
    int p = treep[i];
    encode_number(p,N,H);
  }
  int count[3] = {0,0,0};
  for(int i = 1; i < N; i++)
  {
    int p = treep[i];
    for(int h=1; h < H; h++)
      count[distance[h][i]-distance[h][p]+1]++;
  }
  int v[3]{0,1,-1};
  if(count[0] > count[1])
  {
    v[0] = 1; v[1] = 0;
    encode_bit(1);
  } else encode_bit(0);
  for(int i = 1; i < N; i++)
  {
    int p = treep[i];
    for(int h=1; h < H; h++)
    {
      int d = distance[h][i]-distance[h][p];// mostly 1, sometimes -1, rarely 0
      
      if(d==v[0]) encode_bit(1);
      if(d==v[1])
        encode_bit(0),encode_bit(1);
      if(d==v[2])
        encode_bit(0),encode_bit(0);
      

    }
  }
  //cout << "counts = " << count1 << " " << count0 << " " << countm1 << "\n";
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
int decode_number(int N,int H)
{
    int o=0;
    for(int i = 0; i < 10; i++) o = (o<<1)+decode_bit();
    return o;
}

void decode(int N, int H) {
    vector<int> treep(N,-1);
    vector<vector<int>> treec(N);
    vector<vector<int>> distance(N,vector<int>(H,INT_MAX));
    vector<vector<int>> delta(N,vector<int>(H,0));
    for(int i = 0; i < H; i++) distance[i][i] = 0;
    for(int i = 1; i < N; i++)
    {
        treep[i] = decode_number(N, H);
        treec[treep[i]].push_back(i);
    }
    int v[3]{0,1,-1};
    if(decode_bit())
    {
        v[0] = 1; v[1] = 0;
    }
    for(int i = 1; i < N; i++)
    {
        delta[i][0] = 1;
        for(int h = 1; h < H; h++)
        {
            if(decode_bit())
            {
                delta[i][h] = v[0];
                continue;
            }
            if(decode_bit())
            {
                delta[i][h] = v[1];
            }
            else
            {
                delta[i][h] = v[2];
            }
        }
    }
    for(int h = 1; h < H; h++)
    {
        int c = 0;
        int t = h;
        while(t!=0)
        {
            c += delta[t][h];
            t = treep[t];
        }
        distance[0][h] = -c;
    }
    queue<int> q;
    for(auto i : treec[0]) q.push(i);
    while(q.size())
    {
        auto v = q.front(); q.pop();
        for(int h = 0; h < H; h++)
        {
            distance[v][h] = distance[treep[v]][h] + delta[v][h];
        }
        for(auto i : treec[v]) q.push(i);
    }
    for(int h = 0; h < H; h++)
        for(int c = 0; c < N; c++)
            hops(h,c,distance[c][h]);
        
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 14336 KB Output is correct - 62914 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 53 call(s) of encode_bit()
3 Correct 19 ms 5704 KB Output is correct - 58902 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 63 call(s) of encode_bit()
5 Correct 27 ms 5856 KB Output is correct - 56289 call(s) of encode_bit()
6 Correct 26 ms 6124 KB Output is correct - 60906 call(s) of encode_bit()
7 Correct 41 ms 6568 KB Output is correct - 50829 call(s) of encode_bit()
8 Correct 15 ms 5752 KB Output is correct - 51272 call(s) of encode_bit()
9 Correct 16 ms 5768 KB Output is correct - 49157 call(s) of encode_bit()
10 Correct 18 ms 5808 KB Output is correct - 48796 call(s) of encode_bit()
11 Correct 23 ms 6016 KB Output is correct - 52513 call(s) of encode_bit()
12 Correct 16 ms 5800 KB Output is correct - 54633 call(s) of encode_bit()
13 Correct 63 ms 6880 KB Output is correct - 58327 call(s) of encode_bit()
14 Correct 20 ms 5856 KB Output is correct - 57622 call(s) of encode_bit()
15 Correct 20 ms 5840 KB Output is correct - 63703 call(s) of encode_bit()
16 Correct 55 ms 6600 KB Output is correct - 62929 call(s) of encode_bit()
17 Correct 52 ms 6456 KB Output is correct - 61727 call(s) of encode_bit()
18 Correct 60 ms 6944 KB Output is correct - 69824 call(s) of encode_bit()
19 Correct 40 ms 6424 KB Output is correct - 66844 call(s) of encode_bit()
20 Correct 87 ms 7396 KB Output is correct - 63571 call(s) of encode_bit()
21 Correct 111 ms 7768 KB Output is correct - 64321 call(s) of encode_bit()
22 Correct 53 ms 6748 KB Output is correct - 53040 call(s) of encode_bit()
23 Correct 98 ms 7904 KB Output is correct - 56826 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 14336 KB Output is correct - 62914 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 53 call(s) of encode_bit()
3 Correct 19 ms 5704 KB Output is correct - 58902 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 63 call(s) of encode_bit()
5 Correct 27 ms 5856 KB Output is correct - 56289 call(s) of encode_bit()
6 Correct 26 ms 6124 KB Output is correct - 60906 call(s) of encode_bit()
7 Correct 41 ms 6568 KB Output is correct - 50829 call(s) of encode_bit()
8 Correct 15 ms 5752 KB Output is correct - 51272 call(s) of encode_bit()
9 Correct 16 ms 5768 KB Output is correct - 49157 call(s) of encode_bit()
10 Correct 18 ms 5808 KB Output is correct - 48796 call(s) of encode_bit()
11 Correct 23 ms 6016 KB Output is correct - 52513 call(s) of encode_bit()
12 Correct 16 ms 5800 KB Output is correct - 54633 call(s) of encode_bit()
13 Correct 63 ms 6880 KB Output is correct - 58327 call(s) of encode_bit()
14 Correct 20 ms 5856 KB Output is correct - 57622 call(s) of encode_bit()
15 Correct 20 ms 5840 KB Output is correct - 63703 call(s) of encode_bit()
16 Correct 55 ms 6600 KB Output is correct - 62929 call(s) of encode_bit()
17 Correct 52 ms 6456 KB Output is correct - 61727 call(s) of encode_bit()
18 Correct 60 ms 6944 KB Output is correct - 69824 call(s) of encode_bit()
19 Correct 40 ms 6424 KB Output is correct - 66844 call(s) of encode_bit()
20 Correct 87 ms 7396 KB Output is correct - 63571 call(s) of encode_bit()
21 Correct 111 ms 7768 KB Output is correct - 64321 call(s) of encode_bit()
22 Correct 53 ms 6748 KB Output is correct - 53040 call(s) of encode_bit()
23 Correct 98 ms 7904 KB Output is correct - 56826 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 14336 KB Output is correct - 62914 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 53 call(s) of encode_bit()
3 Correct 19 ms 5704 KB Output is correct - 58902 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 63 call(s) of encode_bit()
5 Correct 27 ms 5856 KB Output is correct - 56289 call(s) of encode_bit()
6 Correct 26 ms 6124 KB Output is correct - 60906 call(s) of encode_bit()
7 Correct 41 ms 6568 KB Output is correct - 50829 call(s) of encode_bit()
8 Correct 15 ms 5752 KB Output is correct - 51272 call(s) of encode_bit()
9 Correct 16 ms 5768 KB Output is correct - 49157 call(s) of encode_bit()
10 Correct 18 ms 5808 KB Output is correct - 48796 call(s) of encode_bit()
11 Correct 23 ms 6016 KB Output is correct - 52513 call(s) of encode_bit()
12 Correct 16 ms 5800 KB Output is correct - 54633 call(s) of encode_bit()
13 Correct 63 ms 6880 KB Output is correct - 58327 call(s) of encode_bit()
14 Correct 20 ms 5856 KB Output is correct - 57622 call(s) of encode_bit()
15 Correct 20 ms 5840 KB Output is correct - 63703 call(s) of encode_bit()
16 Correct 55 ms 6600 KB Output is correct - 62929 call(s) of encode_bit()
17 Correct 52 ms 6456 KB Output is correct - 61727 call(s) of encode_bit()
18 Correct 60 ms 6944 KB Output is correct - 69824 call(s) of encode_bit()
19 Correct 40 ms 6424 KB Output is correct - 66844 call(s) of encode_bit()
20 Correct 87 ms 7396 KB Output is correct - 63571 call(s) of encode_bit()
21 Correct 111 ms 7768 KB Output is correct - 64321 call(s) of encode_bit()
22 Correct 53 ms 6748 KB Output is correct - 53040 call(s) of encode_bit()
23 Correct 98 ms 7904 KB Output is correct - 56826 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 14336 KB Output is correct - 62914 call(s) of encode_bit()
2 Correct 2 ms 4476 KB Output is correct - 53 call(s) of encode_bit()
3 Correct 19 ms 5704 KB Output is correct - 58902 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 63 call(s) of encode_bit()
5 Correct 27 ms 5856 KB Output is correct - 56289 call(s) of encode_bit()
6 Correct 26 ms 6124 KB Output is correct - 60906 call(s) of encode_bit()
7 Correct 41 ms 6568 KB Output is correct - 50829 call(s) of encode_bit()
8 Correct 15 ms 5752 KB Output is correct - 51272 call(s) of encode_bit()
9 Correct 16 ms 5768 KB Output is correct - 49157 call(s) of encode_bit()
10 Correct 18 ms 5808 KB Output is correct - 48796 call(s) of encode_bit()
11 Correct 23 ms 6016 KB Output is correct - 52513 call(s) of encode_bit()
12 Correct 16 ms 5800 KB Output is correct - 54633 call(s) of encode_bit()
13 Correct 63 ms 6880 KB Output is correct - 58327 call(s) of encode_bit()
14 Correct 20 ms 5856 KB Output is correct - 57622 call(s) of encode_bit()
15 Correct 20 ms 5840 KB Output is correct - 63703 call(s) of encode_bit()
16 Correct 55 ms 6600 KB Output is correct - 62929 call(s) of encode_bit()
17 Correct 52 ms 6456 KB Output is correct - 61727 call(s) of encode_bit()
18 Correct 60 ms 6944 KB Output is correct - 69824 call(s) of encode_bit()
19 Correct 40 ms 6424 KB Output is correct - 66844 call(s) of encode_bit()
20 Correct 87 ms 7396 KB Output is correct - 63571 call(s) of encode_bit()
21 Correct 111 ms 7768 KB Output is correct - 64321 call(s) of encode_bit()
22 Correct 53 ms 6748 KB Output is correct - 53040 call(s) of encode_bit()
23 Correct 98 ms 7904 KB Output is correct - 56826 call(s) of encode_bit()