oj.uz

Submission #703449

# Submission time Handle Problem Language Result Execution time Memory
703449 2023-02-27T12:24:26 Z KoD 한자 끝말잇기 (JOI14_kanji) C++17
100 / 100
 260 ms 17540 KB 
#include "Annalib.h"

#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
    using namespace std;
    using ll = long long;
    using ull = unsigned long long;
    constexpr ll inf = numeric_limits<ll>::max() / 3;

    vector use(M, true);
    for (int i = 0; i < K; ++i) {
        use[U[i]] = false;
    }
    vector d(N, vector(N, inf));
    for (int i = 0; i < N; ++i) {
        d[i][i] = 0;
    }
    for (int i = 0; i < M; ++i) {
        if (use[i]) {
            d[A[i]][B[i]] = C[i];
        }
    }
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    map<int, vector<int>> g = {};
    {
        vector<int> v(Q);
        iota(begin(v), end(v), 0);
        g.emplace(-1, move(v));
    }
    ull send = 0, coeff = 1;
    for (int k = 0; k < K; ++k) {
        map<int, vector<int>> g2 = {};
        for (const auto& [j, v] : g) {
            if (j == -1) {
                for (const int i : v) {
                    if (d[S[i]][T[i]] - d[S[i]][A[U[k]]] - d[B[U[k]]][T[i]] <= C[U[k]]) {
                        send += coeff;
                        g2[j].push_back(i);
                    } else {
                        g2[k].push_back(i);
                    }
                }
            } else {
                for (const int i : v) {
                    if (d[B[U[j]]][T[i]] - d[B[U[k]]][T[i]] <= C[U[k]] - C[U[j]]) {
                        send += coeff;
                        g2[j].push_back(i);
                    } else {
                        g2[k].push_back(i);
                    }
                }
            }
            coeff *= v.size() + 1;
        }
        g = move(g2);
    }

    for (int i = 0; i < 64; ++i) {
        Tap(send >> i & 1);
    }
}

#include "Brunolib.h"

