Submission #1254774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254774		lambd47	Saveit (IOI10_saveit)	C++20	100 / 100	75 ms	8000 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end() 


void encode(int n, int h, int m, int *v1, int *v2){
    vector<vector<int>> adj(n);
    vector<pair<int,int>> edg(m);
    vector<bool> marc(m);
    vector<int> resp;
    vector<vector<int>> pseudo(h,vector<int>(n,0));
    L(i,0,m-1){
        adj[v1[i]].push_back(i);
        adj[v2[i]].push_back(i);
        edg[i]={v1[i],v2[i]};
    }
    vector<vector<int>> dp(h,vector<int>(n,-1));
    vector<int> pai(n);
    auto bfs=[&](int node){
        queue<int> fila;
        fila.push(node);
        dp[node][node]=0;
        while(!fila.empty()){
            int v=fila.front();
            fila.pop();
            for(auto e:adj[v]){
                int vai=edg[e].first^edg[e].second^v;
                if(dp[node][vai]!=-1)continue;
                if(!marc[e])marc[e]=1;
                if(node==0)pai[vai]=v;
                dp[node][vai]=dp[node][v]+1;
                fila.push(vai);
            }
        }
    };
    bfs(0);
    auto send=[&](int x,int mx){
        L(i,0,mx){
            encode_bit((x&(1<<i))==0?0:1);
        }
    };
    L(i,1,n-1){
        send(pai[i],9);
    }
    L(i,1,h-1)bfs(i);


    int at=0;
    int nat=0;
    L(i,1,h-1){
        L(j,1,n-1){
            nat*=3;
            at++;
            if(dp[i][j]>dp[i][pai[j]]){
                nat+=0;
            }
            else if(dp[i][j]==dp[i][pai[j]]){
                nat+=1;
            }
            else{
                nat+=2;
            }
            if(at==3){
                send(nat,4);
                at=0;
                nat=0;
            }
        }
    }
    if(at!=0)send(nat,4);
}

decoder

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end() 

void decode(int n, int h) {
    vector<vector<int>> adj(n);
    auto liga=[&]()->int{
        int a=0;
        L(i,0,9){
            if(decode_bit()==1)a|=(1<<i);
        }
        return a;
    };
    L(j,1,n-1){
        int a=liga();
        adj[j].push_back(a);
        adj[a].push_back(j);

    }
    

    vector<int> dist(n,-1);
    vector<int> pai(n,0);
    auto bfs=[&](int node){
        hops(node,node,0);
        dist[node]=0;
        queue<int> fila;
        fila.push(node);
        while(!fila.empty()){
            int a=fila.front();
            fila.pop();
            for(auto b:adj[a]){
                if(dist[b]!=-1)continue;
                pai[b]=a;
                dist[b]=dist[a]+1;
                hops(node,b,dist[b]);
                fila.push(b);
            }
        }
    };
    bfs(0);

    vector<vector<int>> dp(h,vector<int> (n));
    vector<int> fila(3);
    int at=0;
    L(i,1,h-1){
        L(j,1,n-1){
            fila[at]=i*n+j;
            at++;
            if(at==3){
                int num=0;
                L(i,0,4){
                    if(decode_bit()==1)num+=(1<<i);
                }
                while(at>0){
                    at--;
                    dp[fila[at]/n][fila[at]%n]=num%3;
                    num/=3;
                }
                fila[0]=fila[1]=fila[2]=-1;
            }
        }
    }
    if(at!=0){
                int num=0;
                L(i,0,4){
                    if(decode_bit()==1)num+=(1<<i);
                }
                while(at>0){
                    at--;
                    dp[fila[at]/n][fila[at]%n]=num%3;
                    num/=3;
                }
                fila[0]=fila[1]=fila[2]=-1;
    }

    int resp=0;
    int hub=0;
    auto calc=[&](auto&& self,int a,int b)->void{
        if(a==b)return;
        if(dist[a]<=dist[b]){
        if(dp[hub][b]==0){
            resp++;
        }
        else if(dp[hub][b]==2){
            resp--;
        }
        self(self,a,pai[b]);
        }
        else{
            resp++;
            self(self,pai[a],b);
        }
    };
    L(i,1,h-1){
        hub=i;
        L(j,0,n-1){
            resp=0;
            hub=i;
            calc(calc,i,j);
            hops(i,j,resp);
        }
    }


}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25