oj.uz

Submission #792581

# Submission time Handle Problem Language Result Execution time Memory
792581 2023-07-25T07:05:40 Z irmuun Saveit (IOI10_saveit) C++17
0 / 100
 189 ms 10900 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);
            }
        }
    };
    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 189 ms 10900 KB Execution killed with signal 11
2 Runtime error 3 ms 464 KB Execution killed with signal 11
3 Runtime error 5 ms 996 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 10 ms 1264 KB Execution killed with signal 11
6 Runtime error 10 ms 1380 KB Execution killed with signal 11
7 Runtime error 29 ms 1984 KB Execution killed with signal 11
8 Runtime error 5 ms 920 KB Execution killed with signal 11
9 Runtime error 6 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 10 ms 1300 KB Execution killed with signal 11
12 Runtime error 4 ms 936 KB Execution killed with signal 11
13 Runtime error 46 ms 2296 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 5 ms 1104 KB Execution killed with signal 11
16 Runtime error 21 ms 2016 KB Execution killed with signal 11
17 Runtime error 26 ms 1896 KB Execution killed with signal 11
18 Runtime error 20 ms 2472 KB Execution killed with signal 11
19 Runtime error 13 ms 1616 KB Execution killed with signal 11
20 Runtime error 40 ms 3116 KB Execution killed with signal 11
21 Runtime error 33 ms 3388 KB Execution killed with signal 11
22 Runtime error 26 ms 2400 KB Execution killed with signal 11
23 Runtime error 37 ms 3824 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 10900 KB Execution killed with signal 11
2 Runtime error 3 ms 464 KB Execution killed with signal 11
3 Runtime error 5 ms 996 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 10 ms 1264 KB Execution killed with signal 11
6 Runtime error 10 ms 1380 KB Execution killed with signal 11
7 Runtime error 29 ms 1984 KB Execution killed with signal 11
8 Runtime error 5 ms 920 KB Execution killed with signal 11
9 Runtime error 6 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 10 ms 1300 KB Execution killed with signal 11
12 Runtime error 4 ms 936 KB Execution killed with signal 11
13 Runtime error 46 ms 2296 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 5 ms 1104 KB Execution killed with signal 11
16 Runtime error 21 ms 2016 KB Execution killed with signal 11
17 Runtime error 26 ms 1896 KB Execution killed with signal 11
18 Runtime error 20 ms 2472 KB Execution killed with signal 11
19 Runtime error 13 ms 1616 KB Execution killed with signal 11
20 Runtime error 40 ms 3116 KB Execution killed with signal 11
21 Runtime error 33 ms 3388 KB Execution killed with signal 11
22 Runtime error 26 ms 2400 KB Execution killed with signal 11
23 Runtime error 37 ms 3824 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 10900 KB Execution killed with signal 11
2 Runtime error 3 ms 464 KB Execution killed with signal 11
3 Runtime error 5 ms 996 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 10 ms 1264 KB Execution killed with signal 11
6 Runtime error 10 ms 1380 KB Execution killed with signal 11
7 Runtime error 29 ms 1984 KB Execution killed with signal 11
8 Runtime error 5 ms 920 KB Execution killed with signal 11
9 Runtime error 6 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 10 ms 1300 KB Execution killed with signal 11
12 Runtime error 4 ms 936 KB Execution killed with signal 11
13 Runtime error 46 ms 2296 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 5 ms 1104 KB Execution killed with signal 11
16 Runtime error 21 ms 2016 KB Execution killed with signal 11
17 Runtime error 26 ms 1896 KB Execution killed with signal 11
18 Runtime error 20 ms 2472 KB Execution killed with signal 11
19 Runtime error 13 ms 1616 KB Execution killed with signal 11
20 Runtime error 40 ms 3116 KB Execution killed with signal 11
21 Runtime error 33 ms 3388 KB Execution killed with signal 11
22 Runtime error 26 ms 2400 KB Execution killed with signal 11
23 Runtime error 37 ms 3824 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 10900 KB Execution killed with signal 11
2 Runtime error 3 ms 464 KB Execution killed with signal 11
3 Runtime error 5 ms 996 KB Execution killed with signal 11
4 Runtime error 2 ms 464 KB Execution killed with signal 11
5 Runtime error 10 ms 1264 KB Execution killed with signal 11
6 Runtime error 10 ms 1380 KB Execution killed with signal 11
7 Runtime error 29 ms 1984 KB Execution killed with signal 11
8 Runtime error 5 ms 920 KB Execution killed with signal 11
9 Runtime error 6 ms 976 KB Execution killed with signal 11
10 Runtime error 5 ms 976 KB Execution killed with signal 11
11 Runtime error 10 ms 1300 KB Execution killed with signal 11
12 Runtime error 4 ms 936 KB Execution killed with signal 11
13 Runtime error 46 ms 2296 KB Execution killed with signal 11
14 Runtime error 7 ms 976 KB Execution killed with signal 11
15 Runtime error 5 ms 1104 KB Execution killed with signal 11
16 Runtime error 21 ms 2016 KB Execution killed with signal 11
17 Runtime error 26 ms 1896 KB Execution killed with signal 11
18 Runtime error 20 ms 2472 KB Execution killed with signal 11
19 Runtime error 13 ms 1616 KB Execution killed with signal 11
20 Runtime error 40 ms 3116 KB Execution killed with signal 11
21 Runtime error 33 ms 3388 KB Execution killed with signal 11
22 Runtime error 26 ms 2400 KB Execution killed with signal 11
23 Runtime error 37 ms 3824 KB Execution killed with signal 11