oj.uz

Submission #566700

# Submission time Handle Problem Language Result Execution time Memory
566700 2022-05-22T16:51:00 Z Uzouf Saveit (IOI10_saveit) C++14
75 / 100
 199 ms 17956 KB 
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "encoder.h"
 
void encode(int n,int h,int p,int a[],int b[]) {
  vector<vector<int> > v(n+5);
  int dis[n+5][n+5];
  for (int i=0;i<n+5;i++) {
      for (int j=0;j<n+5;j++) {
        dis[i][j]=2000;
      }
      dis[i][i]=0;
    }
 
    for (int i=0;i<p;i++) {
      v[a[i]].push_back(b[i]);
      v[b[i]].push_back(a[i]);
      dis[a[i]][b[i]]=dis[b[i]][a[i]]=1;
    }
 
    int par[n+5];
    for (int i=0;i<n+5;i++) par[i]=i;
    queue<int> q;
    q.push(0); par[0]=-1;
 
    while (!q.empty()) {
      int i=q.front();
      q.pop();
      for (int j:v[i]) {
        if (par[j]==j) {
          par[j]=i; q.push(j);
        }
      }
    }
    //tree:
    for (int i=0;i<n;i++) {
      if (par[i]==-1) par[i]=i;
      for (int pp=0;pp<10;pp++) {
        if (((1<<pp)&par[i])==0) encode_bit(0);
        else encode_bit(1);
      }
    }
 
 
    for (int hub=1;hub<h;hub++) {
      //cout<<hub<<":"<<endl;
      int dis[n+5];
      bool vis[n+5];
      for (int i=0;i<n;i++) {
        vis[i]=false;
      }
      queue<int> q;
      q.push(hub); dis[hub]=0; vis[hub]=true;
 
      while (!q.empty()) {
        int i=q.front();
        q.pop();
        for (int j:v[i]) {
          if (!vis[j]) {
            vis[j]=true; dis[j]=dis[i]+1; q.push(j);
          }
        }
      }
 
      for (int i=0;i<n;i++) {
        int nm=dis[i]-dis[par[i]];
        //cout<<i<<' '<<par[i]<<"  "<<dis[i]<<' '<<dis[par[i]]<<' '<<nm<<endl;
        if (nm==0) {encode_bit(0);continue;}
        encode_bit(1);
        if (nm==1) encode_bit(0);
        else encode_bit(1);
      }
    }
}
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "encoder.h"
 
