oj.uz

Submission #513863

# Submission time Handle Problem Language Result Execution time Memory
513863 2022-01-17T19:26:06 Z jerzyk Saveit (IOI10_saveit) C++14
100 / 100
 319 ms 10724 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
 
typedef long long ll;
using namespace std;
const int N = 1000 + 7;
vector<int>ed[N];
int tab[38][N], wsk[N];
 
ll Return3(int v, int h)
{
  ll w = 0LL, m, pot = 1LL;
  for(int i = 1; i <= h; ++i)
  {
    m = 0LL;
    if(tab[i][v] == tab[i][wsk[v]])
      m = 1LL;
    if(tab[i][v] > tab[i][wsk[v]])
      m = 2LL;
    w += m * pot;
    pot *= 3LL;
  }
  return w;
}

void PrintBits(ll x, int l)
{
  for(int i = 1; i <= l; ++i)
  {
    encode_bit((int)(x % 2LL));
    //cout << x % 2LL;
    x /= 2LL;
  }
}
 
void DFS(int v)
{
  for(int i = 0; i < (int)ed[v].size(); ++i)
  {
    if(wsk[ed[v][i]] == 0)
    {
      wsk[ed[v][i]] = v;
      DFS(ed[v][i]);
    }
  }
}
 
void BFS(int n, int s)
{
  int v;
  queue<int> q;
  for(int i = 1; i <= n; ++i)
    tab[s][i] = N * 2;
  tab[s][s] = 0;
  q.push(s);
  while(q.size() > 0)
  {
    v = q.front();
    q.pop();
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
      if(tab[s][ed[v][i]] > tab[s][v] + 1)
      {
        tab[s][ed[v][i]] = tab[s][v] + 1;
        q.push(ed[v][i]);
      }
    }
  }
}

void encode(int n, int h, int m, int* a, int* b)
{
  for(int i = 0; i < m; ++i)
  {
    ed[a[i] + 1].push_back(b[i] + 1);
    ed[b[i] + 1].push_back(a[i] + 1);
  }
  for(int i = 1; i <= h; ++i)
    BFS(n, i);
  wsk[1] = 1;
  DFS(1);
  for(int i = 2; i <= h; ++i)
    PrintBits(tab[i][1], 10);
  for(int i = 2; i <= n; ++i)
  {
    PrintBits(wsk[i], 10);       
    PrintBits(Return3(i, h), 58);
  }
}

/*
int main()
{
  int n, h, m;
  cin >> n >> m >> h;
  for(int i = 0; i < m; ++i)
  {
    int a, b;
    cin >> a >> b;
    ed[a + 1].push_back(b + 1);
    ed[b + 1].push_back(a + 1);
  }
  for(int i = 1; i <= h; ++i)
    BFS(n, i);
  wsk[1] = 1;
  DFS(1);
  for(int i = 2; i <= h; ++i)
    PrintBits(tab[i][1], 10);
  for(int i = 2; i <= n; ++i)
  {
    PrintBits(wsk[i], 10);
    //cout << i << " " << wsk[i] << " " << tab[1][i] << " " << Return3(i, h) << "\n";  
    PrintBits(Return3(i, h), 58);
  }
  cout << "\n";
  return 0;
}*/
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int N = 1000 + 7;
int odl[37][N], dod[37][N], wsk[N];
vector<int>ed[N];
 
void DFS(int v, int h)
{
   for(int i = 1; i <= h; ++i)
      if(v != 1)
         odl[i][v] = dod[i][v] + odl[i][wsk[v]];
    for(int i = 0; i < (int)ed[v].size(); ++i)
      DFS(ed[v][i], h);
}
 
void Dod(ll l, int v, int h)
{
   //cout << v << " " << l << "\n";
   for(int i = 1; i <= h; ++i)
   {
      if(l % 3LL == 0LL)
         dod[i][v] = -1;
      if(l % 3LL == 2LL)
         dod[i][v] = 1;
      l /= 3LL;
   }
}
 
