oj.uz

Submission #792627

# Submission time Handle Problem Language Result Execution time Memory
792627 2023-07-25T07:35:37 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 193 ms 10228 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);
    assert(ord.size()==N);
    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);
        }
    }
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from encoder.cpp:1:
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:76:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |     assert(ord.size()==N);
      |            ~~~~~~~~~~^~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 10228 KB wrong parameter
2 Incorrect 1 ms 4472 KB too many decode_bit() calls
3 Incorrect 16 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 17 ms 5492 KB wrong parameter
6 Incorrect 18 ms 5528 KB too many decode_bit() calls
7 Incorrect 33 ms 5852 KB wrong parameter
8 Incorrect 17 ms 5340 KB wrong parameter
9 Incorrect 17 ms 5364 KB wrong parameter
10 Incorrect 20 ms 5448 KB wrong parameter
11 Incorrect 17 ms 5536 KB wrong parameter
12 Incorrect 15 ms 5352 KB wrong parameter
13 Incorrect 43 ms 5940 KB wrong parameter
14 Incorrect 20 ms 5408 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 28 ms 5956 KB wrong parameter
17 Incorrect 36 ms 5776 KB wrong parameter
18 Incorrect 38 ms 6112 KB wrong parameter
19 Incorrect 25 ms 5768 KB wrong parameter
20 Incorrect 39 ms 6560 KB wrong parameter
21 Incorrect 68 ms 6596 KB wrong parameter
22 Incorrect 64 ms 6128 KB wrong parameter
23 Incorrect 57 ms 6680 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 10228 KB wrong parameter
2 Incorrect 1 ms 4472 KB too many decode_bit() calls
3 Incorrect 16 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 17 ms 5492 KB wrong parameter
6 Incorrect 18 ms 5528 KB too many decode_bit() calls
7 Incorrect 33 ms 5852 KB wrong parameter
8 Incorrect 17 ms 5340 KB wrong parameter
9 Incorrect 17 ms 5364 KB wrong parameter
10 Incorrect 20 ms 5448 KB wrong parameter
11 Incorrect 17 ms 5536 KB wrong parameter
12 Incorrect 15 ms 5352 KB wrong parameter
13 Incorrect 43 ms 5940 KB wrong parameter
14 Incorrect 20 ms 5408 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 28 ms 5956 KB wrong parameter
17 Incorrect 36 ms 5776 KB wrong parameter
18 Incorrect 38 ms 6112 KB wrong parameter
19 Incorrect 25 ms 5768 KB wrong parameter
20 Incorrect 39 ms 6560 KB wrong parameter
21 Incorrect 68 ms 6596 KB wrong parameter
22 Incorrect 64 ms 6128 KB wrong parameter
23 Incorrect 57 ms 6680 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 10228 KB wrong parameter
2 Incorrect 1 ms 4472 KB too many decode_bit() calls
3 Incorrect 16 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 17 ms 5492 KB wrong parameter
6 Incorrect 18 ms 5528 KB too many decode_bit() calls
7 Incorrect 33 ms 5852 KB wrong parameter
8 Incorrect 17 ms 5340 KB wrong parameter
9 Incorrect 17 ms 5364 KB wrong parameter
10 Incorrect 20 ms 5448 KB wrong parameter
11 Incorrect 17 ms 5536 KB wrong parameter
12 Incorrect 15 ms 5352 KB wrong parameter
13 Incorrect 43 ms 5940 KB wrong parameter
14 Incorrect 20 ms 5408 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 28 ms 5956 KB wrong parameter
17 Incorrect 36 ms 5776 KB wrong parameter
18 Incorrect 38 ms 6112 KB wrong parameter
19 Incorrect 25 ms 5768 KB wrong parameter
20 Incorrect 39 ms 6560 KB wrong parameter
21 Incorrect 68 ms 6596 KB wrong parameter
22 Incorrect 64 ms 6128 KB wrong parameter
23 Incorrect 57 ms 6680 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 10228 KB wrong parameter
2 Incorrect 1 ms 4472 KB too many decode_bit() calls
3 Incorrect 16 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 17 ms 5492 KB wrong parameter
6 Incorrect 18 ms 5528 KB too many decode_bit() calls
7 Incorrect 33 ms 5852 KB wrong parameter
8 Incorrect 17 ms 5340 KB wrong parameter
9 Incorrect 17 ms 5364 KB wrong parameter
10 Incorrect 20 ms 5448 KB wrong parameter
11 Incorrect 17 ms 5536 KB wrong parameter
12 Incorrect 15 ms 5352 KB wrong parameter
13 Incorrect 43 ms 5940 KB wrong parameter
14 Incorrect 20 ms 5408 KB wrong parameter
15 Incorrect 19 ms 5500 KB wrong parameter
16 Incorrect 28 ms 5956 KB wrong parameter
17 Incorrect 36 ms 5776 KB wrong parameter
18 Incorrect 38 ms 6112 KB wrong parameter
19 Incorrect 25 ms 5768 KB wrong parameter
20 Incorrect 39 ms 6560 KB wrong parameter
21 Incorrect 68 ms 6596 KB wrong parameter
22 Incorrect 64 ms 6128 KB wrong parameter
23 Incorrect 57 ms 6680 KB wrong parameter