Submission #1254748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254748		lambd47	Saveit (IOI10_saveit)	C++20	50 / 100	95 ms	7744 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){
    int at=0;
    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]};
        if(v1[i]<h || v2[i]<h)marc[i]=1;
        if(v1[i]<h){
            pseudo[v1[i]][v2[i]]=1;
        }
        if(v2[i]<h){
            pseudo[v2[i]][v1[i]]=1;
        }
    }
    auto bfs=[&](int node){
        queue<int> fila;
        fila.push(node);
        vector<bool> vis(m,0);
        vis[node]=1;
        while(!fila.empty()){
            int v=fila.front();
            fila.pop();
            for(auto e:adj[v]){
                int vai=edg[e].first^edg[e].second^v;
                if(vis[vai])continue;
                if(!marc[e])marc[e]=1;
                vis[vai]=1;
                fila.push(vai);
            }
        }
    };
    L(i,0,h-1)bfs(i);

    L(i,0,h-1){
        L(j,0,n-1){
            encode_bit(pseudo[i][j]);
        }
    }
    auto send=[&](int x){
        L(i,0,9){
            encode_bit((x&(1<<i))==0?0:1);
        }
    };
    L(i,0,m-1){
        if(marc[i]){
            if(edg[i].first < h || edg[i].second<h)continue;
            send(edg[i].first);
            send(edg[i].second);
        }
    }
    at=0;
    while(at<=11){
        encode_bit(1);
        at++;
    }



}

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);
    L(i,0,h-1){
        L(j,0,n-1){
            if(decode_bit()==1){
                adj[i].push_back(j);
                if(j>=h)adj[j].push_back(i);
            }
        }
    }
    auto liga=[&]()->bool{
        int a=0;
        L(i,0,9){
            if(decode_bit()==1)a|=(1<<i);
        }
        if(a==1023)return false;
        int b=0;
        L(i,0,9){
            if(decode_bit()==1)b|=(1<<i);
        }
        adj[a].push_back(b);
        adj[b].push_back(a);
        return true;
    };
    while(liga());

    auto bfs=[&](int node){
        vector<int> dist(n,-1);
        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;
                dist[b]=dist[a]+1;
                hops(node,b,dist[b]);
                fila.push(b);
            }
        }
    };
    L(i,0,h-1)bfs(i);
}

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