oj.uz

Submission #796928

# Submission time Handle Problem Language Result Execution time Memory
796928 2023-07-28T23:27:56 Z I_Love_EliskaM_ Saveit (IOI10_saveit) C++14
0 / 100
 278 ms 10344 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[i]==d[par[i]]+1) {
               x+=t;
            } else if (d[i]==d[par[i]]-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;
         }
      }
   }
}

void decode(int n, int h) {
   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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 10344 KB wrong parameter
2 Incorrect 3 ms 4612 KB Output isn't correct
3 Incorrect 16 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4600 KB Output isn't correct
5 Incorrect 20 ms 5492 KB wrong parameter
6 Incorrect 20 ms 5604 KB wrong parameter
7 Incorrect 33 ms 6000 KB wrong parameter
8 Incorrect 14 ms 5432 KB wrong parameter
9 Incorrect 14 ms 5492 KB wrong parameter
10 Incorrect 16 ms 5416 KB wrong parameter
11 Incorrect 20 ms 5612 KB wrong parameter
12 Incorrect 14 ms 5464 KB wrong parameter
13 Incorrect 35 ms 6068 KB wrong parameter
14 Incorrect 16 ms 5480 KB wrong parameter
15 Incorrect 18 ms 5576 KB wrong parameter
16 Incorrect 31 ms 5932 KB wrong parameter
17 Incorrect 27 ms 5988 KB wrong parameter
18 Incorrect 39 ms 6184 KB wrong parameter
19 Incorrect 23 ms 5880 KB wrong parameter
20 Incorrect 48 ms 6428 KB wrong parameter
21 Incorrect 59 ms 6672 KB wrong parameter
22 Incorrect 31 ms 6188 KB wrong parameter
23 Incorrect 68 ms 6840 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 10344 KB wrong parameter
2 Incorrect 3 ms 4612 KB Output isn't correct
3 Incorrect 16 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4600 KB Output isn't correct
5 Incorrect 20 ms 5492 KB wrong parameter
6 Incorrect 20 ms 5604 KB wrong parameter
7 Incorrect 33 ms 6000 KB wrong parameter
8 Incorrect 14 ms 5432 KB wrong parameter
9 Incorrect 14 ms 5492 KB wrong parameter
10 Incorrect 16 ms 5416 KB wrong parameter
11 Incorrect 20 ms 5612 KB wrong parameter
12 Incorrect 14 ms 5464 KB wrong parameter
13 Incorrect 35 ms 6068 KB wrong parameter
14 Incorrect 16 ms 5480 KB wrong parameter
15 Incorrect 18 ms 5576 KB wrong parameter
16 Incorrect 31 ms 5932 KB wrong parameter
17 Incorrect 27 ms 5988 KB wrong parameter
18 Incorrect 39 ms 6184 KB wrong parameter
19 Incorrect 23 ms 5880 KB wrong parameter
20 Incorrect 48 ms 6428 KB wrong parameter
21 Incorrect 59 ms 6672 KB wrong parameter
22 Incorrect 31 ms 6188 KB wrong parameter
23 Incorrect 68 ms 6840 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 10344 KB wrong parameter
2 Incorrect 3 ms 4612 KB Output isn't correct
3 Incorrect 16 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4600 KB Output isn't correct
5 Incorrect 20 ms 5492 KB wrong parameter
6 Incorrect 20 ms 5604 KB wrong parameter
7 Incorrect 33 ms 6000 KB wrong parameter
8 Incorrect 14 ms 5432 KB wrong parameter
9 Incorrect 14 ms 5492 KB wrong parameter
10 Incorrect 16 ms 5416 KB wrong parameter
11 Incorrect 20 ms 5612 KB wrong parameter
12 Incorrect 14 ms 5464 KB wrong parameter
13 Incorrect 35 ms 6068 KB wrong parameter
14 Incorrect 16 ms 5480 KB wrong parameter
15 Incorrect 18 ms 5576 KB wrong parameter
16 Incorrect 31 ms 5932 KB wrong parameter
17 Incorrect 27 ms 5988 KB wrong parameter
18 Incorrect 39 ms 6184 KB wrong parameter
19 Incorrect 23 ms 5880 KB wrong parameter
20 Incorrect 48 ms 6428 KB wrong parameter
21 Incorrect 59 ms 6672 KB wrong parameter
22 Incorrect 31 ms 6188 KB wrong parameter
23 Incorrect 68 ms 6840 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 10344 KB wrong parameter
2 Incorrect 3 ms 4612 KB Output isn't correct
3 Incorrect 16 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4600 KB Output isn't correct
5 Incorrect 20 ms 5492 KB wrong parameter
6 Incorrect 20 ms 5604 KB wrong parameter
7 Incorrect 33 ms 6000 KB wrong parameter
8 Incorrect 14 ms 5432 KB wrong parameter
9 Incorrect 14 ms 5492 KB wrong parameter
10 Incorrect 16 ms 5416 KB wrong parameter
11 Incorrect 20 ms 5612 KB wrong parameter
12 Incorrect 14 ms 5464 KB wrong parameter
13 Incorrect 35 ms 6068 KB wrong parameter
14 Incorrect 16 ms 5480 KB wrong parameter
15 Incorrect 18 ms 5576 KB wrong parameter
16 Incorrect 31 ms 5932 KB wrong parameter
17 Incorrect 27 ms 5988 KB wrong parameter
18 Incorrect 39 ms 6184 KB wrong parameter
19 Incorrect 23 ms 5880 KB wrong parameter
20 Incorrect 48 ms 6428 KB wrong parameter
21 Incorrect 59 ms 6672 KB wrong parameter
22 Incorrect 31 ms 6188 KB wrong parameter
23 Incorrect 68 ms 6840 KB wrong parameter