oj.uz

Submission #1090765

# Submission time Handle Problem Language Result Execution time Memory
1090765 2024-09-18T17:33:47 Z Tymond Saveit (IOI10_saveit) C++17
0 / 100
 142 ms 10636 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXN = 1e3 + 7;
const int MAXH = 40;
int dist[MAXH][MAXN];
int rep[MAXN];
int parent[MAXN];
vi g[MAXN];
vi gt[MAXN];
int n, h, m;

int Find(int a){
    if(a == rep[a]){
        return a;
    }
    return rep[a] = Find(rep[a]);
}

void Union(int a, int b){
    rep[Find(a)] = Find(b);
}

void dfs(int v, int p){
    parent[v] = p;
    for(auto u : g[v]){
        if(u == p){
            continue;
        }
        dfs(u, v);
    }
}

void countDist(int start){
    dist[start][start] = 0;
    queue<int> q;
    q.push(start);
    while(sz(q)){
        int v = q.front();
        q.pop();
 
        for(auto u : gt[v]){
            if(u == start){
                continue;
            }
            if(dist[start][u] == 0){
                dist[start][u] = dist[start][v] + 1;
                q.push(u);
            }
        }
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n = nv;
    h = nh;
    m = ne;
    for(int i = 0; i < n; i++){
        rep[i] = i;
    }
    for(int i = 0; i < m; i++){
        if(Find(v1[i]) != Find(v2[i])){
            g[v1[i]].pb(v2[i]);
            g[v2[i]].pb(v1[i]);
            Union(v1[i], v2[i]);
        }
        gt[v1[i]].pb(v2[i]);
        gt[v2[i]].pb(v1[i]);
    }

    dfs(0, 0);
    for(int i = 1; i < n; i++){
        for(int y = 0; y < 10; y++){
            if(parent[i] & (1 << y)){
                encode_bit(1);
            }else{
                encode_bit(0);
            }
        }
    }

    for(int i = 0; i < h; i++){
        countDist(i);
    }

    for(int j = 0; j < h; j++){
        for(int i = 0; i < n; i++){
            if(i + 2 >= n){
                if(dist[j][i] == dist[j][parent[i]]){
                    encode_bit(0);
                    encode_bit(0);
                }else if(dist[j][i] == dist[j][parent[i]] - 1){
                    encode_bit(0);
                    encode_bit(1);
                }else{
                    encode_bit(1);
                    encode_bit(1);
                }
                continue;
            }

            int r = 0;
            for(int y = i; y <= i + 2; y++){
                r = r * 3 + (dist[j][i] - dist[j][parent[i]] + 1);
            }

            for(int y = 0; y < 5; y++){
                if((1 << y) & r){
                    encode_bit(1);
                }else{
                    encode_bit(0);
                }
            }
            i += 2;
        }
    }

    return;
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXN = 1e3 + 7;
const int MAXH = 40;
int dist[MAXH][MAXN];
int parent[MAXN];
vi g[MAXN];
int n, h;

void countDist(int start){
    dist[start][start] = 0;
    queue<int> q;
    q.push(start);
    while(sz(q)){
        int v = q.front();
        q.pop();
 
        for(auto u : g[v]){
            if(u == start){
                continue;
            }
            if(dist[start][u] == 0){
                dist[start][u] = dist[start][v] + 1;
                q.push(u);
            }
        }
    }
}

void decode(int nv, int nh) {
    n = nv;
    h = nh;

    for(int i = 1; i < n; i++){
        for(int y = 0; y < 10; y++){
            if(decode_bit()){
                parent[i] += (1 << y);
            }
        }
        g[i].pb(parent[i]);
        g[parent[i]].pb(i);
    }

    for(int i = 0; i < n; i++){
        sort(all(g[i]));
    }

    for(int i = 0; i < h; i++){
        countDist(i);
    }

    for(int j = 0; j < h; j++){
        vi vec(n, 0);
        for(int i = 0; i < n; i++){
            if(i + 2 >= n){
                int x = decode_bit();
                int y = decode_bit();
                if(x == 0){
                    vec[i] = -y;
                }else{
                    vec[i] = 1;
                }
                continue;
            }

            int r = 0;
            for(int y = 0; y < 5; y++){
                r += (decode_bit() * (1 << y));
            }
            for(int y = i + 2; y >= i; y--){
                vec[y] = (r % 3) - 1;
                r /= 3;
            }

            i += 2;
        }

        queue<int> q;
        q.push(j);
        for(int i = 0; i < n; i++){
            dist[j][i] = -1;
        }
        dist[j][j] = 0;
        while(sz(q)){
            int v = q.front();
            q.pop();

            for(auto u : g[v]){
                if(u == parent[v] && dist[j][u] == -1){
                    dist[j][u] = dist[j][v] - vec[u];
                    q.push(u);
                }
                if(dist[j][u] == -1 && u != parent[v]){
                    dist[j][u] = dist[j][v] + vec[u];
                    q.push(u);
                }   
            }
        }
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < n; j++){
            hops(i, j, dist[i][j]);
        }
    }

    return;
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 10636 KB wrong parameter
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Incorrect 14 ms 5904 KB wrong parameter
4 Incorrect 2 ms 4620 KB Output isn't correct
5 Incorrect 14 ms 6008 KB wrong parameter
6 Incorrect 15 ms 6160 KB wrong parameter
7 Incorrect 24 ms 6476 KB wrong parameter
8 Incorrect 17 ms 5904 KB wrong parameter
9 Incorrect 13 ms 5904 KB wrong parameter
10 Incorrect 17 ms 5912 KB wrong parameter
11 Incorrect 14 ms 5904 KB wrong parameter
12 Incorrect 17 ms 5896 KB wrong parameter
13 Incorrect 33 ms 6384 KB wrong parameter
14 Incorrect 13 ms 5904 KB wrong parameter
15 Incorrect 14 ms 5944 KB wrong parameter
16 Incorrect 28 ms 6496 KB wrong parameter
17 Incorrect 25 ms 6388 KB wrong parameter
18 Incorrect 33 ms 6692 KB wrong parameter
19 Incorrect 27 ms 6196 KB wrong parameter
20 Incorrect 43 ms 6888 KB wrong parameter
21 Incorrect 48 ms 6908 KB wrong parameter
22 Incorrect 27 ms 6660 KB wrong parameter
23 Incorrect 43 ms 7080 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 10636 KB wrong parameter
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Incorrect 14 ms 5904 KB wrong parameter
4 Incorrect 2 ms 4620 KB Output isn't correct
5 Incorrect 14 ms 6008 KB wrong parameter
6 Incorrect 15 ms 6160 KB wrong parameter
7 Incorrect 24 ms 6476 KB wrong parameter
8 Incorrect 17 ms 5904 KB wrong parameter
9 Incorrect 13 ms 5904 KB wrong parameter
10 Incorrect 17 ms 5912 KB wrong parameter
11 Incorrect 14 ms 5904 KB wrong parameter
12 Incorrect 17 ms 5896 KB wrong parameter
13 Incorrect 33 ms 6384 KB wrong parameter
14 Incorrect 13 ms 5904 KB wrong parameter
15 Incorrect 14 ms 5944 KB wrong parameter
16 Incorrect 28 ms 6496 KB wrong parameter
17 Incorrect 25 ms 6388 KB wrong parameter
18 Incorrect 33 ms 6692 KB wrong parameter
19 Incorrect 27 ms 6196 KB wrong parameter
20 Incorrect 43 ms 6888 KB wrong parameter
21 Incorrect 48 ms 6908 KB wrong parameter
22 Incorrect 27 ms 6660 KB wrong parameter
23 Incorrect 43 ms 7080 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 10636 KB wrong parameter
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Incorrect 14 ms 5904 KB wrong parameter
4 Incorrect 2 ms 4620 KB Output isn't correct
5 Incorrect 14 ms 6008 KB wrong parameter
6 Incorrect 15 ms 6160 KB wrong parameter
7 Incorrect 24 ms 6476 KB wrong parameter
8 Incorrect 17 ms 5904 KB wrong parameter
9 Incorrect 13 ms 5904 KB wrong parameter
10 Incorrect 17 ms 5912 KB wrong parameter
11 Incorrect 14 ms 5904 KB wrong parameter
12 Incorrect 17 ms 5896 KB wrong parameter
13 Incorrect 33 ms 6384 KB wrong parameter
14 Incorrect 13 ms 5904 KB wrong parameter
15 Incorrect 14 ms 5944 KB wrong parameter
16 Incorrect 28 ms 6496 KB wrong parameter
17 Incorrect 25 ms 6388 KB wrong parameter
18 Incorrect 33 ms 6692 KB wrong parameter
19 Incorrect 27 ms 6196 KB wrong parameter
20 Incorrect 43 ms 6888 KB wrong parameter
21 Incorrect 48 ms 6908 KB wrong parameter
22 Incorrect 27 ms 6660 KB wrong parameter
23 Incorrect 43 ms 7080 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 10636 KB wrong parameter
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Incorrect 14 ms 5904 KB wrong parameter
4 Incorrect 2 ms 4620 KB Output isn't correct
5 Incorrect 14 ms 6008 KB wrong parameter
6 Incorrect 15 ms 6160 KB wrong parameter
7 Incorrect 24 ms 6476 KB wrong parameter
8 Incorrect 17 ms 5904 KB wrong parameter
9 Incorrect 13 ms 5904 KB wrong parameter
10 Incorrect 17 ms 5912 KB wrong parameter
11 Incorrect 14 ms 5904 KB wrong parameter
12 Incorrect 17 ms 5896 KB wrong parameter
13 Incorrect 33 ms 6384 KB wrong parameter
14 Incorrect 13 ms 5904 KB wrong parameter
15 Incorrect 14 ms 5944 KB wrong parameter
16 Incorrect 28 ms 6496 KB wrong parameter
17 Incorrect 25 ms 6388 KB wrong parameter
18 Incorrect 33 ms 6692 KB wrong parameter
19 Incorrect 27 ms 6196 KB wrong parameter
20 Incorrect 43 ms 6888 KB wrong parameter
21 Incorrect 48 ms 6908 KB wrong parameter
22 Incorrect 27 ms 6660 KB wrong parameter
23 Incorrect 43 ms 7080 KB wrong parameter