oj.uz

Submission #574498

# Submission time Handle Problem Language Result Execution time Memory
574498 2022-06-08T15:48:19 Z SlavicG Saveit (IOI10_saveit) C++17
0 / 100
 754 ms 15108 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 = 1; i < n; ++i) {
        for(int j = 0; j < 9; ++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 = 1;i < n; ++i) {
        int node = 0;
        for(int j = 0; j < 9; ++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[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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 754 ms 15108 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 86 call(s) of encode_bit()
3 Incorrect 47 ms 9500 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 59 ms 9632 KB wrong parameter
6 Incorrect 74 ms 10404 KB wrong parameter
7 Incorrect 120 ms 10784 KB wrong parameter
8 Incorrect 39 ms 9888 KB Output isn't correct
9 Incorrect 56 ms 10376 KB Output isn't correct
10 Incorrect 51 ms 10264 KB Output isn't correct
11 Incorrect 64 ms 10392 KB wrong parameter
12 Incorrect 40 ms 10272 KB Output isn't correct
13 Incorrect 135 ms 10916 KB wrong parameter
14 Incorrect 49 ms 10276 KB Output isn't correct
15 Incorrect 50 ms 10468 KB wrong parameter
16 Incorrect 129 ms 10888 KB Output isn't correct
17 Incorrect 111 ms 10776 KB Output isn't correct
18 Incorrect 155 ms 11072 KB wrong parameter
19 Incorrect 93 ms 10592 KB Output isn't correct
20 Incorrect 184 ms 11456 KB wrong parameter
21 Incorrect 195 ms 11540 KB wrong parameter
22 Incorrect 130 ms 10972 KB wrong parameter
23 Incorrect 210 ms 11736 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 754 ms 15108 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 86 call(s) of encode_bit()
3 Incorrect 47 ms 9500 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 59 ms 9632 KB wrong parameter
6 Incorrect 74 ms 10404 KB wrong parameter
7 Incorrect 120 ms 10784 KB wrong parameter
8 Incorrect 39 ms 9888 KB Output isn't correct
9 Incorrect 56 ms 10376 KB Output isn't correct
10 Incorrect 51 ms 10264 KB Output isn't correct
11 Incorrect 64 ms 10392 KB wrong parameter
12 Incorrect 40 ms 10272 KB Output isn't correct
13 Incorrect 135 ms 10916 KB wrong parameter
14 Incorrect 49 ms 10276 KB Output isn't correct
15 Incorrect 50 ms 10468 KB wrong parameter
16 Incorrect 129 ms 10888 KB Output isn't correct
17 Incorrect 111 ms 10776 KB Output isn't correct
18 Incorrect 155 ms 11072 KB wrong parameter
19 Incorrect 93 ms 10592 KB Output isn't correct
20 Incorrect 184 ms 11456 KB wrong parameter
21 Incorrect 195 ms 11540 KB wrong parameter
22 Incorrect 130 ms 10972 KB wrong parameter
23 Incorrect 210 ms 11736 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 754 ms 15108 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 86 call(s) of encode_bit()
3 Incorrect 47 ms 9500 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 59 ms 9632 KB wrong parameter
6 Incorrect 74 ms 10404 KB wrong parameter
7 Incorrect 120 ms 10784 KB wrong parameter
8 Incorrect 39 ms 9888 KB Output isn't correct
9 Incorrect 56 ms 10376 KB Output isn't correct
10 Incorrect 51 ms 10264 KB Output isn't correct
11 Incorrect 64 ms 10392 KB wrong parameter
12 Incorrect 40 ms 10272 KB Output isn't correct
13 Incorrect 135 ms 10916 KB wrong parameter
14 Incorrect 49 ms 10276 KB Output isn't correct
15 Incorrect 50 ms 10468 KB wrong parameter
16 Incorrect 129 ms 10888 KB Output isn't correct
17 Incorrect 111 ms 10776 KB Output isn't correct
18 Incorrect 155 ms 11072 KB wrong parameter
19 Incorrect 93 ms 10592 KB Output isn't correct
20 Incorrect 184 ms 11456 KB wrong parameter
21 Incorrect 195 ms 11540 KB wrong parameter
22 Incorrect 130 ms 10972 KB wrong parameter
23 Incorrect 210 ms 11736 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 754 ms 15108 KB wrong parameter
2 Correct 2 ms 4612 KB Output is correct - 86 call(s) of encode_bit()
3 Incorrect 47 ms 9500 KB wrong parameter
4 Correct 2 ms 4604 KB Output is correct - 120 call(s) of encode_bit()
5 Incorrect 59 ms 9632 KB wrong parameter
6 Incorrect 74 ms 10404 KB wrong parameter
7 Incorrect 120 ms 10784 KB wrong parameter
8 Incorrect 39 ms 9888 KB Output isn't correct
9 Incorrect 56 ms 10376 KB Output isn't correct
10 Incorrect 51 ms 10264 KB Output isn't correct
11 Incorrect 64 ms 10392 KB wrong parameter
12 Incorrect 40 ms 10272 KB Output isn't correct
13 Incorrect 135 ms 10916 KB wrong parameter
14 Incorrect 49 ms 10276 KB Output isn't correct
15 Incorrect 50 ms 10468 KB wrong parameter
16 Incorrect 129 ms 10888 KB Output isn't correct
17 Incorrect 111 ms 10776 KB Output isn't correct
18 Incorrect 155 ms 11072 KB wrong parameter
19 Incorrect 93 ms 10592 KB Output isn't correct
20 Incorrect 184 ms 11456 KB wrong parameter
21 Incorrect 195 ms 11540 KB wrong parameter
22 Incorrect 130 ms 10972 KB wrong parameter
23 Incorrect 210 ms 11736 KB Output isn't correct