| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 574470 |
2022-06-08T15:33:25 Z |
SlavicG |
Saveit (IOI10_saveit) |
C++17 |
|
695 ms |
15212 KB |
#include "bits/stdc++.h"
#include "grader.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
vector<int> bfs(int start, vector<vector<int>>& adj) {
int n = sz(adj);
vector<int> dist(n, -1);
dist[start] = 0;
queue<int> q;
q.push(start);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int v: adj[u]) {
if(dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
void dfs(int u, vector<bool>& vis, vector<vector<int>>& adj, vector<int>& par) {
vis[u] = true;
for(int v: adj[u]) {
if(!vis[v]) {
par[v] = u;
dfs(v, vis, adj, par);
}
}
}
map<vector<int>, int> mp;
int amogus = 0;
void rec(vector<int> v) {
if(sz(v) == 3) {
if(mp.count(v)) return;
mp[v] = amogus++;
} else {
for(int i = 0; i <= 2; ++i) {
v.pb(i);
rec(v);
v.pop_back();
}
}
}
void encode(int n, int h, int m, int *v1, int *v2){
vector<vector<int>> adj(n);
for(int i = 0; i < m; ++i) {
adj[v1[i]].pb(v2[i]);
adj[v2[i]].pb(v1[i]);
}
vector<vector<int>> dist(n);
forn(i, n) dist[i] = bfs(i, adj);
for(int i = 0;i < h; ++i) {
for(int j = 0; j < 10; ++j) {
if(dist[0][i] & (1 << j)) encode_bit(1);
else encode_bit(0);
}
}
vector<bool> vis(n, false);
vector<int> parent(n);
iota(all(parent), 0);
dfs(0, vis, adj, parent);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < 10; ++j) {
if(parent[i] & (1 << j)) encode_bit(1);
else encode_bit(0);
}
}
//dist[node][i] = dist[parent[node]][i] (0)
//dist[node][i] = dist[parent[node]][i] - 1 (1)
//dist[node][i] = dist[parent[node]][i] + 1 (2)
rec({});
vector<int> v;
for(int j = 0; j < h; ++j) {
for(int i = 1; i < n; ++i) {
if(dist[i][j] == dist[parent[i]][j]) v.pb(0);
else if(dist[i][j] == dist[parent[i]][j] - 1) v.pb(1);
else v.pb(2);
}
}
for(int i = 0; i + 2 < sz(v); i += 3) {
for(int f = 0; f < 5; ++f) {
if(mp[{v[i], v[i + 1], v[i + 2]}] & (1 << f)) {
encode_bit(1);
} else encode_bit(0);
}
}
if(sz(v) % 3 == 1) {
for(int f = 0; f < 2; ++f) {
if(v.back() & (1 << f)) encode_bit(1);
else encode_bit(0);
}
} else if(sz(v) % 3 == 2) {
for(int k = sz(v) - 2; k < sz(v); ++k) {
for(int f = 0; f < 2; ++f) {
if(v[k] & (1 << f)) encode_bit(1);
else encode_bit(0);
}
}
}
}
/*
void solve() {
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
*/
#include "bits/stdc++.h"
#include "grader.h"
#include "decoder.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
const int N = 1000;
int dist[N][40], type[N][40];
vector<int> adj[N];
map<vector<int>, int> mp;
int amogus = 0;
map<int, vector<int>> Paiu;
void rec(vector<int> v) {
if(sz(v) == 3) {
if(mp.count(v)) return;
mp[v] = amogus;
Paiu[amogus] = v;
++amogus;
} else {
for(int i = 0; i <= 2; ++i) {
v.pb(i);
rec(v);
v.pop_back();
}
}
}
void dfs(int u, int par, int h) {
for(int v: adj[u]) {
if(v == par) continue;
for(int j = 0; j < h; ++j) {
if(type[v][j] == 0) dist[v][j] = dist[u][j];
else if(type[v][j] == 1) dist[v][j] = dist[u][j] - 1;
else dist[v][j] = dist[u][j] + 1;
}
dfs(v, u, h);
}
}
void decode(int n, int h) {
for(int i = 0; i < h; ++i) {
for(int j = 0; j < 10; ++j) {
if(decode_bit()) dist[0][i] += (1 << j);
}
}
for(int i = 0;i < n; ++i) {
int node = 0;
for(int j = 0; j < 10; ++j) {
if(decode_bit()) node += (1 << j);
}
if(node != i) adj[node].pb(i);
}
rec({});
vector<pair<int, int>> v;
for(int j = 0; j < h; ++j) {
for(int i = 1; i < n; ++i) {
v.pb({i, j});
}
}
for(int i = 0; i + 2 < sz(v); i += 3) {
int number = 0;
for(int f = 0; f < 5; ++f) {
if(decode_bit()) number += (1 << f);
}
vector<int> f = Paiu[number];
type[v[i].first][v[i].second] = f[0];
type[v[i + 1].first][v[i + 1].second] = f[1];
type[v[i + 2].first][v[i + 2].second] = f[2];
}
if(sz(v) % 3 == 1) {
for(int f = 0; f < 2; ++f) {
if(decode_bit()) type[v[n - 1].first][v[n - 1].second] += (1 << f);
}
} else if(sz(v) % 3 == 2) {
for(int k = n - 2; k < n; ++k) {
for(int f = 0; f < 2; ++f) {
if(decode_bit()) type[v[k].first][v[k].second] += (1 << f);
}
}
}
dfs(0, -1, h);
for(int i = 0; i < h; ++i) {
for(int j = 0; j < n; ++j) {
hops(i, j, dist[j][i]);
}
}
}
/*
void solve() {
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
15212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 100 call(s) of encode_bit() |
| 3 |
Correct |
50 ms |
9508 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 4 |
Incorrect |
2 ms |
4612 KB |
Output isn't correct |
| 5 |
Correct |
62 ms |
9652 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 6 |
Correct |
69 ms |
10452 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 7 |
Correct |
115 ms |
10916 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 8 |
Correct |
40 ms |
10164 KB |
Output is correct - 67570 call(s) of encode_bit() |
| 9 |
Correct |
59 ms |
10212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 10 |
Correct |
55 ms |
10268 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 11 |
Correct |
72 ms |
10420 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 12 |
Correct |
38 ms |
10448 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 13 |
Correct |
145 ms |
11068 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 14 |
Correct |
57 ms |
10392 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 15 |
Correct |
54 ms |
10512 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 16 |
Correct |
124 ms |
10888 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 17 |
Correct |
107 ms |
10896 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 18 |
Correct |
158 ms |
11144 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 19 |
Correct |
92 ms |
10748 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 20 |
Correct |
179 ms |
11464 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 21 |
Correct |
201 ms |
11784 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 22 |
Correct |
128 ms |
11048 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 23 |
Correct |
230 ms |
11760 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
15212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 100 call(s) of encode_bit() |
| 3 |
Correct |
50 ms |
9508 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 4 |
Incorrect |
2 ms |
4612 KB |
Output isn't correct |
| 5 |
Correct |
62 ms |
9652 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 6 |
Correct |
69 ms |
10452 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 7 |
Correct |
115 ms |
10916 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 8 |
Correct |
40 ms |
10164 KB |
Output is correct - 67570 call(s) of encode_bit() |
| 9 |
Correct |
59 ms |
10212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 10 |
Correct |
55 ms |
10268 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 11 |
Correct |
72 ms |
10420 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 12 |
Correct |
38 ms |
10448 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 13 |
Correct |
145 ms |
11068 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 14 |
Correct |
57 ms |
10392 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 15 |
Correct |
54 ms |
10512 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 16 |
Correct |
124 ms |
10888 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 17 |
Correct |
107 ms |
10896 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 18 |
Correct |
158 ms |
11144 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 19 |
Correct |
92 ms |
10748 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 20 |
Correct |
179 ms |
11464 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 21 |
Correct |
201 ms |
11784 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 22 |
Correct |
128 ms |
11048 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 23 |
Correct |
230 ms |
11760 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
15212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 100 call(s) of encode_bit() |
| 3 |
Correct |
50 ms |
9508 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 4 |
Incorrect |
2 ms |
4612 KB |
Output isn't correct |
| 5 |
Correct |
62 ms |
9652 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 6 |
Correct |
69 ms |
10452 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 7 |
Correct |
115 ms |
10916 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 8 |
Correct |
40 ms |
10164 KB |
Output is correct - 67570 call(s) of encode_bit() |
| 9 |
Correct |
59 ms |
10212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 10 |
Correct |
55 ms |
10268 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 11 |
Correct |
72 ms |
10420 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 12 |
Correct |
38 ms |
10448 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 13 |
Correct |
145 ms |
11068 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 14 |
Correct |
57 ms |
10392 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 15 |
Correct |
54 ms |
10512 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 16 |
Correct |
124 ms |
10888 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 17 |
Correct |
107 ms |
10896 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 18 |
Correct |
158 ms |
11144 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 19 |
Correct |
92 ms |
10748 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 20 |
Correct |
179 ms |
11464 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 21 |
Correct |
201 ms |
11784 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 22 |
Correct |
128 ms |
11048 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 23 |
Correct |
230 ms |
11760 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
695 ms |
15212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4604 KB |
Output is correct - 100 call(s) of encode_bit() |
| 3 |
Correct |
50 ms |
9508 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 4 |
Incorrect |
2 ms |
4612 KB |
Output isn't correct |
| 5 |
Correct |
62 ms |
9652 KB |
Output is correct - 63300 call(s) of encode_bit() |
| 6 |
Correct |
69 ms |
10452 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 7 |
Correct |
115 ms |
10916 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 8 |
Correct |
40 ms |
10164 KB |
Output is correct - 67570 call(s) of encode_bit() |
| 9 |
Correct |
59 ms |
10212 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 10 |
Correct |
55 ms |
10268 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 11 |
Correct |
72 ms |
10420 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 12 |
Correct |
38 ms |
10448 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 13 |
Correct |
145 ms |
11068 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 14 |
Correct |
57 ms |
10392 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 15 |
Correct |
54 ms |
10512 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 16 |
Correct |
124 ms |
10888 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 17 |
Correct |
107 ms |
10896 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 18 |
Correct |
158 ms |
11144 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 19 |
Correct |
92 ms |
10748 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 20 |
Correct |
179 ms |
11464 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 21 |
Correct |
201 ms |
11784 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 22 |
Correct |
128 ms |
11048 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
| 23 |
Correct |
230 ms |
11760 KB |
Output is partially correct - 70300 call(s) of encode_bit() |
