oj.uz

Submission #774386

# Submission time Handle Problem Language Result Execution time Memory
774386 2023-07-05T17:05:23 Z ttamx Saveit (IOI10_saveit) C++14
100 / 100
 259 ms 10388 KB 
#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);
	vector<bool> enc;
	for(int i=1;i<n;i++)for(int j=0;j<10;j++)enc.emplace_back(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++)enc.emplace_back(cur>>j&1);
				cur=cnt=0;
			}
		}
	}
	for(auto x:enc)encode_bit(x);
}
#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

encoder.cpp: In lambda function:
encoder.cpp:49:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |    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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 10388 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 4612 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 19 ms 5644 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 25 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 37 ms 6068 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 19 ms 5508 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 22 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 20 ms 5492 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 24 ms 5608 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 19 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 48 ms 6188 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 19 ms 5620 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 5612 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 33 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 26 ms 6092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 42 ms 6552 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 49 ms 6700 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 34 ms 6228 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 78 ms 6916 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 10388 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 4612 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 19 ms 5644 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 25 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 37 ms 6068 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 19 ms 5508 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 22 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 20 ms 5492 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 24 ms 5608 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 19 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 48 ms 6188 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 19 ms 5620 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 5612 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 33 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 26 ms 6092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 42 ms 6552 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 49 ms 6700 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 34 ms 6228 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 78 ms 6916 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 10388 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 4612 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 19 ms 5644 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 25 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 37 ms 6068 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 19 ms 5508 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 22 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 20 ms 5492 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 24 ms 5608 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 19 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 48 ms 6188 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 19 ms 5620 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 5612 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 33 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 26 ms 6092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 42 ms 6552 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 49 ms 6700 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 34 ms 6228 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 78 ms 6916 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 10388 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 4612 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 17 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 19 ms 5644 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 25 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 37 ms 6068 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 19 ms 5508 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 22 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 20 ms 5492 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 24 ms 5608 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 19 ms 5716 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 48 ms 6188 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 19 ms 5620 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 19 ms 5612 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 34 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 33 ms 6120 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 34 ms 6460 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 26 ms 6092 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 42 ms 6552 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 49 ms 6700 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 34 ms 6228 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 78 ms 6916 KB Output is correct - 67590 call(s) of encode_bit()