oj.uz

Submission #792603

# Submission time Handle Problem Language Result Execution time Memory
792603 2023-07-25T07:20:19 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 144 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+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 144 ms 10172 KB wrong parameter
2 Incorrect 2 ms 4612 KB too many decode_bit() calls
3 Incorrect 15 ms 5352 KB wrong parameter
4 Incorrect 1 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5480 KB wrong parameter
6 Incorrect 20 ms 5536 KB too many decode_bit() calls
7 Incorrect 30 ms 5812 KB wrong parameter
8 Incorrect 15 ms 5444 KB wrong parameter
9 Incorrect 17 ms 5480 KB wrong parameter
10 Incorrect 17 ms 5420 KB wrong parameter
11 Incorrect 19 ms 5436 KB wrong parameter
12 Incorrect 16 ms 5368 KB wrong parameter
13 Incorrect 39 ms 6032 KB wrong parameter
14 Incorrect 17 ms 5544 KB wrong parameter
15 Incorrect 20 ms 5444 KB wrong parameter
16 Incorrect 29 ms 5912 KB wrong parameter
17 Incorrect 32 ms 5732 KB wrong parameter
18 Incorrect 36 ms 6120 KB wrong parameter
19 Incorrect 24 ms 5668 KB wrong parameter
20 Incorrect 54 ms 6360 KB wrong parameter
21 Incorrect 54 ms 6444 KB wrong parameter
22 Incorrect 24 ms 5992 KB wrong parameter
23 Incorrect 65 ms 6752 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 10172 KB wrong parameter
2 Incorrect 2 ms 4612 KB too many decode_bit() calls
3 Incorrect 15 ms 5352 KB wrong parameter
4 Incorrect 1 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5480 KB wrong parameter
6 Incorrect 20 ms 5536 KB too many decode_bit() calls
7 Incorrect 30 ms 5812 KB wrong parameter
8 Incorrect 15 ms 5444 KB wrong parameter
9 Incorrect 17 ms 5480 KB wrong parameter
10 Incorrect 17 ms 5420 KB wrong parameter
11 Incorrect 19 ms 5436 KB wrong parameter
12 Incorrect 16 ms 5368 KB wrong parameter
13 Incorrect 39 ms 6032 KB wrong parameter
14 Incorrect 17 ms 5544 KB wrong parameter
15 Incorrect 20 ms 5444 KB wrong parameter
16 Incorrect 29 ms 5912 KB wrong parameter
17 Incorrect 32 ms 5732 KB wrong parameter
18 Incorrect 36 ms 6120 KB wrong parameter
19 Incorrect 24 ms 5668 KB wrong parameter
20 Incorrect 54 ms 6360 KB wrong parameter
21 Incorrect 54 ms 6444 KB wrong parameter
22 Incorrect 24 ms 5992 KB wrong parameter
23 Incorrect 65 ms 6752 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 10172 KB wrong parameter
2 Incorrect 2 ms 4612 KB too many decode_bit() calls
3 Incorrect 15 ms 5352 KB wrong parameter
4 Incorrect 1 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5480 KB wrong parameter
6 Incorrect 20 ms 5536 KB too many decode_bit() calls
7 Incorrect 30 ms 5812 KB wrong parameter
8 Incorrect 15 ms 5444 KB wrong parameter
9 Incorrect 17 ms 5480 KB wrong parameter
10 Incorrect 17 ms 5420 KB wrong parameter
11 Incorrect 19 ms 5436 KB wrong parameter
12 Incorrect 16 ms 5368 KB wrong parameter
13 Incorrect 39 ms 6032 KB wrong parameter
14 Incorrect 17 ms 5544 KB wrong parameter
15 Incorrect 20 ms 5444 KB wrong parameter
16 Incorrect 29 ms 5912 KB wrong parameter
17 Incorrect 32 ms 5732 KB wrong parameter
18 Incorrect 36 ms 6120 KB wrong parameter
19 Incorrect 24 ms 5668 KB wrong parameter
20 Incorrect 54 ms 6360 KB wrong parameter
21 Incorrect 54 ms 6444 KB wrong parameter
22 Incorrect 24 ms 5992 KB wrong parameter
23 Incorrect 65 ms 6752 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 10172 KB wrong parameter
2 Incorrect 2 ms 4612 KB too many decode_bit() calls
3 Incorrect 15 ms 5352 KB wrong parameter
4 Incorrect 1 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5480 KB wrong parameter
6 Incorrect 20 ms 5536 KB too many decode_bit() calls
7 Incorrect 30 ms 5812 KB wrong parameter
8 Incorrect 15 ms 5444 KB wrong parameter
9 Incorrect 17 ms 5480 KB wrong parameter
10 Incorrect 17 ms 5420 KB wrong parameter
11 Incorrect 19 ms 5436 KB wrong parameter
12 Incorrect 16 ms 5368 KB wrong parameter
13 Incorrect 39 ms 6032 KB wrong parameter
14 Incorrect 17 ms 5544 KB wrong parameter
15 Incorrect 20 ms 5444 KB wrong parameter
16 Incorrect 29 ms 5912 KB wrong parameter
17 Incorrect 32 ms 5732 KB wrong parameter
18 Incorrect 36 ms 6120 KB wrong parameter
19 Incorrect 24 ms 5668 KB wrong parameter
20 Incorrect 54 ms 6360 KB wrong parameter
21 Incorrect 54 ms 6444 KB wrong parameter
22 Incorrect 24 ms 5992 KB wrong parameter
23 Incorrect 65 ms 6752 KB wrong parameter