oj.uz

Submission #1013098

# Submission time Handle Problem Language Result Execution time Memory
1013098 2024-07-03T07:45:29 Z huutuan Saveit (IOI10_saveit) C++14
100 / 100
 143 ms 13892 KB 
#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace encoder{
   const int N=1000, H=36;
   int n, h, e, dist[N][H];
   vector<int> g[N];
   int par[N];
   void send(string s){
      for (char c:s) encode_bit(c-'0');
   }
   void bfs(int root){
      queue<int> q;
      q.push(root); dist[root][root]=0;
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:g[u]) if (dist[v][root]==-1){
            dist[v][root]=dist[u][root]+1;
            q.push(v);
         }
      }
   }
   void bfs2(){
      queue<int> q;
      q.push(0);
      memset(par, -1, sizeof par);
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:g[u]) if (par[v]==-1){
            par[v]=u; q.push(v);
         }
      }
   }
   void solve(int32_t _n, int32_t _h, int32_t _e, int32_t *v1, int32_t *v2){
      n=_n, h=_h, e=_e;
      for (int i=0; i<e; ++i) g[v1[i]].push_back(v2[i]), g[v2[i]].push_back(v1[i]);
      memset(dist, -1, sizeof dist);
      for (int i=0; i<h; ++i) bfs(i);
      bfs2();
      for (int i=0; i<h; ++i){
         send(bitset<10>(dist[0][i]).to_string());
      }
      for (int i=1; i<n; ++i){
         send(bitset<10>(par[i]).to_string());
         int val=0;
         for (int j=0, pw=1; j<h; ++j, pw*=3){
            int d=dist[i][j]-dist[par[i]][j]+1;
            val+=d*pw;
         }
         send(bitset<58>(val).to_string());
      }
   }
}

void encode(int32_t nv, int32_t nh, int32_t ne, int32_t *v1, int32_t *v2){
   encoder::solve(nv, nh, ne, v1, v2);
   return;
}

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace decoder{
   const int N=1000, H=36;
   int n, h, dist[N][H], val[N], par[N];
   vector<int> g[N];
   string read(int len){
      string s;
      for (int i=0; i<len; ++i) s.push_back('0'+decode_bit());
      return s;
   }
   int vis[N];
   vector<int> bfs(){
      queue<int> q;
      q.push(0); vis[0]=1;
      vector<int> order;
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:g[u]) if (!vis[v]){
            vis[v]=1;
            q.push(v);
            order.push_back(v);
         }
      }
      return order;
   }
   void solve(int32_t _n, int32_t _h){
      n=_n, h=_h;
      for (int i=0; i<h; ++i) dist[0][i]=bitset<10>(read(10)).to_ullong();
      par[0]=-1;
      for (int i=1; i<n; ++i){
         par[i]=bitset<10>(read(10)).to_ullong();
         val[i]=bitset<58>(read(58)).to_ullong();
         g[par[i]].push_back(i);
      }
      auto order=bfs();
      for (int i:order){
         int p=par[i];
         for (int j=0; j<h; ++j){
            dist[i][j]=dist[p][j]+(val[i]%3)-1;
            val[i]/=3;
         }
      }
      for (int i=0; i<h; ++i) for (int j=0; j<n; ++j) hops(i, j, dist[j][i]);
   }
}

void decode(int32_t nv, int32_t nh) {
   decoder::solve(nv, nh);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 13892 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 14 ms 5904 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4876 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 13 ms 6156 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 26 ms 6904 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 13 ms 6160 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 17 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 18 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 15 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 19 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 37 ms 7192 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 15 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 30 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 28 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 32 ms 7420 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 21 ms 6956 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 38 ms 7856 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 50 ms 8112 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 37 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 47 ms 8440 KB Output is correct - 68292 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 13892 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 14 ms 5904 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4876 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 13 ms 6156 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 26 ms 6904 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 13 ms 6160 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 17 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 18 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 15 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 19 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 37 ms 7192 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 15 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 30 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 28 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 32 ms 7420 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 21 ms 6956 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 38 ms 7856 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 50 ms 8112 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 37 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 47 ms 8440 KB Output is correct - 68292 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 13892 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 14 ms 5904 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4876 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 13 ms 6156 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 26 ms 6904 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 13 ms 6160 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 17 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 18 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 15 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 19 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 37 ms 7192 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 15 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 30 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 28 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 32 ms 7420 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 21 ms 6956 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 38 ms 7856 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 50 ms 8112 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 37 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 47 ms 8440 KB Output is correct - 68292 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 13892 KB Output is correct - 68292 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 302 call(s) of encode_bit()
3 Correct 14 ms 5904 KB Output is correct - 61492 call(s) of encode_bit()
4 Correct 2 ms 4876 KB Output is correct - 322 call(s) of encode_bit()
5 Correct 13 ms 6156 KB Output is correct - 61492 call(s) of encode_bit()
6 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
7 Correct 26 ms 6904 KB Output is correct - 68292 call(s) of encode_bit()
8 Correct 13 ms 6160 KB Output is correct - 65640 call(s) of encode_bit()
9 Correct 17 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
10 Correct 18 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
11 Correct 15 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
12 Correct 19 ms 6160 KB Output is correct - 68292 call(s) of encode_bit()
13 Correct 37 ms 7192 KB Output is correct - 68292 call(s) of encode_bit()
14 Correct 15 ms 6156 KB Output is correct - 68292 call(s) of encode_bit()
15 Correct 14 ms 6416 KB Output is correct - 68292 call(s) of encode_bit()
16 Correct 30 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
17 Correct 28 ms 6920 KB Output is correct - 68292 call(s) of encode_bit()
18 Correct 32 ms 7420 KB Output is correct - 68292 call(s) of encode_bit()
19 Correct 21 ms 6956 KB Output is correct - 68292 call(s) of encode_bit()
20 Correct 38 ms 7856 KB Output is correct - 68292 call(s) of encode_bit()
21 Correct 50 ms 8112 KB Output is correct - 68292 call(s) of encode_bit()
22 Correct 37 ms 7376 KB Output is correct - 68292 call(s) of encode_bit()
23 Correct 47 ms 8440 KB Output is correct - 68292 call(s) of encode_bit()