oj.uz

답안 #1090769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090769 2024-09-18T17:53:30 Z Tymond 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 10000 ms 262144 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(1);
                }else if(dist[j][i] == dist[j][parent[i]] - 1){
                    encode_bit(0);
                    encode_bit(0);
                }else{
                    encode_bit(1);
                    encode_bit(0);
                }
                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 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[parent[i]].pb(i);
    }

    for(int j = 0; j < h; j++){
        vi vec(n, 0);
        int i;
        for(i = 0; i < n; i++){
            if(i + 2 >= n){
                int x = decode_bit();
                int y = decode_bit();
                vec[i] = 2 * x + y - 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(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(dist[j][u] == -1){
                    dist[j][u] = dist[j][v] + vec[u];
                    q.push(u);
                } 
            }

            if(dist[j][parent[v]] == -1){
                q.push(parent[v]);
                dist[j][parent[v]] = dist[j][v] - vec[v];
            }
        }
    }

    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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 757 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4616 KB Output isn't correct
3 Execution timed out 10004 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4624 KB Output isn't correct
5 Runtime error 489 ms 262144 KB Execution killed with signal 9
6 Runtime error 340 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10004 ms 5904 KB Time limit exceeded
9 Execution timed out 10104 ms 5904 KB Time limit exceeded
10 Runtime error 1049 ms 262144 KB Execution killed with signal 9
11 Runtime error 661 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10098 ms 5900 KB Time limit exceeded
13 Runtime error 817 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10096 ms 5904 KB Time limit exceeded
15 Execution timed out 10097 ms 5904 KB Time limit exceeded
16 Execution timed out 10091 ms 6320 KB Time limit exceeded
17 Execution timed out 10092 ms 6088 KB Time limit exceeded
18 Runtime error 574 ms 262144 KB Execution killed with signal 9
19 Runtime error 311 ms 262144 KB Execution killed with signal 9
20 Runtime error 323 ms 262144 KB Execution killed with signal 9
21 Runtime error 629 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10054 ms 6312 KB Time limit exceeded
23 Execution timed out 10091 ms 6820 KB Time limit exceeded

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 757 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4616 KB Output isn't correct
3 Execution timed out 10004 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4624 KB Output isn't correct
5 Runtime error 489 ms 262144 KB Execution killed with signal 9
6 Runtime error 340 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10004 ms 5904 KB Time limit exceeded
9 Execution timed out 10104 ms 5904 KB Time limit exceeded
10 Runtime error 1049 ms 262144 KB Execution killed with signal 9
11 Runtime error 661 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10098 ms 5900 KB Time limit exceeded
13 Runtime error 817 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10096 ms 5904 KB Time limit exceeded
15 Execution timed out 10097 ms 5904 KB Time limit exceeded
16 Execution timed out 10091 ms 6320 KB Time limit exceeded
17 Execution timed out 10092 ms 6088 KB Time limit exceeded
18 Runtime error 574 ms 262144 KB Execution killed with signal 9
19 Runtime error 311 ms 262144 KB Execution killed with signal 9
20 Runtime error 323 ms 262144 KB Execution killed with signal 9
21 Runtime error 629 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10054 ms 6312 KB Time limit exceeded
23 Execution timed out 10091 ms 6820 KB Time limit exceeded

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 757 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4616 KB Output isn't correct
3 Execution timed out 10004 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4624 KB Output isn't correct
5 Runtime error 489 ms 262144 KB Execution killed with signal 9
6 Runtime error 340 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10004 ms 5904 KB Time limit exceeded
9 Execution timed out 10104 ms 5904 KB Time limit exceeded
10 Runtime error 1049 ms 262144 KB Execution killed with signal 9
11 Runtime error 661 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10098 ms 5900 KB Time limit exceeded
13 Runtime error 817 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10096 ms 5904 KB Time limit exceeded
15 Execution timed out 10097 ms 5904 KB Time limit exceeded
16 Execution timed out 10091 ms 6320 KB Time limit exceeded
17 Execution timed out 10092 ms 6088 KB Time limit exceeded
18 Runtime error 574 ms 262144 KB Execution killed with signal 9
19 Runtime error 311 ms 262144 KB Execution killed with signal 9
20 Runtime error 323 ms 262144 KB Execution killed with signal 9
21 Runtime error 629 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10054 ms 6312 KB Time limit exceeded
23 Execution timed out 10091 ms 6820 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 757 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4616 KB Output isn't correct
3 Execution timed out 10004 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4624 KB Output isn't correct
5 Runtime error 489 ms 262144 KB Execution killed with signal 9
6 Runtime error 340 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10004 ms 5904 KB Time limit exceeded
9 Execution timed out 10104 ms 5904 KB Time limit exceeded
10 Runtime error 1049 ms 262144 KB Execution killed with signal 9
11 Runtime error 661 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10098 ms 5900 KB Time limit exceeded
13 Runtime error 817 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10096 ms 5904 KB Time limit exceeded
15 Execution timed out 10097 ms 5904 KB Time limit exceeded
16 Execution timed out 10091 ms 6320 KB Time limit exceeded
17 Execution timed out 10092 ms 6088 KB Time limit exceeded
18 Runtime error 574 ms 262144 KB Execution killed with signal 9
19 Runtime error 311 ms 262144 KB Execution killed with signal 9
20 Runtime error 323 ms 262144 KB Execution killed with signal 9
21 Runtime error 629 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10054 ms 6312 KB Time limit exceeded
23 Execution timed out 10091 ms 6820 KB Time limit exceeded