oj.uz

Submission #796937

# Submission time Handle Problem Language Result Execution time Memory
796937 2023-07-28T23:37:26 Z TimDee Saveit (IOI10_saveit) C++17
100 / 100
 237 ms 10472 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 237 ms 10472 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5632 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 22 ms 5756 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 34 ms 6060 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 19 ms 5496 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 18 ms 5504 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 5592 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 18 ms 5528 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 45 ms 6140 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5480 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5608 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 41 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 27 ms 5984 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 34 ms 6204 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 24 ms 5796 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 55 ms 6448 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 45 ms 6536 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 42 ms 6156 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 74 ms 6920 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 10472 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5632 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 22 ms 5756 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 34 ms 6060 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 19 ms 5496 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 18 ms 5504 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 5592 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 18 ms 5528 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 45 ms 6140 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5480 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5608 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 41 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 27 ms 5984 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 34 ms 6204 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 24 ms 5796 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 55 ms 6448 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 45 ms 6536 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 42 ms 6156 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 74 ms 6920 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 10472 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5632 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 22 ms 5756 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 34 ms 6060 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 19 ms 5496 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 18 ms 5504 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 5592 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 18 ms 5528 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 45 ms 6140 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5480 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5608 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 41 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 27 ms 5984 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 34 ms 6204 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 24 ms 5796 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 55 ms 6448 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 45 ms 6536 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 42 ms 6156 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 74 ms 6920 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 10472 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 19 ms 5632 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 22 ms 5756 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 34 ms 6060 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 19 ms 5496 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 18 ms 5504 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 5592 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 18 ms 5528 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 45 ms 6140 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 19 ms 5480 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 19 ms 5608 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 41 ms 5952 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 27 ms 5984 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 34 ms 6204 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 24 ms 5796 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 55 ms 6448 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 45 ms 6536 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 42 ms 6156 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 74 ms 6920 KB Output is correct - 67600 call(s) of encode_bit()