oj.uz

Submission #792612

# Submission time Handle Problem Language Result Execution time Memory
792612 2023-07-25T07:24:58 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 179 ms 10172 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);
        iota(p.begin(),p.end(),0);
        sz.resize(n);
        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 179 ms 10172 KB wrong parameter
2 Incorrect 1 ms 4604 KB too many decode_bit() calls
3 Incorrect 15 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5412 KB wrong parameter
6 Incorrect 18 ms 5588 KB too many decode_bit() calls
7 Incorrect 35 ms 5864 KB wrong parameter
8 Incorrect 17 ms 5372 KB wrong parameter
9 Incorrect 17 ms 5408 KB wrong parameter
10 Incorrect 16 ms 5384 KB wrong parameter
11 Incorrect 17 ms 5604 KB wrong parameter
12 Incorrect 15 ms 5392 KB wrong parameter
13 Incorrect 41 ms 5988 KB wrong parameter
14 Incorrect 19 ms 5560 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 41 ms 6056 KB wrong parameter
17 Incorrect 33 ms 5796 KB wrong parameter
18 Incorrect 34 ms 6124 KB wrong parameter
19 Incorrect 30 ms 5772 KB wrong parameter
20 Incorrect 37 ms 6564 KB wrong parameter
21 Incorrect 70 ms 6440 KB wrong parameter
22 Incorrect 37 ms 5972 KB wrong parameter
23 Incorrect 47 ms 6844 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 10172 KB wrong parameter
2 Incorrect 1 ms 4604 KB too many decode_bit() calls
3 Incorrect 15 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5412 KB wrong parameter
6 Incorrect 18 ms 5588 KB too many decode_bit() calls
7 Incorrect 35 ms 5864 KB wrong parameter
8 Incorrect 17 ms 5372 KB wrong parameter
9 Incorrect 17 ms 5408 KB wrong parameter
10 Incorrect 16 ms 5384 KB wrong parameter
11 Incorrect 17 ms 5604 KB wrong parameter
12 Incorrect 15 ms 5392 KB wrong parameter
13 Incorrect 41 ms 5988 KB wrong parameter
14 Incorrect 19 ms 5560 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 41 ms 6056 KB wrong parameter
17 Incorrect 33 ms 5796 KB wrong parameter
18 Incorrect 34 ms 6124 KB wrong parameter
19 Incorrect 30 ms 5772 KB wrong parameter
20 Incorrect 37 ms 6564 KB wrong parameter
21 Incorrect 70 ms 6440 KB wrong parameter
22 Incorrect 37 ms 5972 KB wrong parameter
23 Incorrect 47 ms 6844 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 10172 KB wrong parameter
2 Incorrect 1 ms 4604 KB too many decode_bit() calls
3 Incorrect 15 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5412 KB wrong parameter
6 Incorrect 18 ms 5588 KB too many decode_bit() calls
7 Incorrect 35 ms 5864 KB wrong parameter
8 Incorrect 17 ms 5372 KB wrong parameter
9 Incorrect 17 ms 5408 KB wrong parameter
10 Incorrect 16 ms 5384 KB wrong parameter
11 Incorrect 17 ms 5604 KB wrong parameter
12 Incorrect 15 ms 5392 KB wrong parameter
13 Incorrect 41 ms 5988 KB wrong parameter
14 Incorrect 19 ms 5560 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 41 ms 6056 KB wrong parameter
17 Incorrect 33 ms 5796 KB wrong parameter
18 Incorrect 34 ms 6124 KB wrong parameter
19 Incorrect 30 ms 5772 KB wrong parameter
20 Incorrect 37 ms 6564 KB wrong parameter
21 Incorrect 70 ms 6440 KB wrong parameter
22 Incorrect 37 ms 5972 KB wrong parameter
23 Incorrect 47 ms 6844 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 10172 KB wrong parameter
2 Incorrect 1 ms 4604 KB too many decode_bit() calls
3 Incorrect 15 ms 5356 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5412 KB wrong parameter
6 Incorrect 18 ms 5588 KB too many decode_bit() calls
7 Incorrect 35 ms 5864 KB wrong parameter
8 Incorrect 17 ms 5372 KB wrong parameter
9 Incorrect 17 ms 5408 KB wrong parameter
10 Incorrect 16 ms 5384 KB wrong parameter
11 Incorrect 17 ms 5604 KB wrong parameter
12 Incorrect 15 ms 5392 KB wrong parameter
13 Incorrect 41 ms 5988 KB wrong parameter
14 Incorrect 19 ms 5560 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 41 ms 6056 KB wrong parameter
17 Incorrect 33 ms 5796 KB wrong parameter
18 Incorrect 34 ms 6124 KB wrong parameter
19 Incorrect 30 ms 5772 KB wrong parameter
20 Incorrect 37 ms 6564 KB wrong parameter
21 Incorrect 70 ms 6440 KB wrong parameter
22 Incorrect 37 ms 5972 KB wrong parameter
23 Incorrect 47 ms 6844 KB wrong parameter