oj.uz

답안 #566650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566650 2022-05-22T14:10:21 Z RealSnake 저장 (Saveit) (IOI10_saveit) C++14
0 / 100
 216 ms 16132 KB 
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "encoder.h"

void encode(int n, int h, int p, int a[], int b[]) {
    vector<int> v[n];
    for(int i = 0; i < p; i++) {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    set<int> s;
    s.insert(0);
    int par[n] = {};
    par[0] = 1;
    vector<int> v2[n];
    while(s.size()) {
        int x = *s.begin();
        s.erase(s.begin());
        for(int i : v[x]) {
            if(!par[i]) {
                v2[x].push_back(i);
                v2[i].push_back(x);
                par[i] = x + 1;
                s.insert(i);
            }
        }
    }
    for(int i = 0; i < n; i++)
        sort(v2[i].begin(), v2[i].end());
    for(int i = 1; i < n; i++) {
        int x = par[i] - 1;
        for(int j = 0; j < 10; j++)
            encode_bit(((x & (1 << j)) > 0));
    }
    int ans[n][h];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < h; j++)
            ans[i][j] = 1e9;
    }
    set<pair<int, pair<int, int>>> ss;
    for(int i = 0; i < h; i++) {
        ss.insert({0, {i, i}});
        ans[i][i] = 0;
    }
    while(ss.size()) {
        pair<int, pair<int, int>> p = *ss.begin();
        ss.erase(ss.begin());
        int x = p.second.first, hub = p.second.second;
        int cost = p.first;
        if(cost > ans[x][hub])
            continue;
        for(int i : v[x]) {
            if(cost + 1 < ans[i][hub]) {
                ans[i][hub] = cost + 1;
                ss.insert({cost + 1, {i, hub}});
            }
        }
    }
    bool vis[n];
    for(int i = 1; i < h; i++) {
        for(int j = 0; j < n; j++)
            vis[j] = 0;
        s.insert(i);
        vis[i] = 1;
        while(s.size()) {
            int x = *s.begin();
            s.erase(s.begin());
            for(int j : v2[x]) {
                if(vis[j])
                    continue;
                vis[j] = 1;
                s.insert(j);
                if(j <= i)
                    continue;
                int dif = ans[j][i] - ans[x][i];
                if(dif == 0)
                    encode_bit(0);
                else {
                    encode_bit(1);
                    if(dif == 1)
                        encode_bit(1);
                    else
                        encode_bit(0);
                }
            }
        }
    }
}
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "decoder.h"

