oj.uz

답안 #574462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574462 2022-06-08T15:25:39 Z SlavicG 저장 (Saveit) (IOI10_saveit) C++17
75 / 100
 675 ms 14572 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 = 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 {
                    assert(dist[i][j] == dist[parent[i]][j] + 1);
                    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 = 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 = 1; 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 - 1) % 3 == 1) {
                for(int f = 0; f < 2; ++f) {
                    if(decode_bit()) type[n - 1][j] += (1 << f);
                }
            } else if((n - 1) % 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) {
                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

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 14572 KB Output is partially correct - 70300 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 101 call(s) of encode_bit()
3 Correct 51 ms 8868 KB Output is correct - 63324 call(s) of encode_bit()
4 Correct 3 ms 4604 KB Output is correct - 135 call(s) of encode_bit()
5 Correct 67 ms 9124 KB Output is correct - 63324 call(s) of encode_bit()
6 Correct 72 ms 9844 KB Output is partially correct - 70300 call(s) of encode_bit()
7 Correct 118 ms 10252 KB Output is partially correct - 70300 call(s) of encode_bit()
8 Correct 53 ms 9380 KB Output is correct - 67570 call(s) of encode_bit()
9 Correct 54 ms 9568 KB Output is partially correct - 70300 call(s) of encode_bit()
10 Correct 51 ms 9712 KB Output is partially correct - 70300 call(s) of encode_bit()
11 Correct 65 ms 9876 KB Output is partially correct - 70300 call(s) of encode_bit()
12 Correct 39 ms 9840 KB Output is partially correct - 70300 call(s) of encode_bit()
13 Correct 154 ms 10460 KB Output is partially correct - 70300 call(s) of encode_bit()
14 Correct 54 ms 9872 KB Output is partially correct - 70300 call(s) of encode_bit()
15 Correct 51 ms 9964 KB Output is partially correct - 70300 call(s) of encode_bit()
16 Correct 125 ms 10300 KB Output is partially correct - 70300 call(s) of encode_bit()
17 Correct 113 ms 10308 KB Output is partially correct - 70300 call(s) of encode_bit()
18 Correct 147 ms 10584 KB Output is partially correct - 70300 call(s) of encode_bit()
19 Correct 84 ms 10152 KB Output is partially correct - 70300 call(s) of encode_bit()
20 Correct 183 ms 10860 KB Output is partially correct - 70300 call(s) of encode_bit()
21 Correct 203 ms 10988 KB Output is partially correct - 70300 call(s) of encode_bit()
22 Correct 136 ms 10412 KB Output is partially correct - 70300 call(s) of encode_bit()
23 Correct 235 ms 11200 KB Output is partially correct - 70300 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 14572 KB Output is partially correct - 70300 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 101 call(s) of encode_bit()
3 Correct 51 ms 8868 KB Output is correct - 63324 call(s) of encode_bit()
4 Correct 3 ms 4604 KB Output is correct - 135 call(s) of encode_bit()
5 Correct 67 ms 9124 KB Output is correct - 63324 call(s) of encode_bit()
6 Correct 72 ms 9844 KB Output is partially correct - 70300 call(s) of encode_bit()
7 Correct 118 ms 10252 KB Output is partially correct - 70300 call(s) of encode_bit()
8 Correct 53 ms 9380 KB Output is correct - 67570 call(s) of encode_bit()
9 Correct 54 ms 9568 KB Output is partially correct - 70300 call(s) of encode_bit()
10 Correct 51 ms 9712 KB Output is partially correct - 70300 call(s) of encode_bit()
11 Correct 65 ms 9876 KB Output is partially correct - 70300 call(s) of encode_bit()
12 Correct 39 ms 9840 KB Output is partially correct - 70300 call(s) of encode_bit()
13 Correct 154 ms 10460 KB Output is partially correct - 70300 call(s) of encode_bit()
14 Correct 54 ms 9872 KB Output is partially correct - 70300 call(s) of encode_bit()
15 Correct 51 ms 9964 KB Output is partially correct - 70300 call(s) of encode_bit()
16 Correct 125 ms 10300 KB Output is partially correct - 70300 call(s) of encode_bit()
17 Correct 113 ms 10308 KB Output is partially correct - 70300 call(s) of encode_bit()
18 Correct 147 ms 10584 KB Output is partially correct - 70300 call(s) of encode_bit()
19 Correct 84 ms 10152 KB Output is partially correct - 70300 call(s) of encode_bit()
20 Correct 183 ms 10860 KB Output is partially correct - 70300 call(s) of encode_bit()
21 Correct 203 ms 10988 KB Output is partially correct - 70300 call(s) of encode_bit()
22 Correct 136 ms 10412 KB Output is partially correct - 70300 call(s) of encode_bit()
23 Correct 235 ms 11200 KB Output is partially correct - 70300 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 14572 KB Output is partially correct - 70300 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 101 call(s) of encode_bit()
3 Correct 51 ms 8868 KB Output is correct - 63324 call(s) of encode_bit()
4 Correct 3 ms 4604 KB Output is correct - 135 call(s) of encode_bit()
5 Correct 67 ms 9124 KB Output is correct - 63324 call(s) of encode_bit()
6 Correct 72 ms 9844 KB Output is partially correct - 70300 call(s) of encode_bit()
7 Correct 118 ms 10252 KB Output is partially correct - 70300 call(s) of encode_bit()
8 Correct 53 ms 9380 KB Output is correct - 67570 call(s) of encode_bit()
9 Correct 54 ms 9568 KB Output is partially correct - 70300 call(s) of encode_bit()
10 Correct 51 ms 9712 KB Output is partially correct - 70300 call(s) of encode_bit()
11 Correct 65 ms 9876 KB Output is partially correct - 70300 call(s) of encode_bit()
12 Correct 39 ms 9840 KB Output is partially correct - 70300 call(s) of encode_bit()
13 Correct 154 ms 10460 KB Output is partially correct - 70300 call(s) of encode_bit()
14 Correct 54 ms 9872 KB Output is partially correct - 70300 call(s) of encode_bit()
15 Correct 51 ms 9964 KB Output is partially correct - 70300 call(s) of encode_bit()
16 Correct 125 ms 10300 KB Output is partially correct - 70300 call(s) of encode_bit()
17 Correct 113 ms 10308 KB Output is partially correct - 70300 call(s) of encode_bit()
18 Correct 147 ms 10584 KB Output is partially correct - 70300 call(s) of encode_bit()
19 Correct 84 ms 10152 KB Output is partially correct - 70300 call(s) of encode_bit()
20 Correct 183 ms 10860 KB Output is partially correct - 70300 call(s) of encode_bit()
21 Correct 203 ms 10988 KB Output is partially correct - 70300 call(s) of encode_bit()
22 Correct 136 ms 10412 KB Output is partially correct - 70300 call(s) of encode_bit()
23 Correct 235 ms 11200 KB Output is partially correct - 70300 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 14572 KB Output is partially correct - 70300 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 101 call(s) of encode_bit()
3 Correct 51 ms 8868 KB Output is correct - 63324 call(s) of encode_bit()
4 Correct 3 ms 4604 KB Output is correct - 135 call(s) of encode_bit()
5 Correct 67 ms 9124 KB Output is correct - 63324 call(s) of encode_bit()
6 Correct 72 ms 9844 KB Output is partially correct - 70300 call(s) of encode_bit()
7 Correct 118 ms 10252 KB Output is partially correct - 70300 call(s) of encode_bit()
8 Correct 53 ms 9380 KB Output is correct - 67570 call(s) of encode_bit()
9 Correct 54 ms 9568 KB Output is partially correct - 70300 call(s) of encode_bit()
10 Correct 51 ms 9712 KB Output is partially correct - 70300 call(s) of encode_bit()
11 Correct 65 ms 9876 KB Output is partially correct - 70300 call(s) of encode_bit()
12 Correct 39 ms 9840 KB Output is partially correct - 70300 call(s) of encode_bit()
13 Correct 154 ms 10460 KB Output is partially correct - 70300 call(s) of encode_bit()
14 Correct 54 ms 9872 KB Output is partially correct - 70300 call(s) of encode_bit()
15 Correct 51 ms 9964 KB Output is partially correct - 70300 call(s) of encode_bit()
16 Correct 125 ms 10300 KB Output is partially correct - 70300 call(s) of encode_bit()
17 Correct 113 ms 10308 KB Output is partially correct - 70300 call(s) of encode_bit()
18 Correct 147 ms 10584 KB Output is partially correct - 70300 call(s) of encode_bit()
19 Correct 84 ms 10152 KB Output is partially correct - 70300 call(s) of encode_bit()
20 Correct 183 ms 10860 KB Output is partially correct - 70300 call(s) of encode_bit()
21 Correct 203 ms 10988 KB Output is partially correct - 70300 call(s) of encode_bit()
22 Correct 136 ms 10412 KB Output is partially correct - 70300 call(s) of encode_bit()
23 Correct 235 ms 11200 KB Output is partially correct - 70300 call(s) of encode_bit()