oj.uz

Submission #796930

# Submission time Handle Problem Language Result Execution time Memory
796930 2023-07-28T23:30:46 Z I_Love_EliskaM_ Saveit (IOI10_saveit) C++14
0 / 100
 214 ms 10284 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;
             }
          }
         restore(v,u);
       }
    }
     
    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 214 ms 10284 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 18 ms 5500 KB wrong parameter
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Incorrect 18 ms 5536 KB wrong parameter
6 Incorrect 17 ms 5656 KB wrong parameter
7 Incorrect 36 ms 5992 KB wrong parameter
8 Incorrect 13 ms 5500 KB wrong parameter
9 Incorrect 15 ms 5504 KB wrong parameter
10 Incorrect 18 ms 5500 KB wrong parameter
11 Incorrect 20 ms 5496 KB wrong parameter
12 Incorrect 19 ms 5492 KB wrong parameter
13 Incorrect 33 ms 6192 KB wrong parameter
14 Incorrect 19 ms 5520 KB wrong parameter
15 Incorrect 15 ms 5628 KB wrong parameter
16 Incorrect 30 ms 5968 KB wrong parameter
17 Incorrect 28 ms 5896 KB wrong parameter
18 Incorrect 37 ms 6236 KB wrong parameter
19 Incorrect 28 ms 5880 KB wrong parameter
20 Incorrect 44 ms 6544 KB wrong parameter
21 Incorrect 49 ms 6652 KB wrong parameter
22 Incorrect 34 ms 6184 KB wrong parameter
23 Incorrect 57 ms 6796 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 10284 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 18 ms 5500 KB wrong parameter
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Incorrect 18 ms 5536 KB wrong parameter
6 Incorrect 17 ms 5656 KB wrong parameter
7 Incorrect 36 ms 5992 KB wrong parameter
8 Incorrect 13 ms 5500 KB wrong parameter
9 Incorrect 15 ms 5504 KB wrong parameter
10 Incorrect 18 ms 5500 KB wrong parameter
11 Incorrect 20 ms 5496 KB wrong parameter
12 Incorrect 19 ms 5492 KB wrong parameter
13 Incorrect 33 ms 6192 KB wrong parameter
14 Incorrect 19 ms 5520 KB wrong parameter
15 Incorrect 15 ms 5628 KB wrong parameter
16 Incorrect 30 ms 5968 KB wrong parameter
17 Incorrect 28 ms 5896 KB wrong parameter
18 Incorrect 37 ms 6236 KB wrong parameter
19 Incorrect 28 ms 5880 KB wrong parameter
20 Incorrect 44 ms 6544 KB wrong parameter
21 Incorrect 49 ms 6652 KB wrong parameter
22 Incorrect 34 ms 6184 KB wrong parameter
23 Incorrect 57 ms 6796 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 10284 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 18 ms 5500 KB wrong parameter
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Incorrect 18 ms 5536 KB wrong parameter
6 Incorrect 17 ms 5656 KB wrong parameter
7 Incorrect 36 ms 5992 KB wrong parameter
8 Incorrect 13 ms 5500 KB wrong parameter
9 Incorrect 15 ms 5504 KB wrong parameter
10 Incorrect 18 ms 5500 KB wrong parameter
11 Incorrect 20 ms 5496 KB wrong parameter
12 Incorrect 19 ms 5492 KB wrong parameter
13 Incorrect 33 ms 6192 KB wrong parameter
14 Incorrect 19 ms 5520 KB wrong parameter
15 Incorrect 15 ms 5628 KB wrong parameter
16 Incorrect 30 ms 5968 KB wrong parameter
17 Incorrect 28 ms 5896 KB wrong parameter
18 Incorrect 37 ms 6236 KB wrong parameter
19 Incorrect 28 ms 5880 KB wrong parameter
20 Incorrect 44 ms 6544 KB wrong parameter
21 Incorrect 49 ms 6652 KB wrong parameter
22 Incorrect 34 ms 6184 KB wrong parameter
23 Incorrect 57 ms 6796 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 10284 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 18 ms 5500 KB wrong parameter
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Incorrect 18 ms 5536 KB wrong parameter
6 Incorrect 17 ms 5656 KB wrong parameter
7 Incorrect 36 ms 5992 KB wrong parameter
8 Incorrect 13 ms 5500 KB wrong parameter
9 Incorrect 15 ms 5504 KB wrong parameter
10 Incorrect 18 ms 5500 KB wrong parameter
11 Incorrect 20 ms 5496 KB wrong parameter
12 Incorrect 19 ms 5492 KB wrong parameter
13 Incorrect 33 ms 6192 KB wrong parameter
14 Incorrect 19 ms 5520 KB wrong parameter
15 Incorrect 15 ms 5628 KB wrong parameter
16 Incorrect 30 ms 5968 KB wrong parameter
17 Incorrect 28 ms 5896 KB wrong parameter
18 Incorrect 37 ms 6236 KB wrong parameter
19 Incorrect 28 ms 5880 KB wrong parameter
20 Incorrect 44 ms 6544 KB wrong parameter
21 Incorrect 49 ms 6652 KB wrong parameter
22 Incorrect 34 ms 6184 KB wrong parameter
23 Incorrect 57 ms 6796 KB wrong parameter