oj.uz

Submission #574367

# Submission time Handle Problem Language Result Execution time Memory
574367 2022-06-08T12:29:11 Z SlavicG Saveit (IOI10_saveit) C++17
0 / 100
 664 ms 14664 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 v.pb(2);
        }
        for(int i = 0; i + 2 < n; i += 3) {
            for(int j = 0; j < 5; ++j) {
                if(mp[{v[i], v[i + 1], v[i + 2]}] & (1 << j)) {
                    encode_bit(1);
                } else encode_bit(0);
            }
        }
        if(n % 3 == 1) {
            for(int j = 0; j < 2; ++j) {
                if(v.back() & (1 << j)) encode_bit(1);
                else encode_bit(0);
            }
        } else if(n % 3 == 2) {
            for(int k = sz(v) - 2; k < sz(v); ++k) {
                for(int j = 0; j < 2; ++j) {
                    if(v[k] & (1 << j)) 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 j = 0; j < 5; ++j) {
                if(decode_bit()) number += (1 << j);
            }
            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 664 ms 14664 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8892 KB Output isn't correct
4 Correct 3 ms 4612 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 67 ms 9024 KB Output isn't correct
6 Incorrect 81 ms 9796 KB Output isn't correct
7 Incorrect 124 ms 10316 KB Output isn't correct
8 Incorrect 39 ms 9524 KB Output isn't correct
9 Incorrect 52 ms 9536 KB Output isn't correct
10 Incorrect 57 ms 9508 KB Output isn't correct
11 Incorrect 80 ms 9752 KB Output isn't correct
12 Incorrect 43 ms 9748 KB Output isn't correct
13 Incorrect 156 ms 10500 KB Output isn't correct
14 Incorrect 47 ms 9696 KB Output isn't correct
15 Incorrect 54 ms 9888 KB Output isn't correct
16 Incorrect 123 ms 10244 KB Output isn't correct
17 Incorrect 110 ms 10196 KB Output isn't correct
18 Incorrect 144 ms 10492 KB Output isn't correct
19 Incorrect 94 ms 9928 KB Output isn't correct
20 Incorrect 169 ms 10868 KB Output isn't correct
21 Incorrect 194 ms 10988 KB Output isn't correct
22 Incorrect 132 ms 10468 KB Output isn't correct
23 Incorrect 220 ms 11112 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 664 ms 14664 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8892 KB Output isn't correct
4 Correct 3 ms 4612 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 67 ms 9024 KB Output isn't correct
6 Incorrect 81 ms 9796 KB Output isn't correct
7 Incorrect 124 ms 10316 KB Output isn't correct
8 Incorrect 39 ms 9524 KB Output isn't correct
9 Incorrect 52 ms 9536 KB Output isn't correct
10 Incorrect 57 ms 9508 KB Output isn't correct
11 Incorrect 80 ms 9752 KB Output isn't correct
12 Incorrect 43 ms 9748 KB Output isn't correct
13 Incorrect 156 ms 10500 KB Output isn't correct
14 Incorrect 47 ms 9696 KB Output isn't correct
15 Incorrect 54 ms 9888 KB Output isn't correct
16 Incorrect 123 ms 10244 KB Output isn't correct
17 Incorrect 110 ms 10196 KB Output isn't correct
18 Incorrect 144 ms 10492 KB Output isn't correct
19 Incorrect 94 ms 9928 KB Output isn't correct
20 Incorrect 169 ms 10868 KB Output isn't correct
21 Incorrect 194 ms 10988 KB Output isn't correct
22 Incorrect 132 ms 10468 KB Output isn't correct
23 Incorrect 220 ms 11112 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 664 ms 14664 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8892 KB Output isn't correct
4 Correct 3 ms 4612 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 67 ms 9024 KB Output isn't correct
6 Incorrect 81 ms 9796 KB Output isn't correct
7 Incorrect 124 ms 10316 KB Output isn't correct
8 Incorrect 39 ms 9524 KB Output isn't correct
9 Incorrect 52 ms 9536 KB Output isn't correct
10 Incorrect 57 ms 9508 KB Output isn't correct
11 Incorrect 80 ms 9752 KB Output isn't correct
12 Incorrect 43 ms 9748 KB Output isn't correct
13 Incorrect 156 ms 10500 KB Output isn't correct
14 Incorrect 47 ms 9696 KB Output isn't correct
15 Incorrect 54 ms 9888 KB Output isn't correct
16 Incorrect 123 ms 10244 KB Output isn't correct
17 Incorrect 110 ms 10196 KB Output isn't correct
18 Incorrect 144 ms 10492 KB Output isn't correct
19 Incorrect 94 ms 9928 KB Output isn't correct
20 Incorrect 169 ms 10868 KB Output isn't correct
21 Incorrect 194 ms 10988 KB Output isn't correct
22 Incorrect 132 ms 10468 KB Output isn't correct
23 Incorrect 220 ms 11112 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 664 ms 14664 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8892 KB Output isn't correct
4 Correct 3 ms 4612 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 67 ms 9024 KB Output isn't correct
6 Incorrect 81 ms 9796 KB Output isn't correct
7 Incorrect 124 ms 10316 KB Output isn't correct
8 Incorrect 39 ms 9524 KB Output isn't correct
9 Incorrect 52 ms 9536 KB Output isn't correct
10 Incorrect 57 ms 9508 KB Output isn't correct
11 Incorrect 80 ms 9752 KB Output isn't correct
12 Incorrect 43 ms 9748 KB Output isn't correct
13 Incorrect 156 ms 10500 KB Output isn't correct
14 Incorrect 47 ms 9696 KB Output isn't correct
15 Incorrect 54 ms 9888 KB Output isn't correct
16 Incorrect 123 ms 10244 KB Output isn't correct
17 Incorrect 110 ms 10196 KB Output isn't correct
18 Incorrect 144 ms 10492 KB Output isn't correct
19 Incorrect 94 ms 9928 KB Output isn't correct
20 Incorrect 169 ms 10868 KB Output isn't correct
21 Incorrect 194 ms 10988 KB Output isn't correct
22 Incorrect 132 ms 10468 KB Output isn't correct
23 Incorrect 220 ms 11112 KB Output isn't correct