oj.uz

Submission #785850

# Submission time Handle Problem Language Result Execution time Memory
785850 2023-07-17T16:25:01 Z PoonYaPat Saveit (IOI10_saveit) C++14
100 / 100
 151 ms 12700 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1005];
int n,h,p[1005],dis[1005][36];
bool vis[1005];

void dfs(int x, int par) {
  p[x]=par;
  vis[x]=true;
  for (auto s : adj[x]) if (!vis[s]) dfs(s,x);
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  n=nv; h=nh;
  for (int i=0; i<ne; ++i) {
    adj[v1[i]].push_back(v2[i]);
    adj[v2[i]].push_back(v1[i]);
  }

  dfs(0,0);
  for (int i=1; i<n; ++i) {
    for (int j=0; j<10; ++j) {
      if (p[i]&(1<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }

  vector<int> v;
  memset(dis,-1,sizeof(dis));
  for (int i=0; i<h; ++i) {
    dis[i][i]=0;
    queue<int> q;
    q.push(i);

    while (!q.empty()) {
      int node=q.front();
      q.pop();
      for (auto s : adj[node]) {
        if (dis[s][i]==-1) {
          dis[s][i]=dis[node][i]+1;
          q.push(s);
        }
      }
    }

    for (int j=1; j<n; ++j) v.push_back(dis[p[j]][i]-dis[j][i]+1);
  }

  while (v.size()%3) v.push_back(0);

  for (int i=0; i<v.size(); i+=3) {
    int sum=v[i]+3*v[i+1]+9*v[i+2];
    for (int j=0; j<5; ++j) {
      if (sum&(1<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int nn,hh,pp[1005];
vector<int> v;
vector<pii> adjj[1005][36];

void dfs(int x, int par, int val, int gr) {
   hops(gr,x,val);
   for (auto s : adjj[x][gr]) {
      if (s.first!=par) dfs(s.first,x,val+s.second,gr); 
   }
}

void decode(int nv, int nh) {
   nn=nv; hh=nh;
   for (int i=1; i<nn; ++i) {
      int sum=0;
      for (int j=0; j<10; ++j) {
         if (decode_bit()==1) sum+=(1<<j);
      }
      pp[i]=sum;
   }

   for (int i=0; i<((nn-1)*hh+2)/3; ++i) {
      int sum=0;
      for (int j=0; j<5; ++j) if (decode_bit()==1) sum+=(1<<j);
      v.push_back(sum%3-1); sum/=3;
      v.push_back(sum%3-1); sum/=3;
      v.push_back(sum%3-1);
   }

   int idx=0;
   for (int i=0; i<hh; ++i) {
      for (int j=1; j<nn; ++j) {
         adjj[j][i].push_back({pp[j],v[idx]});
         adjj[pp[j]][i].push_back({j,-v[idx]});
         ++idx;
      }
   }

   for (int i=0; i<hh; ++i) dfs(i,i,0,i);
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i=0; i<v.size(); i+=3) {
      |                 ~^~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 12700 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 5628 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 7784 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 5628 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 28 ms 7924 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 8044 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 37 ms 8360 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 7684 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 7880 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 25 ms 7832 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 8028 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 26 ms 7828 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 42 ms 8424 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 7992 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 7852 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 46 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 46 ms 8252 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 44 ms 8700 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 8112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 56 ms 8980 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 68 ms 9016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 8504 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 75 ms 9192 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 12700 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 5628 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 7784 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 5628 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 28 ms 7924 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 8044 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 37 ms 8360 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 7684 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 7880 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 25 ms 7832 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 8028 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 26 ms 7828 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 42 ms 8424 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 7992 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 7852 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 46 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 46 ms 8252 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 44 ms 8700 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 8112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 56 ms 8980 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 68 ms 9016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 8504 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 75 ms 9192 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 12700 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 5628 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 7784 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 5628 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 28 ms 7924 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 8044 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 37 ms 8360 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 7684 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 7880 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 25 ms 7832 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 8028 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 26 ms 7828 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 42 ms 8424 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 7992 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 7852 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 46 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 46 ms 8252 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 44 ms 8700 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 8112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 56 ms 8980 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 68 ms 9016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 8504 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 75 ms 9192 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 12700 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 5628 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 7784 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 5628 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 28 ms 7924 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 8044 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 37 ms 8360 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 7684 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 7880 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 25 ms 7832 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 30 ms 8028 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 26 ms 7828 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 42 ms 8424 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 23 ms 7992 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 7852 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 46 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 46 ms 8252 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 44 ms 8700 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 41 ms 8112 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 56 ms 8980 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 68 ms 9016 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 8504 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 75 ms 9192 KB Output is correct - 69930 call(s) of encode_bit()