oj.uz

Submission #792602

# Submission time Handle Problem Language Result Execution time Memory
792602 2023-07-25T07:19:15 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 149 ms 10268 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

struct dsu{
    vector<int>p,sz;
    dsu(int n){
        p.resize(n+1);
        iota(p.begin(),p.end(),0);
        sz.resize(n+1);
        fill(sz.begin(),sz.end(),1);
    }
    int find(ll x){
        if(p[x]==x){
            return x;
        }
        return p[x]=find(p[x]);
    }
    bool same(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return true;
        }
        else{
            return false;
        }
    }
    void merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            sz[x]+=sz[y];
            p[y]=x;
        }
    }
};

void encode(int N,int H,int P,int A[],int B[]){
    vector<int>adj[N];
    for(int i=0;i<P;i++){
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    dsu ds(N);
    vector<int>d[N],used(N,0);
    for(int i=0;i<P;i++){
        if(ds.same(A[i],B[i])==false){
            ds.merge(A[i],B[i]);
            d[A[i]].pb(B[i]);
            d[B[i]].pb(A[i]);
        }
    }
    vector<int>ord;
    function <void(int)> dfs=[&](int x){
        used[x]=1;
        ord.pb(x);
        for(auto y:d[x]){
            if(used[y]==0){
                dfs(y);
            }
        }
    };
    dfs(0);
    for(auto x:ord){
        for(int i=0;i<10;i++){
            encode_bit(x%2);
            x/=2;
        }
    }
    int dist[N];
    for(int i=0;i<H;i++){
        fill(dist,dist+N,-1);
        queue<int>q;
        dist[i]=0;
        q.push(i);
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(auto y:adj[x]){
                if(dist[y]==-1){
                    dist[y]=dist[x]+1;
                    q.push(y);
                }
            }
        }
        for(int j=0;j<N;j++){
            if(j==0){
                int y=dist[ord[0]];
                for(int k=0;k<10;k++){
                    encode_bit(y%2);
                    y/=2;
                }
            }
            else{
                if(dist[ord[j]]==dist[ord[j-1]]-1){
                    encode_bit(0);
                    encode_bit(0);
                }
                if(dist[ord[j]]==dist[ord[j-1]]){
                    encode_bit(0);
                    encode_bit(1);
                }
                if(dist[ord[j]]==dist[ord[j-1]]+1){
                    encode_bit(1);
                    encode_bit(1);
                }
            }
        }
    }
}
#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
 
