oj.uz

Submission #574370

# Submission time Handle Problem Language Result Execution time Memory
574370 2022-06-08T12:37:32 Z SlavicG Saveit (IOI10_saveit) C++17
0 / 100
 660 ms 14684 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 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 660 ms 14684 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8824 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 75 ms 8964 KB Output isn't correct
6 Incorrect 67 ms 9856 KB Output isn't correct
7 Incorrect 118 ms 10240 KB Output isn't correct
8 Incorrect 40 ms 9464 KB Output isn't correct
9 Incorrect 57 ms 9660 KB Output isn't correct
10 Incorrect 51 ms 9536 KB Output isn't correct
11 Incorrect 73 ms 9696 KB Output isn't correct
12 Incorrect 37 ms 9788 KB Output isn't correct
13 Incorrect 155 ms 10368 KB Output isn't correct
14 Incorrect 49 ms 9868 KB Output isn't correct
15 Incorrect 54 ms 9856 KB Output isn't correct
16 Incorrect 126 ms 10388 KB Output isn't correct
17 Incorrect 113 ms 10232 KB Output isn't correct
18 Incorrect 142 ms 10496 KB Output isn't correct
19 Incorrect 95 ms 10052 KB Output isn't correct
20 Incorrect 172 ms 10788 KB Output isn't correct
21 Incorrect 202 ms 10992 KB Output isn't correct
22 Incorrect 148 ms 10420 KB Output isn't correct
23 Incorrect 233 ms 11228 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 660 ms 14684 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8824 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 75 ms 8964 KB Output isn't correct
6 Incorrect 67 ms 9856 KB Output isn't correct
7 Incorrect 118 ms 10240 KB Output isn't correct
8 Incorrect 40 ms 9464 KB Output isn't correct
9 Incorrect 57 ms 9660 KB Output isn't correct
10 Incorrect 51 ms 9536 KB Output isn't correct
11 Incorrect 73 ms 9696 KB Output isn't correct
12 Incorrect 37 ms 9788 KB Output isn't correct
13 Incorrect 155 ms 10368 KB Output isn't correct
14 Incorrect 49 ms 9868 KB Output isn't correct
15 Incorrect 54 ms 9856 KB Output isn't correct
16 Incorrect 126 ms 10388 KB Output isn't correct
17 Incorrect 113 ms 10232 KB Output isn't correct
18 Incorrect 142 ms 10496 KB Output isn't correct
19 Incorrect 95 ms 10052 KB Output isn't correct
20 Incorrect 172 ms 10788 KB Output isn't correct
21 Incorrect 202 ms 10992 KB Output isn't correct
22 Incorrect 148 ms 10420 KB Output isn't correct
23 Incorrect 233 ms 11228 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 660 ms 14684 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8824 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 75 ms 8964 KB Output isn't correct
6 Incorrect 67 ms 9856 KB Output isn't correct
7 Incorrect 118 ms 10240 KB Output isn't correct
8 Incorrect 40 ms 9464 KB Output isn't correct
9 Incorrect 57 ms 9660 KB Output isn't correct
10 Incorrect 51 ms 9536 KB Output isn't correct
11 Incorrect 73 ms 9696 KB Output isn't correct
12 Incorrect 37 ms 9788 KB Output isn't correct
13 Incorrect 155 ms 10368 KB Output isn't correct
14 Incorrect 49 ms 9868 KB Output isn't correct
15 Incorrect 54 ms 9856 KB Output isn't correct
16 Incorrect 126 ms 10388 KB Output isn't correct
17 Incorrect 113 ms 10232 KB Output isn't correct
18 Incorrect 142 ms 10496 KB Output isn't correct
19 Incorrect 95 ms 10052 KB Output isn't correct
20 Incorrect 172 ms 10788 KB Output isn't correct
21 Incorrect 202 ms 10992 KB Output isn't correct
22 Incorrect 148 ms 10420 KB Output isn't correct
23 Incorrect 233 ms 11228 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 660 ms 14684 KB Output isn't correct
2 Correct 2 ms 4612 KB Output is correct - 107 call(s) of encode_bit()
3 Incorrect 53 ms 8824 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 145 call(s) of encode_bit()
5 Incorrect 75 ms 8964 KB Output isn't correct
6 Incorrect 67 ms 9856 KB Output isn't correct
7 Incorrect 118 ms 10240 KB Output isn't correct
8 Incorrect 40 ms 9464 KB Output isn't correct
9 Incorrect 57 ms 9660 KB Output isn't correct
10 Incorrect 51 ms 9536 KB Output isn't correct
11 Incorrect 73 ms 9696 KB Output isn't correct
12 Incorrect 37 ms 9788 KB Output isn't correct
13 Incorrect 155 ms 10368 KB Output isn't correct
14 Incorrect 49 ms 9868 KB Output isn't correct
15 Incorrect 54 ms 9856 KB Output isn't correct
16 Incorrect 126 ms 10388 KB Output isn't correct
17 Incorrect 113 ms 10232 KB Output isn't correct
18 Incorrect 142 ms 10496 KB Output isn't correct
19 Incorrect 95 ms 10052 KB Output isn't correct
20 Incorrect 172 ms 10788 KB Output isn't correct
21 Incorrect 202 ms 10992 KB Output isn't correct
22 Incorrect 148 ms 10420 KB Output isn't correct
23 Incorrect 233 ms 11228 KB Output isn't correct