oj.uz

Submission #576778

# Submission time Handle Problem Language Result Execution time Memory
576778 2022-06-13T13:13:38 Z zaneyu Saveit (IOI10_saveit) C++14
0 / 100
 255 ms 10500 KB 
#include "grader.h"
#include "encoder.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
namespace {
    vector<int> v[1005],g[1005];
    int dist[1005];
    void send(int x){
        REP(i,10){
            encode_bit((x>>(9-i))&1);
        }
    }
    int par[1005];
    bool vis[1005];
    void dfs(int u,int p){
        par[u]=p;
        vis[u]=1;
        for(int x:v[u]){
            if(!vis[x]) dfs(x,u);
        }
    }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
    REP(i,ne){
        v[v1[i]].pb(v2[i]);
        v[v2[i]].pb(v1[i]);
    }
    dfs(0,-1);
    REP1(i,nv-1){
        send(par[i]);
    }
    vector<pii> eds;
    REP(i,nh){
        REP(j,nv) dist[j]=1e9;
        dist[i]=0;
        queue<int> q;
        q.push(i);
        while(sz(q)){
            int z=q.front();
            q.pop();
            for(int x:v[z]){
                if(dist[x]>dist[z]+1){
                    g[z].pb(x);
                    dist[x]=dist[z]+1;
                    q.push(x);
                }
            }
        }
        send(dist[0]);
        vector<int> vv;
        REP1(j,nv-1){
            vv.pb(1+dist[j]-dist[par[j]]);
        }
        while(sz(vv)%3) vv.pb(0);
        REP(i,sz(vv)/3){
            int x=vv[i]+vv[i+1]*3+vv[i+2]*9;
            REP(j,5) encode_bit((x>>(4-j))&1);
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
namespace {
int get(){
    int x=0;
    REP(i,10){
        x=x*2+decode_bit();
    }
    return x;
}
vector<int> v[1005];
int par[1005];
int ans[1005];
int df[1005];
void dfs(int u){
    for(int x:v[u]){
        ans[x]=ans[u]+df[x]-1;
        dfs(x);
    }
}
}
void decode(int nv, int nh) {
    REP1(i,nv-1){
        par[i]=get();
        v[par[i]].pb(i);
    }
    REP(i,nh){
        ans[0]=get();
        int it=1;
        REP(i,(nv+2)/3){
            int x=0;
            REP(i,5){
                x=x*2+decode_bit();
            }
            REP(j,3){
                df[it++]=x%3;
                x/=3;
            }
        }
        dfs(0);
        REP(j,nv) hops(i,j,ans[j]); 
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 10500 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4584 KB wrong parameter
5 Incorrect 18 ms 5608 KB wrong parameter
6 Incorrect 20 ms 5880 KB wrong parameter
7 Incorrect 35 ms 6088 KB wrong parameter
8 Incorrect 23 ms 5692 KB wrong parameter
9 Incorrect 19 ms 5756 KB wrong parameter
10 Incorrect 22 ms 5640 KB too many decode_bit() calls
11 Incorrect 27 ms 5820 KB too many decode_bit() calls
12 Incorrect 16 ms 5764 KB wrong parameter
13 Incorrect 42 ms 6368 KB wrong parameter
14 Incorrect 22 ms 5796 KB wrong parameter
15 Incorrect 19 ms 5864 KB wrong parameter
16 Incorrect 46 ms 6220 KB wrong parameter
17 Incorrect 34 ms 6180 KB wrong parameter
18 Incorrect 47 ms 6472 KB wrong parameter
19 Incorrect 28 ms 6124 KB wrong parameter
20 Incorrect 48 ms 6692 KB wrong parameter
21 Incorrect 59 ms 6844 KB wrong parameter
22 Incorrect 33 ms 6420 KB wrong parameter
23 Incorrect 62 ms 7264 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 10500 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4584 KB wrong parameter
5 Incorrect 18 ms 5608 KB wrong parameter
6 Incorrect 20 ms 5880 KB wrong parameter
7 Incorrect 35 ms 6088 KB wrong parameter
8 Incorrect 23 ms 5692 KB wrong parameter
9 Incorrect 19 ms 5756 KB wrong parameter
10 Incorrect 22 ms 5640 KB too many decode_bit() calls
11 Incorrect 27 ms 5820 KB too many decode_bit() calls
12 Incorrect 16 ms 5764 KB wrong parameter
13 Incorrect 42 ms 6368 KB wrong parameter
14 Incorrect 22 ms 5796 KB wrong parameter
15 Incorrect 19 ms 5864 KB wrong parameter
16 Incorrect 46 ms 6220 KB wrong parameter
17 Incorrect 34 ms 6180 KB wrong parameter
18 Incorrect 47 ms 6472 KB wrong parameter
19 Incorrect 28 ms 6124 KB wrong parameter
20 Incorrect 48 ms 6692 KB wrong parameter
21 Incorrect 59 ms 6844 KB wrong parameter
22 Incorrect 33 ms 6420 KB wrong parameter
23 Incorrect 62 ms 7264 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 10500 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4584 KB wrong parameter
5 Incorrect 18 ms 5608 KB wrong parameter
6 Incorrect 20 ms 5880 KB wrong parameter
7 Incorrect 35 ms 6088 KB wrong parameter
8 Incorrect 23 ms 5692 KB wrong parameter
9 Incorrect 19 ms 5756 KB wrong parameter
10 Incorrect 22 ms 5640 KB too many decode_bit() calls
11 Incorrect 27 ms 5820 KB too many decode_bit() calls
12 Incorrect 16 ms 5764 KB wrong parameter
13 Incorrect 42 ms 6368 KB wrong parameter
14 Incorrect 22 ms 5796 KB wrong parameter
15 Incorrect 19 ms 5864 KB wrong parameter
16 Incorrect 46 ms 6220 KB wrong parameter
17 Incorrect 34 ms 6180 KB wrong parameter
18 Incorrect 47 ms 6472 KB wrong parameter
19 Incorrect 28 ms 6124 KB wrong parameter
20 Incorrect 48 ms 6692 KB wrong parameter
21 Incorrect 59 ms 6844 KB wrong parameter
22 Incorrect 33 ms 6420 KB wrong parameter
23 Incorrect 62 ms 7264 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 10500 KB wrong parameter
2 Incorrect 2 ms 4604 KB Output isn't correct
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4584 KB wrong parameter
5 Incorrect 18 ms 5608 KB wrong parameter
6 Incorrect 20 ms 5880 KB wrong parameter
7 Incorrect 35 ms 6088 KB wrong parameter
8 Incorrect 23 ms 5692 KB wrong parameter
9 Incorrect 19 ms 5756 KB wrong parameter
10 Incorrect 22 ms 5640 KB too many decode_bit() calls
11 Incorrect 27 ms 5820 KB too many decode_bit() calls
12 Incorrect 16 ms 5764 KB wrong parameter
13 Incorrect 42 ms 6368 KB wrong parameter
14 Incorrect 22 ms 5796 KB wrong parameter
15 Incorrect 19 ms 5864 KB wrong parameter
16 Incorrect 46 ms 6220 KB wrong parameter
17 Incorrect 34 ms 6180 KB wrong parameter
18 Incorrect 47 ms 6472 KB wrong parameter
19 Incorrect 28 ms 6124 KB wrong parameter
20 Incorrect 48 ms 6692 KB wrong parameter
21 Incorrect 59 ms 6844 KB wrong parameter
22 Incorrect 33 ms 6420 KB wrong parameter
23 Incorrect 62 ms 7264 KB wrong parameter