oj.uz

Submission #574377

# Submission time Handle Problem Language Result Execution time Memory
574377 2022-06-08T12:46:36 Z SlavicG Saveit (IOI10_saveit) C++17
0 / 100
 701 ms 14556 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({});
    for(int j = 0; j < h; ++j) {
        vector<int> v;
        for(int i = 0; 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 {
                assert(dist[i][j] == dist[parent[i]][j] + 1);
                v.pb(2);
            }
        }
        for(int i = 0; i + 2 < n; 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(n % 3 == 1) {
            for(int f = 0; f < 2; ++f) {
                if(v.back() & (1 << f)) encode_bit(1);
                else encode_bit(0);
            }
        } else if(n % 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({});
    for(int j = 0; j < h; ++j) {
        for(int i = 0; i + 2 < n; i += 3) {
            int number = 0;
            for(int f = 0; f < 5; ++f) {
                if(decode_bit()) number += (1 << f);
            }
            vector<int> f = Paiu[number];
            type[i][j] = f[0], type[i + 1][j] = f[1], type[i + 2][j] = f[2];
        }
        if(n % 3 == 1) {
            for(int f = 0; f < 2; ++f) {
                if(decode_bit()) type[n - 1][j] += (1 << f);
            }
        } else if(n % 3 == 2) {
            for(int k = n - 2; k < n; ++k) {
                for(int f = 0; f < 2; ++f) {
                    if(decode_bit()) type[k][j] += (1 << f);
                }
            }
        }
    }
    dfs(0, -1, h);
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < n; ++j) {
            dist[i][j] = dist[j][i];
        }
    }
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < n; ++j) {
            hops(i, j, dist[i][j]);
        }
    }
}
/*
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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 701 ms 14556 KB Output isn't correct
2 Correct 3 ms 4600 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 56 ms 8864 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 60 ms 8960 KB Output isn't correct
6 Incorrect 68 ms 9860 KB Output isn't correct
7 Incorrect 124 ms 10380 KB Output isn't correct
8 Incorrect 41 ms 9436 KB Output isn't correct
9 Incorrect 54 ms 9540 KB Output isn't correct
10 Incorrect 51 ms 9624 KB Output isn't correct
11 Incorrect 73 ms 9828 KB Output isn't correct
12 Incorrect 37 ms 9760 KB Output isn't correct
13 Incorrect 145 ms 10304 KB Output isn't correct
14 Incorrect 47 ms 9800 KB Output isn't correct
15 Incorrect 51 ms 9912 KB Output isn't correct
16 Incorrect 127 ms 10348 KB Output isn't correct
17 Incorrect 119 ms 10320 KB Output isn't correct
18 Incorrect 147 ms 10592 KB Output isn't correct
19 Incorrect 86 ms 10148 KB Output isn't correct
20 Incorrect 226 ms 10860 KB Output isn't correct
21 Incorrect 210 ms 11052 KB Output isn't correct
22 Incorrect 130 ms 10500 KB Output isn't correct
23 Incorrect 212 ms 11224 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 701 ms 14556 KB Output isn't correct
2 Correct 3 ms 4600 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 56 ms 8864 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 60 ms 8960 KB Output isn't correct
6 Incorrect 68 ms 9860 KB Output isn't correct
7 Incorrect 124 ms 10380 KB Output isn't correct
8 Incorrect 41 ms 9436 KB Output isn't correct
9 Incorrect 54 ms 9540 KB Output isn't correct
10 Incorrect 51 ms 9624 KB Output isn't correct
11 Incorrect 73 ms 9828 KB Output isn't correct
12 Incorrect 37 ms 9760 KB Output isn't correct
13 Incorrect 145 ms 10304 KB Output isn't correct
14 Incorrect 47 ms 9800 KB Output isn't correct
15 Incorrect 51 ms 9912 KB Output isn't correct
16 Incorrect 127 ms 10348 KB Output isn't correct
17 Incorrect 119 ms 10320 KB Output isn't correct
18 Incorrect 147 ms 10592 KB Output isn't correct
19 Incorrect 86 ms 10148 KB Output isn't correct
20 Incorrect 226 ms 10860 KB Output isn't correct
21 Incorrect 210 ms 11052 KB Output isn't correct
22 Incorrect 130 ms 10500 KB Output isn't correct
23 Incorrect 212 ms 11224 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 701 ms 14556 KB Output isn't correct
2 Correct 3 ms 4600 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 56 ms 8864 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 60 ms 8960 KB Output isn't correct
6 Incorrect 68 ms 9860 KB Output isn't correct
7 Incorrect 124 ms 10380 KB Output isn't correct
8 Incorrect 41 ms 9436 KB Output isn't correct
9 Incorrect 54 ms 9540 KB Output isn't correct
10 Incorrect 51 ms 9624 KB Output isn't correct
11 Incorrect 73 ms 9828 KB Output isn't correct
12 Incorrect 37 ms 9760 KB Output isn't correct
13 Incorrect 145 ms 10304 KB Output isn't correct
14 Incorrect 47 ms 9800 KB Output isn't correct
15 Incorrect 51 ms 9912 KB Output isn't correct
16 Incorrect 127 ms 10348 KB Output isn't correct
17 Incorrect 119 ms 10320 KB Output isn't correct
18 Incorrect 147 ms 10592 KB Output isn't correct
19 Incorrect 86 ms 10148 KB Output isn't correct
20 Incorrect 226 ms 10860 KB Output isn't correct
21 Incorrect 210 ms 11052 KB Output isn't correct
22 Incorrect 130 ms 10500 KB Output isn't correct
23 Incorrect 212 ms 11224 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 701 ms 14556 KB Output isn't correct
2 Correct 3 ms 4600 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 56 ms 8864 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 60 ms 8960 KB Output isn't correct
6 Incorrect 68 ms 9860 KB Output isn't correct
7 Incorrect 124 ms 10380 KB Output isn't correct
8 Incorrect 41 ms 9436 KB Output isn't correct
9 Incorrect 54 ms 9540 KB Output isn't correct
10 Incorrect 51 ms 9624 KB Output isn't correct
11 Incorrect 73 ms 9828 KB Output isn't correct
12 Incorrect 37 ms 9760 KB Output isn't correct
13 Incorrect 145 ms 10304 KB Output isn't correct
14 Incorrect 47 ms 9800 KB Output isn't correct
15 Incorrect 51 ms 9912 KB Output isn't correct
16 Incorrect 127 ms 10348 KB Output isn't correct
17 Incorrect 119 ms 10320 KB Output isn't correct
18 Incorrect 147 ms 10592 KB Output isn't correct
19 Incorrect 86 ms 10148 KB Output isn't correct
20 Incorrect 226 ms 10860 KB Output isn't correct
21 Incorrect 210 ms 11052 KB Output isn't correct
22 Incorrect 130 ms 10500 KB Output isn't correct
23 Incorrect 212 ms 11224 KB Output isn't correct