oj.uz

Submission #792585

# Submission time Handle Problem Language Result Execution time Memory
792585 2023-07-25T07:10:02 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 145 ms 10884 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])){
            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 Runtime error 145 ms 10884 KB Execution killed with signal 11
2 Incorrect 3 ms 4604 KB wrong parameter
3 Runtime error 4 ms 976 KB Execution killed with signal 11
4 Incorrect 3 ms 4604 KB wrong parameter
5 Runtime error 9 ms 1360 KB Execution killed with signal 11
6 Runtime error 6 ms 1360 KB Execution killed with signal 11
7 Runtime error 15 ms 2012 KB Execution killed with signal 11
8 Incorrect 6 ms 4860 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 7 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 21 ms 2260 KB Execution killed with signal 11
14 Incorrect 10 ms 5116 KB duplicate hops call
15 Incorrect 12 ms 5088 KB duplicate hops call
16 Runtime error 14 ms 2028 KB Execution killed with signal 11
17 Runtime error 21 ms 1956 KB Execution killed with signal 11
18 Runtime error 35 ms 2504 KB Execution killed with signal 11
19 Runtime error 13 ms 1732 KB Execution killed with signal 11
20 Runtime error 25 ms 3196 KB Execution killed with signal 11
21 Runtime error 43 ms 3400 KB Execution killed with signal 11
22 Runtime error 26 ms 2416 KB Execution killed with signal 11
23 Runtime error 47 ms 3792 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 ms 10884 KB Execution killed with signal 11
2 Incorrect 3 ms 4604 KB wrong parameter
3 Runtime error 4 ms 976 KB Execution killed with signal 11
4 Incorrect 3 ms 4604 KB wrong parameter
5 Runtime error 9 ms 1360 KB Execution killed with signal 11
6 Runtime error 6 ms 1360 KB Execution killed with signal 11
7 Runtime error 15 ms 2012 KB Execution killed with signal 11
8 Incorrect 6 ms 4860 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 7 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 21 ms 2260 KB Execution killed with signal 11
14 Incorrect 10 ms 5116 KB duplicate hops call
15 Incorrect 12 ms 5088 KB duplicate hops call
16 Runtime error 14 ms 2028 KB Execution killed with signal 11
17 Runtime error 21 ms 1956 KB Execution killed with signal 11
18 Runtime error 35 ms 2504 KB Execution killed with signal 11
19 Runtime error 13 ms 1732 KB Execution killed with signal 11
20 Runtime error 25 ms 3196 KB Execution killed with signal 11
21 Runtime error 43 ms 3400 KB Execution killed with signal 11
22 Runtime error 26 ms 2416 KB Execution killed with signal 11
23 Runtime error 47 ms 3792 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 ms 10884 KB Execution killed with signal 11
2 Incorrect 3 ms 4604 KB wrong parameter
3 Runtime error 4 ms 976 KB Execution killed with signal 11
4 Incorrect 3 ms 4604 KB wrong parameter
5 Runtime error 9 ms 1360 KB Execution killed with signal 11
6 Runtime error 6 ms 1360 KB Execution killed with signal 11
7 Runtime error 15 ms 2012 KB Execution killed with signal 11
8 Incorrect 6 ms 4860 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 7 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 21 ms 2260 KB Execution killed with signal 11
14 Incorrect 10 ms 5116 KB duplicate hops call
15 Incorrect 12 ms 5088 KB duplicate hops call
16 Runtime error 14 ms 2028 KB Execution killed with signal 11
17 Runtime error 21 ms 1956 KB Execution killed with signal 11
18 Runtime error 35 ms 2504 KB Execution killed with signal 11
19 Runtime error 13 ms 1732 KB Execution killed with signal 11
20 Runtime error 25 ms 3196 KB Execution killed with signal 11
21 Runtime error 43 ms 3400 KB Execution killed with signal 11
22 Runtime error 26 ms 2416 KB Execution killed with signal 11
23 Runtime error 47 ms 3792 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 ms 10884 KB Execution killed with signal 11
2 Incorrect 3 ms 4604 KB wrong parameter
3 Runtime error 4 ms 976 KB Execution killed with signal 11
4 Incorrect 3 ms 4604 KB wrong parameter
5 Runtime error 9 ms 1360 KB Execution killed with signal 11
6 Runtime error 6 ms 1360 KB Execution killed with signal 11
7 Runtime error 15 ms 2012 KB Execution killed with signal 11
8 Incorrect 6 ms 4860 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 7 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 21 ms 2260 KB Execution killed with signal 11
14 Incorrect 10 ms 5116 KB duplicate hops call
15 Incorrect 12 ms 5088 KB duplicate hops call
16 Runtime error 14 ms 2028 KB Execution killed with signal 11
17 Runtime error 21 ms 1956 KB Execution killed with signal 11
18 Runtime error 35 ms 2504 KB Execution killed with signal 11
19 Runtime error 13 ms 1732 KB Execution killed with signal 11
20 Runtime error 25 ms 3196 KB Execution killed with signal 11
21 Runtime error 43 ms 3400 KB Execution killed with signal 11
22 Runtime error 26 ms 2416 KB Execution killed with signal 11
23 Runtime error 47 ms 3792 KB Execution killed with signal 11