oj.uz

Submission #718859

# Submission time Handle Problem Language Result Execution time Memory
718859 2023-04-05T02:49:14 Z lam Saveit (IOI10_saveit) C++14
0 / 100
 227 ms 14984 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n;
int par[maxn];
int d[36][maxn];
vector <int> adj[maxn];

void bfs(int rt, bool keep)
{
    queue<int> q;
    fill_n(d[rt],n,-1);
    d[rt][rt] = 0;
    q.push(rt);
    if (keep) par[rt] = rt;
    while (!q.empty())
    {
        int u=q.front(); q.pop();
        for (int v:adj[u])
            if (d[rt][v] == -1)
        {
            d[rt][v] = d[rt][u] + 1;
            if (keep) par[v] = u;
            q.push(v);
        }
    }
}

inline bool checkbit(int i, int j)
{
    return i>j&1;
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n=nv;
    for (int i=0; i<n; i++) adj[i].clear();
    for (int i=0; i<ne; i++)
    {
        int u=v1[i]; int v=v2[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=0; i<nh; i++) bfs(i,(i==0));
    for (int i=0; i<n; i++)
        for (int j=0; j<10; j++)
            encode_bit(checkbit(par[i],j));
    par[n]=par[n+1]=par[n+2]=0;
    for (int rt=1; rt<nh; rt++)
        for (int i=1; i<n; i+=3)
    {
        int u,v;
        u=i; v=par[i];
        int t1 = (d[rt][u]==d[rt][v])?0:((d[rt][u]>d[rt][v])?1:2);
        u=i+1; v=par[i+1];
        int t2 = (d[rt][u]==d[rt][v])?0:((d[rt][u]>d[rt][v])?1:2);
        u=i+2; v=par[i+2];
        int t3 = (d[rt][u]==d[rt][v])?0:((d[rt][u]>d[rt][v])?1:2);
        int T = t1+t2*3+t3*9;
        for (int z=0; z<=5; z++) encode_bit(checkbit(T,z));
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n,rt;
vector <int> adj[maxn];
int par[maxn];
int d[maxn],t[maxn],ans[maxn];
void BFS()
{
    queue<int> q;
    fill_n(d,n,-1);
    d[0] = 0;
    q.push(0);
    while (!q.empty())
    {
        int u=q.front(); q.pop();
        for (int v:adj[u])
            if (d[v]==-1)
        {
            d[v]=d[u]+1;
            q.push(v);
        }
    }
}
void dfs(int x, int p)
{
    for (int i:adj[x])
        if (i!=p)
    {
        if (t[i]==0) ans[i]=ans[x];
        else if (t[i]==1) ans[i]=ans[x]+1;
        else ans[i]=ans[x]-1;
        dfs(i,x);
    }
}
void decode(int nv, int nh) {
    n=nv; rt = 0;
    for (int i=0; i<n; i++)
    {
        int x=0;
        for (int j=0; j<10; j++) if (decode_bit()) x|=(1<<j);
        par[i] = x;
        adj[par[i]].push_back(x);
    }
    for (int i=0; i<n; i++) hops(rt,i,d[i]);
    for (int st = 1; st<nh; st++)
    {
        for (int i=1; i<n; i+=3)
        {
            int T = 0;
            for (int z=0; z<5; z++) if (decode_bit()) T |= (1<<z);
            int t1 = T%3; T/=3;
            int t2 = T%3; T/=3;
            int t3 = T%3; T/=3;
            t[i]=t1; t[i+1]=t2; t[i+2]=t3;
        }
        ans[0] = d[st];
        dfs(0,0);
        for (int i=0; i<n; i++) hops(st,i,ans[i]);
    }
}

Compilation message

encoder.cpp: In function 'bool checkbit(int, int)':
encoder.cpp:33:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   33 |     return i>j&1;
      |            ~^~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 227 ms 14984 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Runtime error 25 ms 9988 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Runtime error 28 ms 10180 KB Execution killed with signal 11
6 Runtime error 36 ms 10084 KB Execution killed with signal 11
7 Runtime error 47 ms 10520 KB Execution killed with signal 11
8 Runtime error 27 ms 9896 KB Execution killed with signal 11
9 Runtime error 22 ms 10180 KB Execution killed with signal 11
10 Runtime error 24 ms 10100 KB Execution killed with signal 11
11 Runtime error 33 ms 10144 KB Execution killed with signal 11
12 Runtime error 22 ms 9996 KB Execution killed with signal 11
13 Runtime error 65 ms 10600 KB Execution killed with signal 11
14 Runtime error 24 ms 10064 KB Execution killed with signal 11
15 Runtime error 28 ms 10220 KB Execution killed with signal 11
16 Runtime error 46 ms 10524 KB Execution killed with signal 11
17 Runtime error 52 ms 10452 KB Execution killed with signal 11
18 Runtime error 68 ms 10808 KB Execution killed with signal 11
19 Runtime error 36 ms 10408 KB Execution killed with signal 11
20 Runtime error 56 ms 11128 KB Execution killed with signal 11
21 Runtime error 67 ms 11132 KB Execution killed with signal 11
22 Runtime error 49 ms 10648 KB Execution killed with signal 11
23 Runtime error 89 ms 11400 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 227 ms 14984 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Runtime error 25 ms 9988 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Runtime error 28 ms 10180 KB Execution killed with signal 11
6 Runtime error 36 ms 10084 KB Execution killed with signal 11
7 Runtime error 47 ms 10520 KB Execution killed with signal 11
8 Runtime error 27 ms 9896 KB Execution killed with signal 11
9 Runtime error 22 ms 10180 KB Execution killed with signal 11
10 Runtime error 24 ms 10100 KB Execution killed with signal 11
11 Runtime error 33 ms 10144 KB Execution killed with signal 11
12 Runtime error 22 ms 9996 KB Execution killed with signal 11
13 Runtime error 65 ms 10600 KB Execution killed with signal 11
14 Runtime error 24 ms 10064 KB Execution killed with signal 11
15 Runtime error 28 ms 10220 KB Execution killed with signal 11
16 Runtime error 46 ms 10524 KB Execution killed with signal 11
17 Runtime error 52 ms 10452 KB Execution killed with signal 11
18 Runtime error 68 ms 10808 KB Execution killed with signal 11
19 Runtime error 36 ms 10408 KB Execution killed with signal 11
20 Runtime error 56 ms 11128 KB Execution killed with signal 11
21 Runtime error 67 ms 11132 KB Execution killed with signal 11
22 Runtime error 49 ms 10648 KB Execution killed with signal 11
23 Runtime error 89 ms 11400 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 227 ms 14984 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Runtime error 25 ms 9988 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Runtime error 28 ms 10180 KB Execution killed with signal 11
6 Runtime error 36 ms 10084 KB Execution killed with signal 11
7 Runtime error 47 ms 10520 KB Execution killed with signal 11
8 Runtime error 27 ms 9896 KB Execution killed with signal 11
9 Runtime error 22 ms 10180 KB Execution killed with signal 11
10 Runtime error 24 ms 10100 KB Execution killed with signal 11
11 Runtime error 33 ms 10144 KB Execution killed with signal 11
12 Runtime error 22 ms 9996 KB Execution killed with signal 11
13 Runtime error 65 ms 10600 KB Execution killed with signal 11
14 Runtime error 24 ms 10064 KB Execution killed with signal 11
15 Runtime error 28 ms 10220 KB Execution killed with signal 11
16 Runtime error 46 ms 10524 KB Execution killed with signal 11
17 Runtime error 52 ms 10452 KB Execution killed with signal 11
18 Runtime error 68 ms 10808 KB Execution killed with signal 11
19 Runtime error 36 ms 10408 KB Execution killed with signal 11
20 Runtime error 56 ms 11128 KB Execution killed with signal 11
21 Runtime error 67 ms 11132 KB Execution killed with signal 11
22 Runtime error 49 ms 10648 KB Execution killed with signal 11
23 Runtime error 89 ms 11400 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 227 ms 14984 KB Execution killed with signal 11
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Runtime error 25 ms 9988 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB Output isn't correct
5 Runtime error 28 ms 10180 KB Execution killed with signal 11
6 Runtime error 36 ms 10084 KB Execution killed with signal 11
7 Runtime error 47 ms 10520 KB Execution killed with signal 11
8 Runtime error 27 ms 9896 KB Execution killed with signal 11
9 Runtime error 22 ms 10180 KB Execution killed with signal 11
10 Runtime error 24 ms 10100 KB Execution killed with signal 11
11 Runtime error 33 ms 10144 KB Execution killed with signal 11
12 Runtime error 22 ms 9996 KB Execution killed with signal 11
13 Runtime error 65 ms 10600 KB Execution killed with signal 11
14 Runtime error 24 ms 10064 KB Execution killed with signal 11
15 Runtime error 28 ms 10220 KB Execution killed with signal 11
16 Runtime error 46 ms 10524 KB Execution killed with signal 11
17 Runtime error 52 ms 10452 KB Execution killed with signal 11
18 Runtime error 68 ms 10808 KB Execution killed with signal 11
19 Runtime error 36 ms 10408 KB Execution killed with signal 11
20 Runtime error 56 ms 11128 KB Execution killed with signal 11
21 Runtime error 67 ms 11132 KB Execution killed with signal 11
22 Runtime error 49 ms 10648 KB Execution killed with signal 11
23 Runtime error 89 ms 11400 KB Execution killed with signal 11