oj.uz

답안 #1090806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090806 2024-09-18T18:57:05 Z Tymond 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 144 ms 10672 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);
        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;
            }
 
            f += 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){
                    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 Incorrect 144 ms 10672 KB Output isn't correct
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Correct 17 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
4 Incorrect 3 ms 4624 KB Output isn't correct
5 Correct 14 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
6 Incorrect 18 ms 6164 KB Output isn't correct
7 Incorrect 30 ms 6320 KB Output isn't correct
8 Incorrect 13 ms 5900 KB Output isn't correct
9 Incorrect 14 ms 5916 KB Output isn't correct
10 Incorrect 15 ms 5896 KB Output isn't correct
11 Incorrect 17 ms 5828 KB Output isn't correct
12 Incorrect 15 ms 5904 KB Output isn't correct
13 Incorrect 34 ms 6580 KB Output isn't correct
14 Incorrect 18 ms 6060 KB Output isn't correct
15 Incorrect 15 ms 5908 KB Output isn't correct
16 Incorrect 31 ms 6392 KB Output isn't correct
17 Incorrect 33 ms 6556 KB Output isn't correct
18 Incorrect 32 ms 6656 KB Output isn't correct
19 Incorrect 22 ms 6168 KB Output isn't correct
20 Incorrect 39 ms 6900 KB Output isn't correct
21 Incorrect 46 ms 6900 KB Output isn't correct
22 Incorrect 32 ms 6708 KB Output isn't correct
23 Incorrect 48 ms 7076 KB Output isn't correct

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 10672 KB Output isn't correct
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Correct 17 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
4 Incorrect 3 ms 4624 KB Output isn't correct
5 Correct 14 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
6 Incorrect 18 ms 6164 KB Output isn't correct
7 Incorrect 30 ms 6320 KB Output isn't correct
8 Incorrect 13 ms 5900 KB Output isn't correct
9 Incorrect 14 ms 5916 KB Output isn't correct
10 Incorrect 15 ms 5896 KB Output isn't correct
11 Incorrect 17 ms 5828 KB Output isn't correct
12 Incorrect 15 ms 5904 KB Output isn't correct
13 Incorrect 34 ms 6580 KB Output isn't correct
14 Incorrect 18 ms 6060 KB Output isn't correct
15 Incorrect 15 ms 5908 KB Output isn't correct
16 Incorrect 31 ms 6392 KB Output isn't correct
17 Incorrect 33 ms 6556 KB Output isn't correct
18 Incorrect 32 ms 6656 KB Output isn't correct
19 Incorrect 22 ms 6168 KB Output isn't correct
20 Incorrect 39 ms 6900 KB Output isn't correct
21 Incorrect 46 ms 6900 KB Output isn't correct
22 Incorrect 32 ms 6708 KB Output isn't correct
23 Incorrect 48 ms 7076 KB Output isn't correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 10672 KB Output isn't correct
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Correct 17 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
4 Incorrect 3 ms 4624 KB Output isn't correct
5 Correct 14 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
6 Incorrect 18 ms 6164 KB Output isn't correct
7 Incorrect 30 ms 6320 KB Output isn't correct
8 Incorrect 13 ms 5900 KB Output isn't correct
9 Incorrect 14 ms 5916 KB Output isn't correct
10 Incorrect 15 ms 5896 KB Output isn't correct
11 Incorrect 17 ms 5828 KB Output isn't correct
12 Incorrect 15 ms 5904 KB Output isn't correct
13 Incorrect 34 ms 6580 KB Output isn't correct
14 Incorrect 18 ms 6060 KB Output isn't correct
15 Incorrect 15 ms 5908 KB Output isn't correct
16 Incorrect 31 ms 6392 KB Output isn't correct
17 Incorrect 33 ms 6556 KB Output isn't correct
18 Incorrect 32 ms 6656 KB Output isn't correct
19 Incorrect 22 ms 6168 KB Output isn't correct
20 Incorrect 39 ms 6900 KB Output isn't correct
21 Incorrect 46 ms 6900 KB Output isn't correct
22 Incorrect 32 ms 6708 KB Output isn't correct
23 Incorrect 48 ms 7076 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 10672 KB Output isn't correct
2 Incorrect 3 ms 4620 KB Output isn't correct
3 Correct 17 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
4 Incorrect 3 ms 4624 KB Output isn't correct
5 Correct 14 ms 5904 KB Output is correct - 62990 call(s) of encode_bit()
6 Incorrect 18 ms 6164 KB Output isn't correct
7 Incorrect 30 ms 6320 KB Output isn't correct
8 Incorrect 13 ms 5900 KB Output isn't correct
9 Incorrect 14 ms 5916 KB Output isn't correct
10 Incorrect 15 ms 5896 KB Output isn't correct
11 Incorrect 17 ms 5828 KB Output isn't correct
12 Incorrect 15 ms 5904 KB Output isn't correct
13 Incorrect 34 ms 6580 KB Output isn't correct
14 Incorrect 18 ms 6060 KB Output isn't correct
15 Incorrect 15 ms 5908 KB Output isn't correct
16 Incorrect 31 ms 6392 KB Output isn't correct
17 Incorrect 33 ms 6556 KB Output isn't correct
18 Incorrect 32 ms 6656 KB Output isn't correct
19 Incorrect 22 ms 6168 KB Output isn't correct
20 Incorrect 39 ms 6900 KB Output isn't correct
21 Incorrect 46 ms 6900 KB Output isn't correct
22 Incorrect 32 ms 6708 KB Output isn't correct
23 Incorrect 48 ms 7076 KB Output isn't correct