oj.uz

Submission #792721

# Submission time Handle Problem Language Result Execution time Memory
792721 2023-07-25T08:16:14 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 166 ms 10120 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>par(N);
    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(int y:d[x]){
            if(used[y]==0){
                par[y]=x;
                dfs(y);
            }
        }
    };
    par[0]=-1;
    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[par[ord[j]]]-1){
                    encode_bit(0);
                    encode_bit(0);
                }
                if(dist[ord[j]]==dist[par[ord[j]]]){
                    encode_bit(0);
                    encode_bit(1);
                }
                if(dist[ord[j]]==dist[par[ord[j]]]+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 166 ms 10120 KB wrong parameter
2 Incorrect 1 ms 4604 KB wrong parameter
3 Incorrect 17 ms 5376 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5728 KB wrong parameter
6 Incorrect 22 ms 5520 KB wrong parameter
7 Incorrect 37 ms 5852 KB wrong parameter
8 Incorrect 18 ms 5372 KB wrong parameter
9 Incorrect 19 ms 5660 KB Output isn't correct
10 Incorrect 19 ms 5632 KB Output isn't correct
11 Incorrect 19 ms 5608 KB wrong parameter
12 Incorrect 17 ms 5352 KB wrong parameter
13 Incorrect 52 ms 6156 KB wrong parameter
14 Incorrect 17 ms 5436 KB wrong parameter
15 Incorrect 19 ms 5544 KB wrong parameter
16 Incorrect 30 ms 5884 KB wrong parameter
17 Incorrect 34 ms 5944 KB wrong parameter
18 Incorrect 44 ms 6112 KB wrong parameter
19 Incorrect 23 ms 5752 KB wrong parameter
20 Incorrect 39 ms 6648 KB wrong parameter
21 Incorrect 43 ms 6424 KB wrong parameter
22 Incorrect 30 ms 6124 KB wrong parameter
23 Incorrect 61 ms 6668 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 10120 KB wrong parameter
2 Incorrect 1 ms 4604 KB wrong parameter
3 Incorrect 17 ms 5376 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5728 KB wrong parameter
6 Incorrect 22 ms 5520 KB wrong parameter
7 Incorrect 37 ms 5852 KB wrong parameter
8 Incorrect 18 ms 5372 KB wrong parameter
9 Incorrect 19 ms 5660 KB Output isn't correct
10 Incorrect 19 ms 5632 KB Output isn't correct
11 Incorrect 19 ms 5608 KB wrong parameter
12 Incorrect 17 ms 5352 KB wrong parameter
13 Incorrect 52 ms 6156 KB wrong parameter
14 Incorrect 17 ms 5436 KB wrong parameter
15 Incorrect 19 ms 5544 KB wrong parameter
16 Incorrect 30 ms 5884 KB wrong parameter
17 Incorrect 34 ms 5944 KB wrong parameter
18 Incorrect 44 ms 6112 KB wrong parameter
19 Incorrect 23 ms 5752 KB wrong parameter
20 Incorrect 39 ms 6648 KB wrong parameter
21 Incorrect 43 ms 6424 KB wrong parameter
22 Incorrect 30 ms 6124 KB wrong parameter
23 Incorrect 61 ms 6668 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 10120 KB wrong parameter
2 Incorrect 1 ms 4604 KB wrong parameter
3 Incorrect 17 ms 5376 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5728 KB wrong parameter
6 Incorrect 22 ms 5520 KB wrong parameter
7 Incorrect 37 ms 5852 KB wrong parameter
8 Incorrect 18 ms 5372 KB wrong parameter
9 Incorrect 19 ms 5660 KB Output isn't correct
10 Incorrect 19 ms 5632 KB Output isn't correct
11 Incorrect 19 ms 5608 KB wrong parameter
12 Incorrect 17 ms 5352 KB wrong parameter
13 Incorrect 52 ms 6156 KB wrong parameter
14 Incorrect 17 ms 5436 KB wrong parameter
15 Incorrect 19 ms 5544 KB wrong parameter
16 Incorrect 30 ms 5884 KB wrong parameter
17 Incorrect 34 ms 5944 KB wrong parameter
18 Incorrect 44 ms 6112 KB wrong parameter
19 Incorrect 23 ms 5752 KB wrong parameter
20 Incorrect 39 ms 6648 KB wrong parameter
21 Incorrect 43 ms 6424 KB wrong parameter
22 Incorrect 30 ms 6124 KB wrong parameter
23 Incorrect 61 ms 6668 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 10120 KB wrong parameter
2 Incorrect 1 ms 4604 KB wrong parameter
3 Incorrect 17 ms 5376 KB wrong parameter
4 Incorrect 3 ms 4604 KB wrong parameter
5 Incorrect 20 ms 5728 KB wrong parameter
6 Incorrect 22 ms 5520 KB wrong parameter
7 Incorrect 37 ms 5852 KB wrong parameter
8 Incorrect 18 ms 5372 KB wrong parameter
9 Incorrect 19 ms 5660 KB Output isn't correct
10 Incorrect 19 ms 5632 KB Output isn't correct
11 Incorrect 19 ms 5608 KB wrong parameter
12 Incorrect 17 ms 5352 KB wrong parameter
13 Incorrect 52 ms 6156 KB wrong parameter
14 Incorrect 17 ms 5436 KB wrong parameter
15 Incorrect 19 ms 5544 KB wrong parameter
16 Incorrect 30 ms 5884 KB wrong parameter
17 Incorrect 34 ms 5944 KB wrong parameter
18 Incorrect 44 ms 6112 KB wrong parameter
19 Incorrect 23 ms 5752 KB wrong parameter
20 Incorrect 39 ms 6648 KB wrong parameter
21 Incorrect 43 ms 6424 KB wrong parameter
22 Incorrect 30 ms 6124 KB wrong parameter
23 Incorrect 61 ms 6668 KB wrong parameter