Submission #774389

#	Time	Username	Problem	Language	Result	Execution time	Memory
774389		ttamx	Saveit (IOI10_saveit)	C++14	100 / 100	237 ms	10300 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>

using namespace std;

void encode(int n, int h, int ne, int *v1, int *v2){
	vector<vector<int>> adj(n);
	for(int i=0;i<ne;i++){
		int u=v1[i],v=v2[i];
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	vector<bool> vis(n);
	vector<int> p(n);
	function<void(int)> dfs=[&](int u){
		vis[u]=true;
		for(auto v:adj[u]){
			if(vis[v])continue;
			p[v]=u;
			dfs(v);
		}
	};
	dfs(0);
	for(int i=1;i<n;i++)for(int j=0;j<10;j++)encode_bit(p[i]>>j&1);
	vector<vector<pair<int,int>>> adj2(n);
	for(int i=1;i<n;i++){
		int u=i,v=p[i];
		adj2[u].emplace_back(v,i-1);
		adj2[v].emplace_back(u,i-1);
	}
	for(int i=0;i<h;i++){
		vector<int> dist(n,2e9);
		queue<int> q;
		q.emplace(i);
		dist[i]=0;
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(auto v:adj[u]){
				if(dist[v]<=dist[u]+1)continue;
				dist[v]=dist[u]+1;
				q.emplace(v);
			}
		}
		vector<int> val(n-1);
		function<void(int,int)> dfs2=[&](int u,int p){
			for(auto [v,id]:adj2[u]){
				if(v==p)continue;
				val[id]=dist[v]-dist[u];
				dfs2(v,u);
			}
		};
		dfs2(i,-1);
		while(val.size()%5!=0)val.emplace_back(0);
		int cur=0,cnt=0;
		for(auto x:val){
			cur*=3;
			cur+=x+1;
			cnt++;
			if(cnt==5){
				for(int j=0;j<8;j++)encode_bit(cur>>j&1);
				cur=cnt=0;
			}
		}
	}
}

decoder

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>

using namespace std;

void decode(int n, int h) {
   vector<int> p(n);
	for(int i=1;i<n;i++)for(int j=0;j<10;j++)p[i]+=decode_bit()<<j;
	vector<vector<pair<int,int>>> adj(n);
	for(int i=1;i<n;i++){
		int u=i,v=p[i];
		adj[u].emplace_back(v,i-1);
		adj[v].emplace_back(u,i-1);
	}
   for(int i=0;i<h;i++){
      vector<int> val(n-1);
		while(val.size()%5!=0)val.emplace_back(0);
      for(int i=0;i<val.size();i+=5){
         int cur=0;
         for(int j=0;j<8;j++)cur+=decode_bit()<<j;
         for(int j=4;j>=0;j--){
            val[i+j]=cur%3-1;
            cur/=3;
         }
      }
      vector<int> dist(n);
      function<void(int,int)> dfs=[&](int u,int p){
         for(auto [v,id]:adj[u]){
            if(v==p)continue;
            dist[v]=dist[u]+val[id];
            dfs(v,u);
         }
      };
      dist[i]=0;
      dfs(i,-1);
      for(int j=0;j<n;j++)hops(i,j,dist[j]);
   }
}

Compilation message (stderr)

encoder.cpp: In lambda function:
encoder.cpp:48:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |    for(auto [v,id]:adj2[u]){
      |             ^

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |       for(int i=0;i<val.size();i+=5){
      |                   ~^~~~~~~~~~~
decoder.cpp: In lambda function:
decoder.cpp:29:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |          for(auto [v,id]:adj[u]){
      |                   ^

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