oj.uz

Submission #574503

# Submission time Handle Problem Language Result Execution time Memory
574503 2022-06-08T15:55:30 Z SlavicG Saveit (IOI10_saveit) C++17
100 / 100
 658 ms 15060 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 bfstree(int u, vector<bool>& vis, vector<vector<int>>& adj, vector<int>& par) {
    vis[u] = true;
    queue<int> q;
    q.push(u);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v: adj[u]) {
            if(!vis[v]) {
                q.push(v);
                vis[v] = true;
                par[v] = u;
            }
        }
    }
}
 
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);
    
    vector<bool> vis(n, false);
    vector<int> parent(n);
    iota(all(parent), 0);
 
    bfstree(0, vis, adj, parent);
 
    for(int i = 1; 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 get_distances(int u, int par, int depth) {
    dist[0][u] = depth;
    for(int v: adj[u]) {
        if(v == par) continue;
        get_distances(v, u, depth + 1);
    }
}

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 = 1;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);
    }
    
    get_distances(0, 0, 0);
    
    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[sz(v) - 1].first][v[sz(v) - 1].second] += (1 << f);
        }
    } else if(sz(v) % 3 == 2) {
        for(int k = sz(v) - 2; k < sz(v); ++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();
    }
}
*/

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 15060 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 60 ms 9264 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 74 call(s) of encode_bit()
5 Correct 67 ms 9400 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 81 ms 10312 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 129 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 40 ms 9900 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 59 ms 10240 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 57 ms 10252 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 69 ms 10352 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 39 ms 10316 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 157 ms 10912 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 49 ms 10276 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 52 ms 10408 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 148 ms 10788 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 150 ms 10940 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 93 ms 10552 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 193 ms 11264 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 213 ms 11408 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 140 ms 10932 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 252 ms 11644 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 15060 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 60 ms 9264 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 74 call(s) of encode_bit()
5 Correct 67 ms 9400 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 81 ms 10312 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 129 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 40 ms 9900 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 59 ms 10240 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 57 ms 10252 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 69 ms 10352 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 39 ms 10316 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 157 ms 10912 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 49 ms 10276 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 52 ms 10408 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 148 ms 10788 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 150 ms 10940 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 93 ms 10552 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 193 ms 11264 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 213 ms 11408 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 140 ms 10932 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 252 ms 11644 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 15060 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 60 ms 9264 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 74 call(s) of encode_bit()
5 Correct 67 ms 9400 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 81 ms 10312 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 129 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 40 ms 9900 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 59 ms 10240 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 57 ms 10252 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 69 ms 10352 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 39 ms 10316 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 157 ms 10912 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 49 ms 10276 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 52 ms 10408 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 148 ms 10788 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 150 ms 10940 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 93 ms 10552 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 193 ms 11264 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 213 ms 11408 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 140 ms 10932 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 252 ms 11644 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 15060 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 60 ms 9264 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4616 KB Output is correct - 74 call(s) of encode_bit()
5 Correct 67 ms 9400 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 81 ms 10312 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 129 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 40 ms 9900 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 59 ms 10240 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 57 ms 10252 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 69 ms 10352 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 39 ms 10316 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 157 ms 10912 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 49 ms 10276 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 52 ms 10408 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 148 ms 10788 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 10732 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 150 ms 10940 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 93 ms 10552 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 193 ms 11264 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 213 ms 11408 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 140 ms 10932 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 252 ms 11644 KB Output is correct - 69930 call(s) of encode_bit()