ll ReadBits(int n)
{
   ll w = 0LL, b, pot = 1LL;
   //char z;
   for(int i = 0; i < n; ++i)
   {
      b = decode_bit();
      //cin >> z; b = z - '0';
      w += pot * b;
      pot *= 2LL;
   }
   return w;
}
 
void decode(int n, int h)
{
   for(int i = 2; i <= h; ++i)
     odl[i][1] = ReadBits(10);
   for(int i = 2; i <= n; ++i)
   {
      wsk[i] = ReadBits(10);
      ed[wsk[i]].push_back(i);
      Dod(ReadBits(58), i, h);
   }
   DFS(1, h);
   for(int i = 1; i <= h; ++i)
      for(int j = 1; j <= n; ++j)
         hops(i - 1, j - 1, odl[i][j]);
}

/*
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int n, h;
   cin >> n >> h;
   decode(n, h);

   return 0;
}*/

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 10724 KB Output is correct - 68282 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 292 call(s) of encode_bit()
3 Correct 24 ms 5852 KB Output is correct - 61482 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 312 call(s) of encode_bit()
5 Correct 25 ms 6072 KB Output is correct - 61482 call(s) of encode_bit()
6 Correct 27 ms 6112 KB Output is correct - 68282 call(s) of encode_bit()
7 Correct 48 ms 6336 KB Output is correct - 68282 call(s) of encode_bit()
8 Correct 19 ms 5904 KB Output is correct - 65630 call(s) of encode_bit()
9 Correct 22 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
10 Correct 20 ms 5868 KB Output is correct - 68282 call(s) of encode_bit()
11 Correct 26 ms 5984 KB Output is correct - 68282 call(s) of encode_bit()
12 Correct 20 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
13 Correct 48 ms 6444 KB Output is correct - 68282 call(s) of encode_bit()
14 Correct 26 ms 5840 KB Output is correct - 68282 call(s) of encode_bit()
15 Correct 20 ms 5932 KB Output is correct - 68282 call(s) of encode_bit()
16 Correct 49 ms 6448 KB Output is correct - 68282 call(s) of encode_bit()
17 Correct 41 ms 6356 KB Output is correct - 68282 call(s) of encode_bit()
18 Correct 55 ms 6740 KB Output is correct - 68282 call(s) of encode_bit()
19 Correct 38 ms 6068 KB Output is correct - 68282 call(s) of encode_bit()
20 Correct 75 ms 6784 KB Output is correct - 68282 call(s) of encode_bit()
21 Correct 69 ms 6944 KB Output is correct - 68282 call(s) of encode_bit()
22 Correct 48 ms 6516 KB Output is correct - 68282 call(s) of encode_bit()
23 Correct 74 ms 7164 KB Output is correct - 68282 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 10724 KB Output is correct - 68282 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 292 call(s) of encode_bit()
3 Correct 24 ms 5852 KB Output is correct - 61482 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 312 call(s) of encode_bit()
5 Correct 25 ms 6072 KB Output is correct - 61482 call(s) of encode_bit()
6 Correct 27 ms 6112 KB Output is correct - 68282 call(s) of encode_bit()
7 Correct 48 ms 6336 KB Output is correct - 68282 call(s) of encode_bit()
8 Correct 19 ms 5904 KB Output is correct - 65630 call(s) of encode_bit()
9 Correct 22 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
10 Correct 20 ms 5868 KB Output is correct - 68282 call(s) of encode_bit()
11 Correct 26 ms 5984 KB Output is correct - 68282 call(s) of encode_bit()
12 Correct 20 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
13 Correct 48 ms 6444 KB Output is correct - 68282 call(s) of encode_bit()
14 Correct 26 ms 5840 KB Output is correct - 68282 call(s) of encode_bit()
15 Correct 20 ms 5932 KB Output is correct - 68282 call(s) of encode_bit()
16 Correct 49 ms 6448 KB Output is correct - 68282 call(s) of encode_bit()
17 Correct 41 ms 6356 KB Output is correct - 68282 call(s) of encode_bit()
18 Correct 55 ms 6740 KB Output is correct - 68282 call(s) of encode_bit()
19 Correct 38 ms 6068 KB Output is correct - 68282 call(s) of encode_bit()
20 Correct 75 ms 6784 KB Output is correct - 68282 call(s) of encode_bit()
21 Correct 69 ms 6944 KB Output is correct - 68282 call(s) of encode_bit()
22 Correct 48 ms 6516 KB Output is correct - 68282 call(s) of encode_bit()
23 Correct 74 ms 7164 KB Output is correct - 68282 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 10724 KB Output is correct - 68282 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 292 call(s) of encode_bit()
3 Correct 24 ms 5852 KB Output is correct - 61482 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 312 call(s) of encode_bit()
5 Correct 25 ms 6072 KB Output is correct - 61482 call(s) of encode_bit()
6 Correct 27 ms 6112 KB Output is correct - 68282 call(s) of encode_bit()
7 Correct 48 ms 6336 KB Output is correct - 68282 call(s) of encode_bit()
8 Correct 19 ms 5904 KB Output is correct - 65630 call(s) of encode_bit()
9 Correct 22 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
10 Correct 20 ms 5868 KB Output is correct - 68282 call(s) of encode_bit()
11 Correct 26 ms 5984 KB Output is correct - 68282 call(s) of encode_bit()
12 Correct 20 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
13 Correct 48 ms 6444 KB Output is correct - 68282 call(s) of encode_bit()
14 Correct 26 ms 5840 KB Output is correct - 68282 call(s) of encode_bit()
15 Correct 20 ms 5932 KB Output is correct - 68282 call(s) of encode_bit()
16 Correct 49 ms 6448 KB Output is correct - 68282 call(s) of encode_bit()
17 Correct 41 ms 6356 KB Output is correct - 68282 call(s) of encode_bit()
18 Correct 55 ms 6740 KB Output is correct - 68282 call(s) of encode_bit()
19 Correct 38 ms 6068 KB Output is correct - 68282 call(s) of encode_bit()
20 Correct 75 ms 6784 KB Output is correct - 68282 call(s) of encode_bit()
21 Correct 69 ms 6944 KB Output is correct - 68282 call(s) of encode_bit()
22 Correct 48 ms 6516 KB Output is correct - 68282 call(s) of encode_bit()
23 Correct 74 ms 7164 KB Output is correct - 68282 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 10724 KB Output is correct - 68282 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 292 call(s) of encode_bit()
3 Correct 24 ms 5852 KB Output is correct - 61482 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 312 call(s) of encode_bit()
5 Correct 25 ms 6072 KB Output is correct - 61482 call(s) of encode_bit()
6 Correct 27 ms 6112 KB Output is correct - 68282 call(s) of encode_bit()
7 Correct 48 ms 6336 KB Output is correct - 68282 call(s) of encode_bit()
8 Correct 19 ms 5904 KB Output is correct - 65630 call(s) of encode_bit()
9 Correct 22 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
10 Correct 20 ms 5868 KB Output is correct - 68282 call(s) of encode_bit()
11 Correct 26 ms 5984 KB Output is correct - 68282 call(s) of encode_bit()
12 Correct 20 ms 5860 KB Output is correct - 68282 call(s) of encode_bit()
13 Correct 48 ms 6444 KB Output is correct - 68282 call(s) of encode_bit()
14 Correct 26 ms 5840 KB Output is correct - 68282 call(s) of encode_bit()
15 Correct 20 ms 5932 KB Output is correct - 68282 call(s) of encode_bit()
16 Correct 49 ms 6448 KB Output is correct - 68282 call(s) of encode_bit()
17 Correct 41 ms 6356 KB Output is correct - 68282 call(s) of encode_bit()
18 Correct 55 ms 6740 KB Output is correct - 68282 call(s) of encode_bit()
19 Correct 38 ms 6068 KB Output is correct - 68282 call(s) of encode_bit()
20 Correct 75 ms 6784 KB Output is correct - 68282 call(s) of encode_bit()
21 Correct 69 ms 6944 KB Output is correct - 68282 call(s) of encode_bit()
22 Correct 48 ms 6516 KB Output is correct - 68282 call(s) of encode_bit()
23 Correct 74 ms 7164 KB Output is correct - 68282 call(s) of encode_bit()