oj.uz

Submission #796934

# Submission time Handle Problem Language Result Execution time Memory
796934 2023-07-28T23:35:58 Z I_Love_EliskaM_ Saveit (IOI10_saveit) C++14
100 / 100
 224 ms 10256 KB 
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

const int N=1e3;
vector<int> adj[N];
vector<int> nadj[N];
int par[N];

int vis[N];

void dfs(int u, int p) {
   if (vis[u]) return;
   vis[u]=1;
   par[u]=p;
   for(auto&v:adj[u]) {
      if (v==p) continue;
      dfs(v,u);
   }
}

void encode(int n, int h, int p, int a[], int b[]) {
   forn(i,p) {
      int u=a[i], v=b[i];
      adj[u].pb(v), adj[v].pb(u);
   }
   dfs(0,0);
   forn(i,n) forn(j,10) encode_bit((par[i]>>j)&1);

   vector<int> d, vis;

   forn(i,h) {
      d.assign(n,0), vis.assign(n,0);
      queue<int> q; q.push(i); vis[i]=1;
      while (q.size()) {
         auto u=q.front(); q.pop();
         for(auto&v:adj[u]) {
            if (vis[v]) continue;
            vis[v]=1;
            d[v]=d[u]+1;
            q.push(v);
         }
      }
      for (int i=0; i<n; i+=5) {
         int x=0, t=1;
         for (int j=i; j<min(i+5,n); ++j) {
            if (d[j]==d[par[j]]+1) {
               x+=t;
            } else if (d[j]==d[par[j]]-1) {
               x+=2*t;
            }
            t*=3;
         }
         forn(j,8) encode_bit((x>>j)&1);
      }
   }

}
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

const int N=1e3;
vector<int> adj[N];
vector<int> nadj[N];
int par[N];

int type[N];
int d[N];

void restore(int u, int p) {
   for(auto&v:adj[u]) {
      if (v==p) continue;
      if (v==par[u]) {
         if (type[u]==0) {
            d[v]=d[u];
         } else if (type[u]==1) {
            d[v]=d[u]-1;
         } else {
            d[v]=d[u]+1;
         }
      } else {
         if (type[v]==0) {
            d[v]=d[u];
         } else if (type[v]==1) {
            d[v]=d[u]+1;
         } else {
            d[v]=d[u]-1;
         }
      }
      restore(v,u);
   }
}

void decode(int n, int h) {
   forn(i,n) adj[i].clear();
   forn(i,n) forn(j,10) par[i]|=decode_bit()<<j;
   forn(i,n) if (i) {
      adj[i].pb(par[i]);
      adj[par[i]].pb(i);
   }
   forn(u,h) {
      forn(i,n) d[i]=0;
      for(int i=0; i<n; i+=5) {
         int x=0;
         forn(j,8) x|=decode_bit()<<j;
         for (int j=i; j<min(i+5,n); ++j) {
            type[j]=x%3;
            x/=3;
         }
      }
      restore(u,-1);
      forn(i,n) hops(u,i,d[i]);
   }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10256 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 18 ms 5500 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 1 ms 4600 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5628 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 19 ms 5752 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 38 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 16 ms 5512 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 19 ms 5492 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 18 ms 5524 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 19 ms 5584 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 17 ms 5500 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 43 ms 6056 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5564 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5628 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 43 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 37 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 36 ms 6280 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 30 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 48 ms 6460 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 47 ms 6656 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 31 ms 6164 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 57 ms 6812 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10256 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 18 ms 5500 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 1 ms 4600 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5628 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 19 ms 5752 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 38 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 16 ms 5512 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 19 ms 5492 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 18 ms 5524 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 19 ms 5584 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 17 ms 5500 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 43 ms 6056 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5564 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5628 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 43 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 37 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 36 ms 6280 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 30 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 48 ms 6460 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 47 ms 6656 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 31 ms 6164 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 57 ms 6812 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10256 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 18 ms 5500 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 1 ms 4600 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5628 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 19 ms 5752 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 38 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 16 ms 5512 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 19 ms 5492 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 18 ms 5524 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 19 ms 5584 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 17 ms 5500 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 43 ms 6056 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5564 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5628 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 43 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 37 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 36 ms 6280 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 30 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 48 ms 6460 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 47 ms 6656 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 31 ms 6164 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 57 ms 6812 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10256 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 18 ms 5500 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 1 ms 4600 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5628 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 19 ms 5752 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 38 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 16 ms 5512 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 19 ms 5492 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 18 ms 5524 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 19 ms 5584 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 17 ms 5500 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 43 ms 6056 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5564 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5628 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 43 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 37 ms 6000 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 36 ms 6280 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 30 ms 6064 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 48 ms 6460 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 47 ms 6656 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 31 ms 6164 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 57 ms 6812 KB Output is correct - 67600 call(s) of encode_bit()