oj.uz

답안 #1090804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090804 2024-09-18T18:52:45 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++){
        vi kol;
        if(n % 3 != 0){
            for(int i = 0; i < n; i++){
                if(i != j){
                    kol.pb(i);
                }
            }
        }else{
            for(int i = 0; i < n; i++){
                kol.pb(i);
            }
        }
        for(int f = 0; f < sz(kol); f++){
            if(f + 2 >= sz(kol)){
                if(dist[j][kol[f]] == dist[j][parent[kol[f]]]){
                    encode_bit(0);
                    encode_bit(1);
                }else if(dist[j][kol[f]] == dist[j][parent[kol[f]]] - 1){
                    encode_bit(0);
                    encode_bit(0);
                }else{
                    encode_bit(1);
                    encode_bit(0);
                }
                continue;
            }
 
            int r = 0;
            for(int y = f; y <= f + 2; y++){
                r = r * 3 + (dist[j][kol[y]] - dist[j][parent[kol[y]]] + 1);
            }
 
            for(int y = 0; y < 5; y++){
                if((1 << y) & r){
                    encode_bit(1);
                }else{
                    encode_bit(0);
                }
            }
            f += 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;
        vi kol;
        if(n % 3 != 0){
            for(int i = 0; i < n; i++){
                if(i != j){
                    kol.pb(i);
                }
            }
        }else{
            for(int i = 0; i < n; i++){
                kol.pb(i);
            }
        }
        for(int f = 0; f < sz(kol); f++){
            if(f + 2 >= sz(kol)){
                int x = decode_bit();
                int y = decode_bit();
                vec[kol[f]] = 2 * x + y - 1;
                continue;
            }
 
            int r = 0;
            for(int y = 0; y < 5; y++){
                r += (decode_bit() * (1 << y));
            }
            for(int y = f + 2; y >= f; y--){
                vec[kol[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 466 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4624 KB too many decode_bit() calls
3 Runtime error 405 ms 262144 KB Execution killed with signal 9
4 Incorrect 1 ms 4620 KB too many decode_bit() calls
5 Runtime error 348 ms 262144 KB Execution killed with signal 9
6 Runtime error 341 ms 262144 KB Execution killed with signal 9
7 Runtime error 279 ms 262144 KB Execution killed with signal 9
8 Runtime error 632 ms 262144 KB Execution killed with signal 9
9 Execution timed out 10003 ms 5904 KB Time limit exceeded
10 Execution timed out 10091 ms 5900 KB Time limit exceeded
11 Execution timed out 10099 ms 5732 KB Time limit exceeded
12 Runtime error 912 ms 262144 KB Execution killed with signal 9
13 Runtime error 392 ms 262144 KB Execution killed with signal 9
14 Runtime error 695 ms 262144 KB Execution killed with signal 9
15 Execution timed out 10101 ms 5904 KB Time limit exceeded
16 Runtime error 497 ms 262144 KB Execution killed with signal 9
17 Runtime error 471 ms 262144 KB Execution killed with signal 9
18 Runtime error 399 ms 262144 KB Execution killed with signal 9
19 Runtime error 519 ms 262144 KB Execution killed with signal 9
20 Runtime error 763 ms 262144 KB Execution killed with signal 9
21 Runtime error 355 ms 262144 KB Execution killed with signal 9
22 Runtime error 875 ms 262144 KB Execution killed with signal 9
23 Runtime error 274 ms 262144 KB Execution killed with signal 9

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 466 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4624 KB too many decode_bit() calls
3 Runtime error 405 ms 262144 KB Execution killed with signal 9
4 Incorrect 1 ms 4620 KB too many decode_bit() calls
5 Runtime error 348 ms 262144 KB Execution killed with signal 9
6 Runtime error 341 ms 262144 KB Execution killed with signal 9
7 Runtime error 279 ms 262144 KB Execution killed with signal 9
8 Runtime error 632 ms 262144 KB Execution killed with signal 9
9 Execution timed out 10003 ms 5904 KB Time limit exceeded
10 Execution timed out 10091 ms 5900 KB Time limit exceeded
11 Execution timed out 10099 ms 5732 KB Time limit exceeded
12 Runtime error 912 ms 262144 KB Execution killed with signal 9
13 Runtime error 392 ms 262144 KB Execution killed with signal 9
14 Runtime error 695 ms 262144 KB Execution killed with signal 9
15 Execution timed out 10101 ms 5904 KB Time limit exceeded
16 Runtime error 497 ms 262144 KB Execution killed with signal 9
17 Runtime error 471 ms 262144 KB Execution killed with signal 9
18 Runtime error 399 ms 262144 KB Execution killed with signal 9
19 Runtime error 519 ms 262144 KB Execution killed with signal 9
20 Runtime error 763 ms 262144 KB Execution killed with signal 9
21 Runtime error 355 ms 262144 KB Execution killed with signal 9
22 Runtime error 875 ms 262144 KB Execution killed with signal 9
23 Runtime error 274 ms 262144 KB Execution killed with signal 9

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 466 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4624 KB too many decode_bit() calls
3 Runtime error 405 ms 262144 KB Execution killed with signal 9
4 Incorrect 1 ms 4620 KB too many decode_bit() calls
5 Runtime error 348 ms 262144 KB Execution killed with signal 9
6 Runtime error 341 ms 262144 KB Execution killed with signal 9
7 Runtime error 279 ms 262144 KB Execution killed with signal 9
8 Runtime error 632 ms 262144 KB Execution killed with signal 9
9 Execution timed out 10003 ms 5904 KB Time limit exceeded
10 Execution timed out 10091 ms 5900 KB Time limit exceeded
11 Execution timed out 10099 ms 5732 KB Time limit exceeded
12 Runtime error 912 ms 262144 KB Execution killed with signal 9
13 Runtime error 392 ms 262144 KB Execution killed with signal 9
14 Runtime error 695 ms 262144 KB Execution killed with signal 9
15 Execution timed out 10101 ms 5904 KB Time limit exceeded
16 Runtime error 497 ms 262144 KB Execution killed with signal 9
17 Runtime error 471 ms 262144 KB Execution killed with signal 9
18 Runtime error 399 ms 262144 KB Execution killed with signal 9
19 Runtime error 519 ms 262144 KB Execution killed with signal 9
20 Runtime error 763 ms 262144 KB Execution killed with signal 9
21 Runtime error 355 ms 262144 KB Execution killed with signal 9
22 Runtime error 875 ms 262144 KB Execution killed with signal 9
23 Runtime error 274 ms 262144 KB Execution killed with signal 9

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 466 ms 262144 KB Execution killed with signal 9
2 Incorrect 2 ms 4624 KB too many decode_bit() calls
3 Runtime error 405 ms 262144 KB Execution killed with signal 9
4 Incorrect 1 ms 4620 KB too many decode_bit() calls
5 Runtime error 348 ms 262144 KB Execution killed with signal 9
6 Runtime error 341 ms 262144 KB Execution killed with signal 9
7 Runtime error 279 ms 262144 KB Execution killed with signal 9
8 Runtime error 632 ms 262144 KB Execution killed with signal 9
9 Execution timed out 10003 ms 5904 KB Time limit exceeded
10 Execution timed out 10091 ms 5900 KB Time limit exceeded
11 Execution timed out 10099 ms 5732 KB Time limit exceeded
12 Runtime error 912 ms 262144 KB Execution killed with signal 9
13 Runtime error 392 ms 262144 KB Execution killed with signal 9
14 Runtime error 695 ms 262144 KB Execution killed with signal 9
15 Execution timed out 10101 ms 5904 KB Time limit exceeded
16 Runtime error 497 ms 262144 KB Execution killed with signal 9
17 Runtime error 471 ms 262144 KB Execution killed with signal 9
18 Runtime error 399 ms 262144 KB Execution killed with signal 9
19 Runtime error 519 ms 262144 KB Execution killed with signal 9
20 Runtime error 763 ms 262144 KB Execution killed with signal 9
21 Runtime error 355 ms 262144 KB Execution killed with signal 9
22 Runtime error 875 ms 262144 KB Execution killed with signal 9
23 Runtime error 274 ms 262144 KB Execution killed with signal 9