oj.uz

Submission #703445

# Submission time Handle Problem Language Result Execution time Memory
703445 2023-02-27T12:14:29 Z KoD 한자 끝말잇기 (JOI14_kanji) C++17
0 / 100
 468 ms 262144 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() / 2;

    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() / 2;

    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 (adj[k][j] != -1 and d[i][j] == d[i][k] + d[k][j]) {
                    rev[i][j] = adj[k][j];
                }
            }
        }
    }

    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]] <= C[U[k]] - C[U[j]], 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6416 KB Output is correct - L = 64
2 Correct 88 ms 6308 KB Output is correct - L = 64
3 Correct 106 ms 6360 KB Output is correct - L = 64
4 Incorrect 76 ms 6340 KB Output isn't correct - Wrong Answer [9]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 451 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 468 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 454 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 436 ms 262144 KB Execution killed with signal 9
2 Incorrect 76 ms 6496 KB Output isn't correct - Wrong Answer [4]
3 Correct 84 ms 6520 KB Output is correct - L = 64
4 Correct 79 ms 6748 KB Output is correct - L = 64
5 Incorrect 79 ms 6524 KB Output isn't correct - Wrong Answer [9]
6 Incorrect 78 ms 6696 KB Output isn't correct - Wrong Answer [9]
7 Correct 77 ms 6656 KB Output is correct - L = 64
8 Incorrect 77 ms 6616 KB Output isn't correct - Wrong Answer [9]
9 Incorrect 79 ms 6780 KB Output isn't correct - Wrong Answer [9]
10 Incorrect 98 ms 6784 KB Output isn't correct - Wrong Answer [9]
11 Incorrect 80 ms 6872 KB Output isn't correct - Wrong Answer [9]
12 Correct 77 ms 6812 KB Output is correct - L = 64
13 Incorrect 189 ms 17456 KB Output isn't correct - Wrong Answer [9]
14 Incorrect 77 ms 6768 KB Output isn't correct - Wrong Answer [4]
15 Correct 81 ms 6612 KB Output is correct - L = 64
16 Correct 93 ms 7052 KB Output is correct - L = 64
17 Incorrect 96 ms 6876 KB Output isn't correct - Wrong Answer [9]
18 Incorrect 110 ms 7320 KB Output isn't correct - Wrong Answer [9]
19 Incorrect 96 ms 6476 KB Output isn't correct - Wrong Answer [9]
20 Correct 146 ms 7564 KB Output is correct - L = 64
21 Incorrect 121 ms 7568 KB Output isn't correct - Wrong Answer [9]
22 Incorrect 77 ms 6796 KB Output isn't correct - Wrong Answer [9]
23 Incorrect 78 ms 6808 KB Output isn't correct - Wrong Answer [9]
24 Incorrect 88 ms 6884 KB Output isn't correct - Wrong Answer [9]