void decode(int n,int h) {
  vector<vector<int> > v(n+5);
  int par[n+5];
  for (int i=0;i<n;i++) {
    int tmp=0;
    for (int p=0;p<10;p++) {
      tmp+=(decode_bit()*(1<<p));
    }
    par[i]=tmp;
    v[i].push_back(tmp); v[tmp].push_back(i);
  }
 
  for (int hub=0;hub<h;hub++) {
    int dis[n+5][n+5];
 
    if (hub>0) {
      for (int i=0;i<n;i++) {
        int tmp=decode_bit();
        if (tmp==0) {
          dis[i][par[i]]=0; dis[par[i]][i]=0;
        }
        else {
          tmp=decode_bit();
          if (tmp==0) {
            dis[par[i]][i]=1; dis[i][par[i]]=-1;
          }
          else {
            dis[i][par[i]]=1; dis[par[i]][i]=-1;
          }
        }
      }
    }
    else {
      for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) dis[i][j]=1;
      }
    }
 
    queue<int> q;
    int ans[n+5];
    bool vis[n+5];
    memset(vis,false,sizeof vis);
    ans[hub]=0; q.push(hub); vis[hub]=true;
 
    while (!q.empty()) {
      int i=q.front();
      q.pop();
      hops(hub,i,ans[i]);
 
      for (int j:v[i]) {
        if (!vis[j]) {
          q.push(j); ans[j]=ans[i]+dis[i][j]; vis[j]=true;
        }
      }
    }
 
  }
 
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 17956 KB Output is correct - 62958 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 25 ms 11648 KB Output is correct - 58946 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 27 ms 11780 KB Output is correct - 56333 call(s) of encode_bit()
6 Correct 31 ms 13244 KB Output is correct - 60950 call(s) of encode_bit()
7 Correct 38 ms 13552 KB Output is correct - 50873 call(s) of encode_bit()
8 Correct 32 ms 12604 KB Output is partially correct - 76845 call(s) of encode_bit()
9 Correct 27 ms 13384 KB Output is partially correct - 78691 call(s) of encode_bit()
10 Correct 28 ms 13304 KB Output is partially correct - 78290 call(s) of encode_bit()
11 Correct 32 ms 13552 KB Output is partially correct - 76588 call(s) of encode_bit()
12 Correct 27 ms 13284 KB Output is partially correct - 79965 call(s) of encode_bit()
13 Correct 49 ms 13792 KB Output is correct - 58371 call(s) of encode_bit()
14 Correct 37 ms 13420 KB Output is partially correct - 77739 call(s) of encode_bit()
15 Correct 34 ms 13332 KB Output is partially correct - 76221 call(s) of encode_bit()
16 Correct 55 ms 13992 KB Output is partially correct - 72163 call(s) of encode_bit()
17 Correct 41 ms 13832 KB Output is partially correct - 74054 call(s) of encode_bit()
18 Correct 49 ms 13900 KB Output is correct - 69868 call(s) of encode_bit()
19 Correct 38 ms 13560 KB Output is correct - 66888 call(s) of encode_bit()
20 Correct 59 ms 14160 KB Output is correct - 63615 call(s) of encode_bit()
21 Correct 66 ms 14288 KB Output is correct - 64365 call(s) of encode_bit()
22 Correct 46 ms 13808 KB Output is correct - 53084 call(s) of encode_bit()
23 Correct 65 ms 14516 KB Output is correct - 56870 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 17956 KB Output is correct - 62958 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 25 ms 11648 KB Output is correct - 58946 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 27 ms 11780 KB Output is correct - 56333 call(s) of encode_bit()
6 Correct 31 ms 13244 KB Output is correct - 60950 call(s) of encode_bit()
7 Correct 38 ms 13552 KB Output is correct - 50873 call(s) of encode_bit()
8 Correct 32 ms 12604 KB Output is partially correct - 76845 call(s) of encode_bit()
9 Correct 27 ms 13384 KB Output is partially correct - 78691 call(s) of encode_bit()
10 Correct 28 ms 13304 KB Output is partially correct - 78290 call(s) of encode_bit()
11 Correct 32 ms 13552 KB Output is partially correct - 76588 call(s) of encode_bit()
12 Correct 27 ms 13284 KB Output is partially correct - 79965 call(s) of encode_bit()
13 Correct 49 ms 13792 KB Output is correct - 58371 call(s) of encode_bit()
14 Correct 37 ms 13420 KB Output is partially correct - 77739 call(s) of encode_bit()
15 Correct 34 ms 13332 KB Output is partially correct - 76221 call(s) of encode_bit()
16 Correct 55 ms 13992 KB Output is partially correct - 72163 call(s) of encode_bit()
17 Correct 41 ms 13832 KB Output is partially correct - 74054 call(s) of encode_bit()
18 Correct 49 ms 13900 KB Output is correct - 69868 call(s) of encode_bit()
19 Correct 38 ms 13560 KB Output is correct - 66888 call(s) of encode_bit()
20 Correct 59 ms 14160 KB Output is correct - 63615 call(s) of encode_bit()
21 Correct 66 ms 14288 KB Output is correct - 64365 call(s) of encode_bit()
22 Correct 46 ms 13808 KB Output is correct - 53084 call(s) of encode_bit()
23 Correct 65 ms 14516 KB Output is correct - 56870 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 17956 KB Output is correct - 62958 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 25 ms 11648 KB Output is correct - 58946 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 27 ms 11780 KB Output is correct - 56333 call(s) of encode_bit()
6 Correct 31 ms 13244 KB Output is correct - 60950 call(s) of encode_bit()
7 Correct 38 ms 13552 KB Output is correct - 50873 call(s) of encode_bit()
8 Correct 32 ms 12604 KB Output is partially correct - 76845 call(s) of encode_bit()
9 Correct 27 ms 13384 KB Output is partially correct - 78691 call(s) of encode_bit()
10 Correct 28 ms 13304 KB Output is partially correct - 78290 call(s) of encode_bit()
11 Correct 32 ms 13552 KB Output is partially correct - 76588 call(s) of encode_bit()
12 Correct 27 ms 13284 KB Output is partially correct - 79965 call(s) of encode_bit()
13 Correct 49 ms 13792 KB Output is correct - 58371 call(s) of encode_bit()
14 Correct 37 ms 13420 KB Output is partially correct - 77739 call(s) of encode_bit()
15 Correct 34 ms 13332 KB Output is partially correct - 76221 call(s) of encode_bit()
16 Correct 55 ms 13992 KB Output is partially correct - 72163 call(s) of encode_bit()
17 Correct 41 ms 13832 KB Output is partially correct - 74054 call(s) of encode_bit()
18 Correct 49 ms 13900 KB Output is correct - 69868 call(s) of encode_bit()
19 Correct 38 ms 13560 KB Output is correct - 66888 call(s) of encode_bit()
20 Correct 59 ms 14160 KB Output is correct - 63615 call(s) of encode_bit()
21 Correct 66 ms 14288 KB Output is correct - 64365 call(s) of encode_bit()
22 Correct 46 ms 13808 KB Output is correct - 53084 call(s) of encode_bit()
23 Correct 65 ms 14516 KB Output is correct - 56870 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 17956 KB Output is correct - 62958 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 25 ms 11648 KB Output is correct - 58946 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 27 ms 11780 KB Output is correct - 56333 call(s) of encode_bit()
6 Correct 31 ms 13244 KB Output is correct - 60950 call(s) of encode_bit()
7 Correct 38 ms 13552 KB Output is correct - 50873 call(s) of encode_bit()
8 Correct 32 ms 12604 KB Output is partially correct - 76845 call(s) of encode_bit()
9 Correct 27 ms 13384 KB Output is partially correct - 78691 call(s) of encode_bit()
10 Correct 28 ms 13304 KB Output is partially correct - 78290 call(s) of encode_bit()
11 Correct 32 ms 13552 KB Output is partially correct - 76588 call(s) of encode_bit()
12 Correct 27 ms 13284 KB Output is partially correct - 79965 call(s) of encode_bit()
13 Correct 49 ms 13792 KB Output is correct - 58371 call(s) of encode_bit()
14 Correct 37 ms 13420 KB Output is partially correct - 77739 call(s) of encode_bit()
15 Correct 34 ms 13332 KB Output is partially correct - 76221 call(s) of encode_bit()
16 Correct 55 ms 13992 KB Output is partially correct - 72163 call(s) of encode_bit()
17 Correct 41 ms 13832 KB Output is partially correct - 74054 call(s) of encode_bit()
18 Correct 49 ms 13900 KB Output is correct - 69868 call(s) of encode_bit()
19 Correct 38 ms 13560 KB Output is correct - 66888 call(s) of encode_bit()
20 Correct 59 ms 14160 KB Output is correct - 63615 call(s) of encode_bit()
21 Correct 66 ms 14288 KB Output is correct - 64365 call(s) of encode_bit()
22 Correct 46 ms 13808 KB Output is correct - 53084 call(s) of encode_bit()
23 Correct 65 ms 14516 KB Output is correct - 56870 call(s) of encode_bit()