#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
    using namespace std;
    using ll = long long;
    using ull = unsigned long long;
    constexpr ll inf = numeric_limits<ll>::max() / 3;

    vector use(M, true);
    for (int i = 0; i < K; ++i) {
        use[U[i]] = false;
    }
    vector d(N, vector(N, inf));
    vector adj(N, vector(N, -1));
    for (int i = 0; i < N; ++i) {
        d[i][i] = 0;
    }
    for (int i = 0; i < M; ++i) {
        if (use[i]) {
            d[A[i]][B[i]] = C[i];
            adj[A[i]][B[i]] = i;
        }
    }
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    vector rev(N, vector(N, -1));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                if (const int e = adj[k][j]; e != -1 and d[i][j] == d[i][A[e]] + C[e] + d[B[e]][j]) {
                    rev[i][j] = e;
                }
            }
        }
    }

    ull receive = 0;
    for (int i = 0; i < L; ++i) {
        receive |= (ull)X[i] << i;
    }
    map<int, vector<int>> g = {};
    {
        vector<int> v(Q);
        iota(begin(v), end(v), 0);
        g.emplace(-1, move(v));
    }
    for (int k = 0; k < K; ++k) {
        map<int, vector<int>> g2 = {};
        for (const auto& [j, v] : g) {
            vector<pair<ll, int>> v2;
            if (j == -1) {
                for (const int i : v) {
                    v2.emplace_back(d[S[i]][T[i]] - d[S[i]][A[U[k]]] - d[B[U[k]]][T[i]], i);
                }
            } else {
                for (const int i : v) {
                    v2.emplace_back(d[B[U[j]]][T[i]] - d[B[U[k]]][T[i]], i);
                }
            }
            sort(begin(v2), end(v2));
            const int n = (int)v.size();
            const int m = receive % (n + 1);
            receive /= n + 1;
            for (int i = 0; i < m; ++i) {
                g2[j].push_back(v2[i].second);
            }
            for (int i = m; i < n; ++i) {
                g2[k].push_back(v2[i].second);
            }
        }
        g = move(g2);
    }
    
    vector<int> type(Q);
    for (const auto& [j, v] : g) {
        for (const int i : v) {
            type[i] = j;
        }
    }
    for (int i = 0; i < Q; ++i) {
        vector<int> ans;
        const auto add = [&](const int u, int v) {
            while (v != u) {
                const int e = rev[u][v];
                ans.push_back(e);
                v = A[e];
            }
        };
        if (const int j = type[i]; j == -1) {
            add(S[i], T[i]);
        } else {
            add(B[U[j]], T[i]);
            ans.push_back(U[j]);
            add(S[i], A[U[j]]);
        }
        reverse(begin(ans), end(ans));
        for (const int j : ans) {
            Answer(j);
        }
        Answer(-1);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 6416 KB Output is correct - L = 64
2 Correct 82 ms 6264 KB Output is correct - L = 64
3 Correct 77 ms 6364 KB Output is correct - L = 64
4 Correct 76 ms 6340 KB Output is correct - L = 64
5 Correct 89 ms 6252 KB Output is correct - L = 64
6 Correct 76 ms 6280 KB Output is correct - L = 64
7 Correct 78 ms 6360 KB Output is correct - L = 64
8 Correct 95 ms 6400 KB Output is correct - L = 64
9 Correct 86 ms 6616 KB Output is correct - L = 64
10 Correct 102 ms 6724 KB Output is correct - L = 64
11 Correct 93 ms 6288 KB Output is correct - L = 64
12 Correct 255 ms 17232 KB Output is correct - L = 64
13 Correct 81 ms 6496 KB Output is correct - L = 64
14 Correct 78 ms 6224 KB Output is correct - L = 64

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 6696 KB Output is correct - L = 64
2 Correct 79 ms 6492 KB Output is correct - L = 64
3 Correct 78 ms 6624 KB Output is correct - L = 64
4 Correct 83 ms 6608 KB Output is correct - L = 64
5 Correct 83 ms 6412 KB Output is correct - L = 64
6 Correct 77 ms 6824 KB Output is correct - L = 64
7 Correct 82 ms 6740 KB Output is correct - L = 64
8 Correct 79 ms 6764 KB Output is correct - L = 64
9 Correct 93 ms 6720 KB Output is correct - L = 64
10 Correct 89 ms 6800 KB Output is correct - L = 64
11 Correct 94 ms 6724 KB Output is correct - L = 64
12 Correct 79 ms 6688 KB Output is correct - L = 64
13 Correct 237 ms 17400 KB Output is correct - L = 64
14 Correct 90 ms 6628 KB Output is correct - L = 64
15 Correct 78 ms 6520 KB Output is correct - L = 64
16 Correct 90 ms 6852 KB Output is correct - L = 64
17 Correct 100 ms 6892 KB Output is correct - L = 64
18 Correct 117 ms 7220 KB Output is correct - L = 64
19 Correct 79 ms 6292 KB Output is correct - L = 64
20 Correct 124 ms 7600 KB Output is correct - L = 64
21 Correct 142 ms 7568 KB Output is correct - L = 64
22 Correct 80 ms 6752 KB Output is correct - L = 64
23 Correct 80 ms 6780 KB Output is correct - L = 64
24 Correct 97 ms 6708 KB Output is correct - L = 64

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6704 KB Output is correct - L = 64
2 Correct 84 ms 6596 KB Output is correct - L = 64
3 Correct 76 ms 6520 KB Output is correct - L = 64
4 Correct 91 ms 6604 KB Output is correct - L = 64
5 Correct 103 ms 6284 KB Output is correct - L = 64
6 Correct 76 ms 6748 KB Output is correct - L = 64
7 Correct 80 ms 6736 KB Output is correct - L = 64
8 Correct 84 ms 6644 KB Output is correct - L = 64
9 Correct 78 ms 6808 KB Output is correct - L = 64
10 Correct 81 ms 6812 KB Output is correct - L = 64
11 Correct 80 ms 6824 KB Output is correct - L = 64
12 Correct 79 ms 6764 KB Output is correct - L = 64
13 Correct 257 ms 17540 KB Output is correct - L = 64
14 Correct 83 ms 6648 KB Output is correct - L = 64
15 Correct 99 ms 6756 KB Output is correct - L = 64
16 Correct 93 ms 6864 KB Output is correct - L = 64
17 Correct 93 ms 6908 KB Output is correct - L = 64
18 Correct 123 ms 7180 KB Output is correct - L = 64
19 Correct 77 ms 6372 KB Output is correct - L = 64
20 Correct 126 ms 7820 KB Output is correct - L = 64
21 Correct 126 ms 7576 KB Output is correct - L = 64
22 Correct 78 ms 6752 KB Output is correct - L = 64
23 Correct 90 ms 6884 KB Output is correct - L = 64
24 Correct 84 ms 6772 KB Output is correct - L = 64

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6628 KB Output is correct - L = 64
2 Correct 75 ms 6468 KB Output is correct - L = 64
3 Correct 81 ms 6696 KB Output is correct - L = 64
4 Correct 74 ms 6644 KB Output is correct - L = 64
5 Correct 98 ms 6496 KB Output is correct - L = 64
6 Correct 92 ms 6636 KB Output is correct - L = 64
7 Correct 77 ms 6676 KB Output is correct - L = 64
8 Correct 82 ms 6724 KB Output is correct - L = 64
9 Correct 81 ms 6736 KB Output is correct - L = 64
10 Correct 81 ms 6748 KB Output is correct - L = 64
11 Correct 94 ms 6832 KB Output is correct - L = 64
12 Correct 77 ms 6724 KB Output is correct - L = 64
13 Correct 260 ms 17284 KB Output is correct - L = 64
14 Correct 81 ms 6816 KB Output is correct - L = 64
15 Correct 77 ms 6668 KB Output is correct - L = 64
16 Correct 86 ms 6836 KB Output is correct - L = 64
17 Correct 102 ms 6904 KB Output is correct - L = 64
18 Correct 115 ms 7352 KB Output is correct - L = 64
19 Correct 78 ms 6500 KB Output is correct - L = 64
20 Correct 140 ms 7636 KB Output is correct - L = 64
21 Correct 120 ms 7560 KB Output is correct - L = 64
22 Correct 78 ms 6692 KB Output is correct - L = 64
23 Correct 87 ms 6820 KB Output is correct - L = 64
24 Correct 79 ms 6848 KB Output is correct - L = 64

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6712 KB Output is correct - L = 64
2 Correct 83 ms 6476 KB Output is correct - L = 64
3 Correct 78 ms 6564 KB Output is correct - L = 64
4 Correct 76 ms 6620 KB Output is correct - L = 64
5 Correct 83 ms 6472 KB Output is correct - L = 64
6 Correct 78 ms 6724 KB Output is correct - L = 64
7 Correct 109 ms 6608 KB Output is correct - L = 64
8 Correct 79 ms 6756 KB Output is correct - L = 64
9 Correct 79 ms 6760 KB Output is correct - L = 64
10 Correct 82 ms 6704 KB Output is correct - L = 64
11 Correct 92 ms 6748 KB Output is correct - L = 64
12 Correct 78 ms 6736 KB Output is correct - L = 64
13 Correct 238 ms 15792 KB Output is correct - L = 64
14 Correct 93 ms 6688 KB Output is correct - L = 64
15 Correct 94 ms 6636 KB Output is correct - L = 64
16 Correct 84 ms 6796 KB Output is correct - L = 64
17 Correct 98 ms 6916 KB Output is correct - L = 64
18 Correct 123 ms 7220 KB Output is correct - L = 64
19 Correct 81 ms 6368 KB Output is correct - L = 64
20 Correct 130 ms 7716 KB Output is correct - L = 64
21 Correct 128 ms 7620 KB Output is correct - L = 64
22 Correct 87 ms 6816 KB Output is correct - L = 64
23 Correct 83 ms 6824 KB Output is correct - L = 64
24 Correct 90 ms 6800 KB Output is correct - L = 64