| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 444339 |
2021-07-13T17:13:38 Z |
JovanB |
Saveit (IOI10_saveit) |
C++17 |
|
230 ms |
12604 KB |
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
static int parent[10000];
static int dist[36][10000];
static int info[36][10000];
static vector <int> graf[10000];
void bfs(int root, int n){
for(int i=0; i<n; i++) dist[root][i] = n+5;
dist[root][root] = 0;
queue <int> q;
q.push(root);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto c : graf[v]){
if(dist[root][c] > dist[root][v] + 1){
dist[root][c] = dist[root][v] + 1;
q.push(c);
if(root == 0) parent[c] = v;
}
}
}
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
for(int i=0; i<ne; i++){
graf[v1[i]].push_back(v2[i]);
graf[v2[i]].push_back(v1[i]);
}
for(int i=0; i<nh; i++) bfs(i, nv);
for(int i=1; i<nv; i++){
for(int j=0; j<10; j++){
if((1 << j) & parent[i]) encode_bit(1);
else encode_bit(0);
}
}
vector <pair <int, int>> pairs;
for(int i=0; i<nh; i++){
for(int j=1; j<nv; j++){
if(dist[i][j] == dist[i][parent[j]] + 1) info[i][j] = 1;
else if(dist[i][j] == dist[i][parent[j]] - 1) info[i][j] = 2;
pairs.push_back({i, j});
}
}
while(pairs.size()%3) pairs.push_back({0, 0});
for(int i=0; i<pairs.size(); i+=3){
pair <int, int> a = pairs[i];
pair <int, int> b = pairs[i+1];
pair <int, int> c = pairs[i+2];
int tr = info[c.first][c.second];
tr = 3*tr + info[b.first][b.second];
tr = 3*tr + info[a.first][a.second];
for(int j=0; j<5; j++){
if((1 << j) & tr) encode_bit(1);
else encode_bit(0);
}
}
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
static int parent[10000];
static int info[36][10000];
static int dist[36][10000];
static vector <int> graf[10000];
void dfs(int v, int p, int k){
if(p != -1){
if(info[k][v] == 0) dist[k][v] = dist[k][p];
else if(info[k][v] == 1) dist[k][v] = dist[k][p] + 1;
else dist[k][v] = dist[k][p] - 1;
}
for(auto c : graf[v]){
dfs(c, v, k);
}
}
void decode(int nv, int nh){
int tr = 0;
for(int i=1; i<nv; i++){
for(int j=0; j<10; j++){
parent[i] += (1 << j)*decode_bit();
}
graf[parent[i]].push_back(i);
}
vector <pair <int, int>> pairs;
for(int i=0; i<nh; i++){
for(int j=1; j<nv; j++){
pairs.push_back({i, j});
}
}
while(pairs.size()%3) pairs.push_back({0, 0});
for(int i=0; i<pairs.size(); i+=3){
pair <int, int> a = pairs[i];
pair <int, int> b = pairs[i+1];
pair <int, int> c = pairs[i+2];
int tr = 0;
for(int j=0; j<5; j++){
tr += (1 << j)*decode_bit();
}
info[a.first][a.second] = tr%3;
tr /= 3;
info[b.first][b.second] = tr%3;
tr /= 3;
info[c.first][c.second] = tr;
}
for(int i=0; i<nh; i++){
dfs(0, -1, i);
int dod = -dist[i][i];
for(int j=0; j<nv; j++) dist[i][j] += dod;
for(int j=0; j<nv; j++) hops(i, j, dist[i][j]);
}
}
Compilation message
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0; i<pairs.size(); i+=3){
| ~^~~~~~~~~~~~~
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0; i<pairs.size(); i+=3){
| ~^~~~~~~~~~~~~
decoder.cpp:25:9: warning: unused variable 'tr' [-Wunused-variable]
25 | int tr = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
12604 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
5152 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
28 ms |
7504 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
4 ms |
5096 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
7688 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
40 ms |
8004 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
61 ms |
8212 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
27 ms |
7752 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
34 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
28 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
36 ms |
7840 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
27 ms |
7796 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
75 ms |
8404 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
33 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
59 ms |
8148 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
50 ms |
8200 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
8456 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
44 ms |
8012 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
74 ms |
8728 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
107 ms |
8836 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
70 ms |
8500 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
109 ms |
9204 KB |
Output is correct - 69930 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
12604 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
5152 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
28 ms |
7504 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
4 ms |
5096 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
7688 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
40 ms |
8004 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
61 ms |
8212 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
27 ms |
7752 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
34 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
28 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
36 ms |
7840 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
27 ms |
7796 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
75 ms |
8404 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
33 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
59 ms |
8148 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
50 ms |
8200 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
8456 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
44 ms |
8012 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
74 ms |
8728 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
107 ms |
8836 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
70 ms |
8500 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
109 ms |
9204 KB |
Output is correct - 69930 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
12604 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
5152 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
28 ms |
7504 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
4 ms |
5096 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
7688 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
40 ms |
8004 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
61 ms |
8212 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
27 ms |
7752 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
34 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
28 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
36 ms |
7840 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
27 ms |
7796 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
75 ms |
8404 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
33 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
59 ms |
8148 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
50 ms |
8200 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
8456 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
44 ms |
8012 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
74 ms |
8728 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
107 ms |
8836 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
70 ms |
8500 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
109 ms |
9204 KB |
Output is correct - 69930 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
12604 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
3 ms |
5152 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
28 ms |
7504 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
4 ms |
5096 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
7688 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
40 ms |
8004 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
61 ms |
8212 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
27 ms |
7752 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
34 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
28 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
36 ms |
7840 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
27 ms |
7796 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
75 ms |
8404 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
33 ms |
7720 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
7708 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
59 ms |
8148 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
50 ms |
8200 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
63 ms |
8456 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
44 ms |
8012 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
74 ms |
8728 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
107 ms |
8836 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
70 ms |
8500 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
109 ms |
9204 KB |
Output is correct - 69930 call(s) of encode_bit() |