void decode(int N,int H){
    int ver[N];
    for(int i=0;i<N;i++){
        ver[i]=0;
        for(int j=0;j<10;j++){
            ver[i]+=(1<<j)*decode_bit();
        }
    }
    for(int i=0;i<H;i++){
        int dist=0;
        for(int j=0;j<10;j++){
            dist+=(1<<j)*decode_bit();
        }
        hops(i,ver[0],dist);
        for(int j=1;j<N;j++){
            int x=0;
            x+=decode_bit();
            x+=decode_bit();
            if(x==0){
                dist--;
            }
            if(x==2){
                dist++;
            }
            hops(i,ver[j],dist);
        }
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 10268 KB wrong parameter
2 Incorrect 1 ms 4476 KB too many decode_bit() calls
3 Incorrect 15 ms 5364 KB wrong parameter
4 Incorrect 1 ms 4616 KB wrong parameter
5 Incorrect 16 ms 5596 KB wrong parameter
6 Incorrect 19 ms 5596 KB too many decode_bit() calls
7 Incorrect 28 ms 5944 KB wrong parameter
8 Incorrect 15 ms 5372 KB wrong parameter
9 Incorrect 18 ms 5480 KB wrong parameter
10 Incorrect 18 ms 5404 KB wrong parameter
11 Incorrect 23 ms 5512 KB wrong parameter
12 Incorrect 18 ms 5384 KB wrong parameter
13 Incorrect 32 ms 5992 KB wrong parameter
14 Incorrect 19 ms 5484 KB wrong parameter
15 Incorrect 17 ms 5520 KB wrong parameter
16 Incorrect 27 ms 5996 KB wrong parameter
17 Incorrect 27 ms 5864 KB wrong parameter
18 Incorrect 38 ms 6152 KB wrong parameter
19 Incorrect 24 ms 5732 KB wrong parameter
20 Incorrect 49 ms 6424 KB wrong parameter
21 Incorrect 51 ms 6512 KB wrong parameter
22 Incorrect 39 ms 6048 KB wrong parameter
23 Incorrect 47 ms 6820 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 10268 KB wrong parameter
2 Incorrect 1 ms 4476 KB too many decode_bit() calls
3 Incorrect 15 ms 5364 KB wrong parameter
4 Incorrect 1 ms 4616 KB wrong parameter
5 Incorrect 16 ms 5596 KB wrong parameter
6 Incorrect 19 ms 5596 KB too many decode_bit() calls
7 Incorrect 28 ms 5944 KB wrong parameter
8 Incorrect 15 ms 5372 KB wrong parameter
9 Incorrect 18 ms 5480 KB wrong parameter
10 Incorrect 18 ms 5404 KB wrong parameter
11 Incorrect 23 ms 5512 KB wrong parameter
12 Incorrect 18 ms 5384 KB wrong parameter
13 Incorrect 32 ms 5992 KB wrong parameter
14 Incorrect 19 ms 5484 KB wrong parameter
15 Incorrect 17 ms 5520 KB wrong parameter
16 Incorrect 27 ms 5996 KB wrong parameter
17 Incorrect 27 ms 5864 KB wrong parameter
18 Incorrect 38 ms 6152 KB wrong parameter
19 Incorrect 24 ms 5732 KB wrong parameter
20 Incorrect 49 ms 6424 KB wrong parameter
21 Incorrect 51 ms 6512 KB wrong parameter
22 Incorrect 39 ms 6048 KB wrong parameter
23 Incorrect 47 ms 6820 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 10268 KB wrong parameter
2 Incorrect 1 ms 4476 KB too many decode_bit() calls
3 Incorrect 15 ms 5364 KB wrong parameter
4 Incorrect 1 ms 4616 KB wrong parameter
5 Incorrect 16 ms 5596 KB wrong parameter
6 Incorrect 19 ms 5596 KB too many decode_bit() calls
7 Incorrect 28 ms 5944 KB wrong parameter
8 Incorrect 15 ms 5372 KB wrong parameter
9 Incorrect 18 ms 5480 KB wrong parameter
10 Incorrect 18 ms 5404 KB wrong parameter
11 Incorrect 23 ms 5512 KB wrong parameter
12 Incorrect 18 ms 5384 KB wrong parameter
13 Incorrect 32 ms 5992 KB wrong parameter
14 Incorrect 19 ms 5484 KB wrong parameter
15 Incorrect 17 ms 5520 KB wrong parameter
16 Incorrect 27 ms 5996 KB wrong parameter
17 Incorrect 27 ms 5864 KB wrong parameter
18 Incorrect 38 ms 6152 KB wrong parameter
19 Incorrect 24 ms 5732 KB wrong parameter
20 Incorrect 49 ms 6424 KB wrong parameter
21 Incorrect 51 ms 6512 KB wrong parameter
22 Incorrect 39 ms 6048 KB wrong parameter
23 Incorrect 47 ms 6820 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 10268 KB wrong parameter
2 Incorrect 1 ms 4476 KB too many decode_bit() calls
3 Incorrect 15 ms 5364 KB wrong parameter
4 Incorrect 1 ms 4616 KB wrong parameter
5 Incorrect 16 ms 5596 KB wrong parameter
6 Incorrect 19 ms 5596 KB too many decode_bit() calls
7 Incorrect 28 ms 5944 KB wrong parameter
8 Incorrect 15 ms 5372 KB wrong parameter
9 Incorrect 18 ms 5480 KB wrong parameter
10 Incorrect 18 ms 5404 KB wrong parameter
11 Incorrect 23 ms 5512 KB wrong parameter
12 Incorrect 18 ms 5384 KB wrong parameter
13 Incorrect 32 ms 5992 KB wrong parameter
14 Incorrect 19 ms 5484 KB wrong parameter
15 Incorrect 17 ms 5520 KB wrong parameter
16 Incorrect 27 ms 5996 KB wrong parameter
17 Incorrect 27 ms 5864 KB wrong parameter
18 Incorrect 38 ms 6152 KB wrong parameter
19 Incorrect 24 ms 5732 KB wrong parameter
20 Incorrect 49 ms 6424 KB wrong parameter
21 Incorrect 51 ms 6512 KB wrong parameter
22 Incorrect 39 ms 6048 KB wrong parameter
23 Incorrect 47 ms 6820 KB wrong parameter