oj.uz

Submission #792583

# Submission time Handle Problem Language Result Execution time Memory
792583 2023-07-25T07:06:42 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 135 ms 10908 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]]){
                    encode_bit(0);
                    encode_bit(0);
                }
                if(dist[ord[j]]==dist[ord[j-1]]-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=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 135 ms 10908 KB Execution killed with signal 11
2 Incorrect 3 ms 4608 KB duplicate hops call
3 Runtime error 5 ms 976 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Runtime error 5 ms 1324 KB Execution killed with signal 11
6 Runtime error 6 ms 1328 KB Execution killed with signal 11
7 Runtime error 18 ms 2052 KB Execution killed with signal 11
8 Incorrect 6 ms 4728 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 30 ms 2360 KB Execution killed with signal 11
14 Incorrect 9 ms 5064 KB duplicate hops call
15 Incorrect 9 ms 5112 KB duplicate hops call
16 Runtime error 20 ms 1992 KB Execution killed with signal 11
17 Runtime error 17 ms 1916 KB Execution killed with signal 11
18 Runtime error 33 ms 2504 KB Execution killed with signal 11
19 Runtime error 14 ms 1728 KB Execution killed with signal 11
20 Runtime error 26 ms 3136 KB Execution killed with signal 11
21 Runtime error 31 ms 3288 KB Execution killed with signal 11
22 Runtime error 23 ms 2324 KB Execution killed with signal 11
23 Runtime error 37 ms 3784 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 10908 KB Execution killed with signal 11
2 Incorrect 3 ms 4608 KB duplicate hops call
3 Runtime error 5 ms 976 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Runtime error 5 ms 1324 KB Execution killed with signal 11
6 Runtime error 6 ms 1328 KB Execution killed with signal 11
7 Runtime error 18 ms 2052 KB Execution killed with signal 11
8 Incorrect 6 ms 4728 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 30 ms 2360 KB Execution killed with signal 11
14 Incorrect 9 ms 5064 KB duplicate hops call
15 Incorrect 9 ms 5112 KB duplicate hops call
16 Runtime error 20 ms 1992 KB Execution killed with signal 11
17 Runtime error 17 ms 1916 KB Execution killed with signal 11
18 Runtime error 33 ms 2504 KB Execution killed with signal 11
19 Runtime error 14 ms 1728 KB Execution killed with signal 11
20 Runtime error 26 ms 3136 KB Execution killed with signal 11
21 Runtime error 31 ms 3288 KB Execution killed with signal 11
22 Runtime error 23 ms 2324 KB Execution killed with signal 11
23 Runtime error 37 ms 3784 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 10908 KB Execution killed with signal 11
2 Incorrect 3 ms 4608 KB duplicate hops call
3 Runtime error 5 ms 976 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Runtime error 5 ms 1324 KB Execution killed with signal 11
6 Runtime error 6 ms 1328 KB Execution killed with signal 11
7 Runtime error 18 ms 2052 KB Execution killed with signal 11
8 Incorrect 6 ms 4728 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 30 ms 2360 KB Execution killed with signal 11
14 Incorrect 9 ms 5064 KB duplicate hops call
15 Incorrect 9 ms 5112 KB duplicate hops call
16 Runtime error 20 ms 1992 KB Execution killed with signal 11
17 Runtime error 17 ms 1916 KB Execution killed with signal 11
18 Runtime error 33 ms 2504 KB Execution killed with signal 11
19 Runtime error 14 ms 1728 KB Execution killed with signal 11
20 Runtime error 26 ms 3136 KB Execution killed with signal 11
21 Runtime error 31 ms 3288 KB Execution killed with signal 11
22 Runtime error 23 ms 2324 KB Execution killed with signal 11
23 Runtime error 37 ms 3784 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 10908 KB Execution killed with signal 11
2 Incorrect 3 ms 4608 KB duplicate hops call
3 Runtime error 5 ms 976 KB Execution killed with signal 11
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Runtime error 5 ms 1324 KB Execution killed with signal 11
6 Runtime error 6 ms 1328 KB Execution killed with signal 11
7 Runtime error 18 ms 2052 KB Execution killed with signal 11
8 Incorrect 6 ms 4728 KB too many decode_bit() calls
9 Runtime error 5 ms 976 KB Execution killed with signal 11
10 Runtime error 6 ms 976 KB Execution killed with signal 11
11 Runtime error 8 ms 1232 KB Execution killed with signal 11
12 Runtime error 4 ms 848 KB Execution killed with signal 11
13 Runtime error 30 ms 2360 KB Execution killed with signal 11
14 Incorrect 9 ms 5064 KB duplicate hops call
15 Incorrect 9 ms 5112 KB duplicate hops call
16 Runtime error 20 ms 1992 KB Execution killed with signal 11
17 Runtime error 17 ms 1916 KB Execution killed with signal 11
18 Runtime error 33 ms 2504 KB Execution killed with signal 11
19 Runtime error 14 ms 1728 KB Execution killed with signal 11
20 Runtime error 26 ms 3136 KB Execution killed with signal 11
21 Runtime error 31 ms 3288 KB Execution killed with signal 11
22 Runtime error 23 ms 2324 KB Execution killed with signal 11
23 Runtime error 37 ms 3784 KB Execution killed with signal 11