oj.uz

Submission #598769

# Submission time Handle Problem Language Result Execution time Memory
598769 2022-07-19T02:37:27 Z farhan132 Saveit (IOI10_saveit) C++17
100 / 100
 205 ms 10456 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 1005;
vector < ll > v[N], g[N];
ll dist[40][N];
bool vis[N]; 
ll n, h;
ll par[N];

void dfs(ll s){
  vis[s] = 1;
  for(auto u : v[s]){
    if(!vis[u]){
      g[s].pb(u);
      g[u].pb(s);
      par[u] = s;
      dfs(u);
    }
  }
  return;
}

void bfs(int source){
  for(ll i = 0; i < n; i++) dist[source][i] = -1;
  dist[source][source] = 0;
  queue < ll > q; q.push(source);
  while(q.size()){
    auto node = q.front(); q.pop();
    for(auto u : v[node]){
      if(dist[source][u] == -1){
        dist[source][u] = dist[source][node] + 1;
        q.push(u);
      }
    }
  }
  return;
}
vector < ll > mp = {-1, 0, 1};
vector < ll > cnt(3, 0);
int convert(int num){
  for(int i = 0; i < 3; i++){
    if(mp[i] == num) return i;
  }
  cout << "Something is Wrrong\n";
  return 3;
}
int start = 0;
void magic(ll s, ll p){
  for(auto u : g[s]){
    if(u - p){
      cnt[convert(dist[start][u] - dist[start][s])]++;
      magic(u, s);
    }
  }
  return;
}
void final(ll s, ll p){
  for(auto u : g[s]){
    if(u - p){
      ll k = convert(dist[start][u] - dist[start][s]);
      if(k == 0){
        encode_bit(0);
      }else{
        encode_bit(1);
        encode_bit(k - 1);
      }
      final(u, s);
    }
  }
  return;
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  n = nv, h = nh;
  memset(vis, 0, sizeof(vis));
  for(ll i = 0; i < ne; i++){
    int x = v1[i] , y = v2[i];
    v[x].pb(y);
    v[y].pb(x);
  }
  dfs(0);
  for(ll i = 1; i < n; i++){
    for(ll j = 0; j < 10; j++){
      encode_bit((par[i] >> j)&1);
    }
  }
  for(ll i = 0; i < n; i++){
    sort(g[i].begin(), g[i].end());
  }
  for(ll i = 0; i < h; i++){
    start = i;
    bfs(i);
    magic(i, -1);
  }
  if(cnt[0] >= max(cnt[1], cnt[2])){
    encode_bit(0);
    encode_bit(0);
  }else if(cnt[1] >= max(cnt[0], cnt[2])){
    encode_bit(1);
    encode_bit(0);
    swap(mp[0], mp[1]);
  }else{
    encode_bit(0);
    encode_bit(1);
    swap(mp[0], mp[2]);
  }
  for(ll i = 0; i < h; i++){
    start = i;
    final(i, -1);
  }

  return;
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 1005;
vector < ll > _g[N];

ll _n , _h;
vector < ll > rev = {-1, 0, 1};

void ultimate(ll s, ll p, ll D, ll source){
   hops(source, s, D);
   for(auto u : _g[s]){
      if(u - p){
         int k = decode_bit();
         if(k == 0){
            ultimate(u, s, D + rev[k], source);
         }else{
            k += decode_bit();
            ultimate(u, s, D + rev[k], source);
         }
      }
   }
   return;
}

void decode(int nv, int nh) {
   _n = nv;
   _h = nh;
   for(ll i = 1; i < _n; i++){
      ll p = 0;
      for(ll j = 0; j < 10; j++){
         int k = decode_bit();
         p |= (k << j);
      }
      _g[p].pb(i);
      _g[i].pb(p);
   }
   ll pos = 0;
   for(ll i = 0; i < 2; i++){
      int k = decode_bit();
      pos |= (k << i);
   }
   swap(rev[pos], rev[0]);
   for(ll i = 0; i < _n; i++){
      sort(_g[i].begin(), _g[i].end());
   }
   for(ll i = 0; i < _h; i++){
      ultimate(i, -1, 0, i);
   }
   return;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10456 KB Output is correct - 63890 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 58 call(s) of encode_bit()
3 Correct 20 ms 5596 KB Output is correct - 60442 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 28 ms 5776 KB Output is correct - 57367 call(s) of encode_bit()
6 Correct 31 ms 5864 KB Output is correct - 62204 call(s) of encode_bit()
7 Correct 40 ms 6088 KB Output is correct - 52277 call(s) of encode_bit()
8 Correct 24 ms 5608 KB Output is correct - 60549 call(s) of encode_bit()
9 Correct 20 ms 5484 KB Output is correct - 48558 call(s) of encode_bit()
10 Correct 20 ms 5588 KB Output is correct - 48560 call(s) of encode_bit()
11 Correct 26 ms 5608 KB Output is correct - 51293 call(s) of encode_bit()
12 Correct 20 ms 5656 KB Output is correct - 45956 call(s) of encode_bit()
13 Correct 65 ms 6104 KB Output is correct - 59065 call(s) of encode_bit()
14 Correct 24 ms 5728 KB Output is correct - 56265 call(s) of encode_bit()
15 Correct 25 ms 5640 KB Output is correct - 58043 call(s) of encode_bit()
16 Correct 44 ms 6180 KB Output is correct - 62369 call(s) of encode_bit()
17 Correct 40 ms 6228 KB Output is correct - 62344 call(s) of encode_bit()
18 Correct 53 ms 6444 KB Output is correct - 68110 call(s) of encode_bit()
19 Correct 42 ms 5932 KB Output is correct - 62759 call(s) of encode_bit()
20 Correct 89 ms 6600 KB Output is correct - 62991 call(s) of encode_bit()
21 Correct 88 ms 6892 KB Output is correct - 63454 call(s) of encode_bit()
22 Correct 62 ms 6172 KB Output is correct - 54294 call(s) of encode_bit()
23 Correct 67 ms 6924 KB Output is correct - 57577 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10456 KB Output is correct - 63890 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 58 call(s) of encode_bit()
3 Correct 20 ms 5596 KB Output is correct - 60442 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 28 ms 5776 KB Output is correct - 57367 call(s) of encode_bit()
6 Correct 31 ms 5864 KB Output is correct - 62204 call(s) of encode_bit()
7 Correct 40 ms 6088 KB Output is correct - 52277 call(s) of encode_bit()
8 Correct 24 ms 5608 KB Output is correct - 60549 call(s) of encode_bit()
9 Correct 20 ms 5484 KB Output is correct - 48558 call(s) of encode_bit()
10 Correct 20 ms 5588 KB Output is correct - 48560 call(s) of encode_bit()
11 Correct 26 ms 5608 KB Output is correct - 51293 call(s) of encode_bit()
12 Correct 20 ms 5656 KB Output is correct - 45956 call(s) of encode_bit()
13 Correct 65 ms 6104 KB Output is correct - 59065 call(s) of encode_bit()
14 Correct 24 ms 5728 KB Output is correct - 56265 call(s) of encode_bit()
15 Correct 25 ms 5640 KB Output is correct - 58043 call(s) of encode_bit()
16 Correct 44 ms 6180 KB Output is correct - 62369 call(s) of encode_bit()
17 Correct 40 ms 6228 KB Output is correct - 62344 call(s) of encode_bit()
18 Correct 53 ms 6444 KB Output is correct - 68110 call(s) of encode_bit()
19 Correct 42 ms 5932 KB Output is correct - 62759 call(s) of encode_bit()
20 Correct 89 ms 6600 KB Output is correct - 62991 call(s) of encode_bit()
21 Correct 88 ms 6892 KB Output is correct - 63454 call(s) of encode_bit()
22 Correct 62 ms 6172 KB Output is correct - 54294 call(s) of encode_bit()
23 Correct 67 ms 6924 KB Output is correct - 57577 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10456 KB Output is correct - 63890 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 58 call(s) of encode_bit()
3 Correct 20 ms 5596 KB Output is correct - 60442 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 28 ms 5776 KB Output is correct - 57367 call(s) of encode_bit()
6 Correct 31 ms 5864 KB Output is correct - 62204 call(s) of encode_bit()
7 Correct 40 ms 6088 KB Output is correct - 52277 call(s) of encode_bit()
8 Correct 24 ms 5608 KB Output is correct - 60549 call(s) of encode_bit()
9 Correct 20 ms 5484 KB Output is correct - 48558 call(s) of encode_bit()
10 Correct 20 ms 5588 KB Output is correct - 48560 call(s) of encode_bit()
11 Correct 26 ms 5608 KB Output is correct - 51293 call(s) of encode_bit()
12 Correct 20 ms 5656 KB Output is correct - 45956 call(s) of encode_bit()
13 Correct 65 ms 6104 KB Output is correct - 59065 call(s) of encode_bit()
14 Correct 24 ms 5728 KB Output is correct - 56265 call(s) of encode_bit()
15 Correct 25 ms 5640 KB Output is correct - 58043 call(s) of encode_bit()
16 Correct 44 ms 6180 KB Output is correct - 62369 call(s) of encode_bit()
17 Correct 40 ms 6228 KB Output is correct - 62344 call(s) of encode_bit()
18 Correct 53 ms 6444 KB Output is correct - 68110 call(s) of encode_bit()
19 Correct 42 ms 5932 KB Output is correct - 62759 call(s) of encode_bit()
20 Correct 89 ms 6600 KB Output is correct - 62991 call(s) of encode_bit()
21 Correct 88 ms 6892 KB Output is correct - 63454 call(s) of encode_bit()
22 Correct 62 ms 6172 KB Output is correct - 54294 call(s) of encode_bit()
23 Correct 67 ms 6924 KB Output is correct - 57577 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10456 KB Output is correct - 63890 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 58 call(s) of encode_bit()
3 Correct 20 ms 5596 KB Output is correct - 60442 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 28 ms 5776 KB Output is correct - 57367 call(s) of encode_bit()
6 Correct 31 ms 5864 KB Output is correct - 62204 call(s) of encode_bit()
7 Correct 40 ms 6088 KB Output is correct - 52277 call(s) of encode_bit()
8 Correct 24 ms 5608 KB Output is correct - 60549 call(s) of encode_bit()
9 Correct 20 ms 5484 KB Output is correct - 48558 call(s) of encode_bit()
10 Correct 20 ms 5588 KB Output is correct - 48560 call(s) of encode_bit()
11 Correct 26 ms 5608 KB Output is correct - 51293 call(s) of encode_bit()
12 Correct 20 ms 5656 KB Output is correct - 45956 call(s) of encode_bit()
13 Correct 65 ms 6104 KB Output is correct - 59065 call(s) of encode_bit()
14 Correct 24 ms 5728 KB Output is correct - 56265 call(s) of encode_bit()
15 Correct 25 ms 5640 KB Output is correct - 58043 call(s) of encode_bit()
16 Correct 44 ms 6180 KB Output is correct - 62369 call(s) of encode_bit()
17 Correct 40 ms 6228 KB Output is correct - 62344 call(s) of encode_bit()
18 Correct 53 ms 6444 KB Output is correct - 68110 call(s) of encode_bit()
19 Correct 42 ms 5932 KB Output is correct - 62759 call(s) of encode_bit()
20 Correct 89 ms 6600 KB Output is correct - 62991 call(s) of encode_bit()
21 Correct 88 ms 6892 KB Output is correct - 63454 call(s) of encode_bit()
22 Correct 62 ms 6172 KB Output is correct - 54294 call(s) of encode_bit()
23 Correct 67 ms 6924 KB Output is correct - 57577 call(s) of encode_bit()