void decode(int n, int h) {
    vector<int> v[n];
    for(int i = 1; i < n; i++) {
        int x = 0;
        for(int j = 0; j < 10; j++) {
            if(decode_bit())
                x += (1 << j);
        }
        v[x].push_back(i);
        v[i].push_back(x);
    }
    for(int i = 0; i < n; i++)
        sort(v[i].begin(), v[i].end());
    int ans[n][n];
    bool vis[n] = {};
    set<int> s;
    s.insert(0);
    ans[0][0] = 0;
    vis[0] = 1;
    while(s.size()) {
        int x = *s.begin();
        s.erase(s.begin());
        hops(0, x, ans[x][0]);
        if(x < h && x != 0)
            hops(x, 0, ans[x][0]);
        for(int i : v[x]) {
            if(vis[i])
                continue;
            vis[i] = 1;
            ans[i][0] = ans[0][i] = ans[x][0] + 1;
            s.insert(i);
        }
    }
    for(int i = 1; i < h; i++) {
        for(int j = 0; j < n; j++)
            vis[j] = 0;
        ans[i][i] = 0;
        s.insert(i);
        vis[i] = 1;
        while(s.size()) {
            int x = *s.begin();
            s.erase(s.begin());
            if(x >= i) {
                hops(i, x, ans[x][i]);
                if(x < h && x != i)
                    hops(x, i, ans[x][i]);
            }
            for(int j : v[x]) {
                if(vis[j])
                    continue;
                vis[j] = 1;
                s.insert(j);
                if(j <= i)
                    continue;
                int dif = decode_bit();
                if(dif) {
                    if(!decode_bit())
                        dif = -1;
                }
                ans[j][i] = ans[i][j] = ans[x][i] + dif;
            }
        }
    }
}

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 216 ms 16132 KB Output isn't correct
2 Correct 2 ms 4476 KB Output is correct - 47 call(s) of encode_bit()
3 Incorrect 36 ms 9896 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 47 call(s) of encode_bit()
5 Incorrect 39 ms 10436 KB Output isn't correct
6 Incorrect 40 ms 11348 KB Output isn't correct
7 Incorrect 59 ms 11876 KB Output isn't correct
8 Incorrect 47 ms 9352 KB Output isn't correct
9 Incorrect 40 ms 9636 KB Output isn't correct
10 Correct 34 ms 9660 KB Output is partially correct - 77065 call(s) of encode_bit()
11 Incorrect 44 ms 9844 KB Output isn't correct
12 Correct 33 ms 9604 KB Output is partially correct - 78660 call(s) of encode_bit()
13 Incorrect 57 ms 11344 KB Output isn't correct
14 Incorrect 38 ms 9592 KB Output isn't correct
15 Incorrect 35 ms 9692 KB Output isn't correct
16 Incorrect 55 ms 10220 KB Output isn't correct
17 Incorrect 53 ms 10120 KB Output isn't correct
18 Incorrect 59 ms 10604 KB Output isn't correct
19 Incorrect 48 ms 10264 KB Output isn't correct
20 Incorrect 70 ms 11608 KB Output isn't correct
21 Incorrect 79 ms 11332 KB Output isn't correct
22 Incorrect 67 ms 11804 KB Output isn't correct
23 Incorrect 83 ms 12500 KB Output isn't correct

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 216 ms 16132 KB Output isn't correct
2 Correct 2 ms 4476 KB Output is correct - 47 call(s) of encode_bit()
3 Incorrect 36 ms 9896 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 47 call(s) of encode_bit()
5 Incorrect 39 ms 10436 KB Output isn't correct
6 Incorrect 40 ms 11348 KB Output isn't correct
7 Incorrect 59 ms 11876 KB Output isn't correct
8 Incorrect 47 ms 9352 KB Output isn't correct
9 Incorrect 40 ms 9636 KB Output isn't correct
10 Correct 34 ms 9660 KB Output is partially correct - 77065 call(s) of encode_bit()
11 Incorrect 44 ms 9844 KB Output isn't correct
12 Correct 33 ms 9604 KB Output is partially correct - 78660 call(s) of encode_bit()
13 Incorrect 57 ms 11344 KB Output isn't correct
14 Incorrect 38 ms 9592 KB Output isn't correct
15 Incorrect 35 ms 9692 KB Output isn't correct
16 Incorrect 55 ms 10220 KB Output isn't correct
17 Incorrect 53 ms 10120 KB Output isn't correct
18 Incorrect 59 ms 10604 KB Output isn't correct
19 Incorrect 48 ms 10264 KB Output isn't correct
20 Incorrect 70 ms 11608 KB Output isn't correct
21 Incorrect 79 ms 11332 KB Output isn't correct
22 Incorrect 67 ms 11804 KB Output isn't correct
23 Incorrect 83 ms 12500 KB Output isn't correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 216 ms 16132 KB Output isn't correct
2 Correct 2 ms 4476 KB Output is correct - 47 call(s) of encode_bit()
3 Incorrect 36 ms 9896 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 47 call(s) of encode_bit()
5 Incorrect 39 ms 10436 KB Output isn't correct
6 Incorrect 40 ms 11348 KB Output isn't correct
7 Incorrect 59 ms 11876 KB Output isn't correct
8 Incorrect 47 ms 9352 KB Output isn't correct
9 Incorrect 40 ms 9636 KB Output isn't correct
10 Correct 34 ms 9660 KB Output is partially correct - 77065 call(s) of encode_bit()
11 Incorrect 44 ms 9844 KB Output isn't correct
12 Correct 33 ms 9604 KB Output is partially correct - 78660 call(s) of encode_bit()
13 Incorrect 57 ms 11344 KB Output isn't correct
14 Incorrect 38 ms 9592 KB Output isn't correct
15 Incorrect 35 ms 9692 KB Output isn't correct
16 Incorrect 55 ms 10220 KB Output isn't correct
17 Incorrect 53 ms 10120 KB Output isn't correct
18 Incorrect 59 ms 10604 KB Output isn't correct
19 Incorrect 48 ms 10264 KB Output isn't correct
20 Incorrect 70 ms 11608 KB Output isn't correct
21 Incorrect 79 ms 11332 KB Output isn't correct
22 Incorrect 67 ms 11804 KB Output isn't correct
23 Incorrect 83 ms 12500 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 216 ms 16132 KB Output isn't correct
2 Correct 2 ms 4476 KB Output is correct - 47 call(s) of encode_bit()
3 Incorrect 36 ms 9896 KB Output isn't correct
4 Correct 2 ms 4604 KB Output is correct - 47 call(s) of encode_bit()
5 Incorrect 39 ms 10436 KB Output isn't correct
6 Incorrect 40 ms 11348 KB Output isn't correct
7 Incorrect 59 ms 11876 KB Output isn't correct
8 Incorrect 47 ms 9352 KB Output isn't correct
9 Incorrect 40 ms 9636 KB Output isn't correct
10 Correct 34 ms 9660 KB Output is partially correct - 77065 call(s) of encode_bit()
11 Incorrect 44 ms 9844 KB Output isn't correct
12 Correct 33 ms 9604 KB Output is partially correct - 78660 call(s) of encode_bit()
13 Incorrect 57 ms 11344 KB Output isn't correct
14 Incorrect 38 ms 9592 KB Output isn't correct
15 Incorrect 35 ms 9692 KB Output isn't correct
16 Incorrect 55 ms 10220 KB Output isn't correct
17 Incorrect 53 ms 10120 KB Output isn't correct
18 Incorrect 59 ms 10604 KB Output isn't correct
19 Incorrect 48 ms 10264 KB Output isn't correct
20 Incorrect 70 ms 11608 KB Output isn't correct
21 Incorrect 79 ms 11332 KB Output isn't correct
22 Incorrect 67 ms 11804 KB Output isn't correct
23 Incorrect 83 ms 12500 KB Output isn't correct