oj.uz

답안 #1090767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090767 2024-09-18T17:48:07 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[i].pb(parent[i]);
        g[parent[i]].pb(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();
                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(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(dist[j][u] == -1){
                    if(u == parent[v]){
                        dist[j][u] = dist[j][v] - vec[v];
                    }else{
                        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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 775 ms 262144 KB Execution killed with signal 9
2 Incorrect 1 ms 4872 KB Output isn't correct
3 Execution timed out 10102 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4620 KB Output isn't correct
5 Runtime error 538 ms 262144 KB Execution killed with signal 9
6 Runtime error 335 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10096 ms 5908 KB Time limit exceeded
9 Execution timed out 10102 ms 5896 KB Time limit exceeded
10 Runtime error 1029 ms 262144 KB Execution killed with signal 9
11 Runtime error 744 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10103 ms 5904 KB Time limit exceeded
13 Runtime error 862 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10097 ms 5900 KB Time limit exceeded
15 Execution timed out 10001 ms 5900 KB Time limit exceeded
16 Execution timed out 10005 ms 6404 KB Time limit exceeded
17 Execution timed out 10046 ms 6316 KB Time limit exceeded
18 Runtime error 551 ms 262144 KB Execution killed with signal 9
19 Runtime error 323 ms 262144 KB Execution killed with signal 9
20 Runtime error 303 ms 262144 KB Execution killed with signal 9
21 Runtime error 617 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10014 ms 6552 KB Time limit exceeded
23 Execution timed out 10010 ms 7076 KB Time limit exceeded

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 775 ms 262144 KB Execution killed with signal 9
2 Incorrect 1 ms 4872 KB Output isn't correct
3 Execution timed out 10102 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4620 KB Output isn't correct
5 Runtime error 538 ms 262144 KB Execution killed with signal 9
6 Runtime error 335 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10096 ms 5908 KB Time limit exceeded
9 Execution timed out 10102 ms 5896 KB Time limit exceeded
10 Runtime error 1029 ms 262144 KB Execution killed with signal 9
11 Runtime error 744 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10103 ms 5904 KB Time limit exceeded
13 Runtime error 862 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10097 ms 5900 KB Time limit exceeded
15 Execution timed out 10001 ms 5900 KB Time limit exceeded
16 Execution timed out 10005 ms 6404 KB Time limit exceeded
17 Execution timed out 10046 ms 6316 KB Time limit exceeded
18 Runtime error 551 ms 262144 KB Execution killed with signal 9
19 Runtime error 323 ms 262144 KB Execution killed with signal 9
20 Runtime error 303 ms 262144 KB Execution killed with signal 9
21 Runtime error 617 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10014 ms 6552 KB Time limit exceeded
23 Execution timed out 10010 ms 7076 KB Time limit exceeded

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 775 ms 262144 KB Execution killed with signal 9
2 Incorrect 1 ms 4872 KB Output isn't correct
3 Execution timed out 10102 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4620 KB Output isn't correct
5 Runtime error 538 ms 262144 KB Execution killed with signal 9
6 Runtime error 335 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10096 ms 5908 KB Time limit exceeded
9 Execution timed out 10102 ms 5896 KB Time limit exceeded
10 Runtime error 1029 ms 262144 KB Execution killed with signal 9
11 Runtime error 744 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10103 ms 5904 KB Time limit exceeded
13 Runtime error 862 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10097 ms 5900 KB Time limit exceeded
15 Execution timed out 10001 ms 5900 KB Time limit exceeded
16 Execution timed out 10005 ms 6404 KB Time limit exceeded
17 Execution timed out 10046 ms 6316 KB Time limit exceeded
18 Runtime error 551 ms 262144 KB Execution killed with signal 9
19 Runtime error 323 ms 262144 KB Execution killed with signal 9
20 Runtime error 303 ms 262144 KB Execution killed with signal 9
21 Runtime error 617 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10014 ms 6552 KB Time limit exceeded
23 Execution timed out 10010 ms 7076 KB Time limit exceeded

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 775 ms 262144 KB Execution killed with signal 9
2 Incorrect 1 ms 4872 KB Output isn't correct
3 Execution timed out 10102 ms 5648 KB Time limit exceeded
4 Incorrect 1 ms 4620 KB Output isn't correct
5 Runtime error 538 ms 262144 KB Execution killed with signal 9
6 Runtime error 335 ms 262144 KB Execution killed with signal 9
7 Runtime error 293 ms 262144 KB Execution killed with signal 9
8 Execution timed out 10096 ms 5908 KB Time limit exceeded
9 Execution timed out 10102 ms 5896 KB Time limit exceeded
10 Runtime error 1029 ms 262144 KB Execution killed with signal 9
11 Runtime error 744 ms 262144 KB Execution killed with signal 9
12 Execution timed out 10103 ms 5904 KB Time limit exceeded
13 Runtime error 862 ms 262144 KB Execution killed with signal 9
14 Execution timed out 10097 ms 5900 KB Time limit exceeded
15 Execution timed out 10001 ms 5900 KB Time limit exceeded
16 Execution timed out 10005 ms 6404 KB Time limit exceeded
17 Execution timed out 10046 ms 6316 KB Time limit exceeded
18 Runtime error 551 ms 262144 KB Execution killed with signal 9
19 Runtime error 323 ms 262144 KB Execution killed with signal 9
20 Runtime error 303 ms 262144 KB Execution killed with signal 9
21 Runtime error 617 ms 262144 KB Execution killed with signal 9
22 Execution timed out 10014 ms 6552 KB Time limit exceeded
23 Execution timed out 10010 ms 7076 KB Time limit exceeded