Submission #792585

#	Time	Username	Problem	Language	Result	Execution time	Memory
792585		irmuun	Saveit (IOI10_saveit)	C++17	0 / 100	145 ms	10884 KiB

encoder

#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);
                }
            }
        }
    }
}

decoder

#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 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25