#include "grader.h" #include "encoder.h" #include<bits/stdc++.h> using namespace std; vector<int> ad[1010]; int par[1010], dis[1010]; bool visited[1010]; void encode_num(int x, int b) { for(int i = 1; i <= b; i++){ encode_bit(x%2); x >>= 1; } } void dfs(int u) { visited[u] = 1; for(int v : ad[u]) if(visited[v] == 0){ par[v] = u; dfs(v); } } void encode_vec(vector<int> vec) { //There are 3^5 = 243 different combinations, which is smaller than 256 (1 byte) int cur = 0, p = 1; for(int i : vec){ cur += (i+1) * p; p *= 3; } /*cerr<<cur<<endl; for(int i : vec) cerr<<i<<" "; cerr<<endl;*/ encode_num(cur, 8); } void encode(int n, int hh, int m, int *v1, int *v2){ //Load the edges in the graph for(int i = 0; i < m; i++){ ad[v1[i]].push_back(v2[i]); ad[v2[i]].push_back(v1[i]); } //Send a spanning tree first dfs(0); for(int i = 1; i < n; i++) encode_num(par[i], 10); //Then send the information for(int p = 0; p < hh; p++){ memset(dis, 0x3f, sizeof(dis)); queue<int> w; dis[p] = 0; w.push(p); while(w.size() > 0){ int u = w.front(); w.pop(); for(int v : ad[u]) if(dis[v] > dis[u] + 1){ dis[v] = dis[u] + 1; w.push(v); } } //Encode the difference vector<int> cur; for(int i = 1; i < n; i++){ cur.push_back(dis[i] - dis[par[i]]); if(cur.size() == 5){ encode_vec(cur); cur.clear(); } } //We optimize by saving 5 numbers (in [-1, 1]) in a single byte if(cur.size() > 0){ while(cur.size() < 5) cur.push_back(0); encode_vec(cur); } } }

#include "grader.h" #include "decoder.h" #include<bits/stdc++.h> using namespace std; inline int flipbit(int num, int bit) { return num ^ (1 << bit); } int getnum(int b) { int cur = 0; for(int i = 0; i < b; i++) if(decode_bit() == 1) cur = flipbit(cur, i); return cur; } vector<int> getvec() { //Get the vector of 5 numbers from -1 to 1 int cur = getnum(8); vector<int> ans; for(int i = 1; i <= 5; i++){ ans.push_back(cur%3 - 1); cur /= 3; } /*cerr<<"B"<<cur<<endl; for(int i : ans) cerr<<i<<" "; cerr<<endl;*/ return ans; } vector<array<int, 2>> adj[1010]; int parr[1010], pardif[1010], ans[1010]; bool visited2[1010]; void dfs_ans(int u) { visited2[u] = 1; for(auto &[v, d] : adj[u]) if(visited2[v] == 0){ ans[v] = ans[u] + d; dfs_ans(v); } visited2[u] = 0; } void decode(int n, int hh) { //Reconstruct the spanning tree for(int i = 1; i < n; i++) parr[i] = getnum(10); //Solve for each hub for(int i = 0; i < hh; i++){ for(int j = 0; j < n; j++) adj[j].clear(); //Get the dif information for(int j = 1; j < n; j += 5){ vector<int> cur = getvec(); for(int k = j; k < j+5; k++) pardif[k] = cur[k-j]; } for(int j = 1; j < n; j++){ adj[parr[j]].push_back({j, pardif[j]}); adj[j].push_back({parr[j], -pardif[j]}); } //Calculate the actual value ans[i] = 0; dfs_ans(i); //Answer the question for(int j = 0; j < n; j++) hops(i, j, ans[j]); } }