oj.uz

Submission #218608

# Submission time Handle Problem Language Result Execution time Memory
218608 2020-04-02T11:36:43 Z EntityIT 한자 끝말잇기 (JOI14_kanji) C++14
98 / 100
 219 ms 14268 KB 
#include<bits/stdc++.h>
using namespace std;

#include "Annalib.h"

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const LL infLL = 4e18;

void Anna(int N, int M, int A[], int B[], LL C[], int Q, int S[], int T[], int K, int U[]) {
    vector<vector<LL> > d(N, vector<LL>(N, infLL) );
    for (int u = 0; u < N; ++u) d[u][u] = 0;
    for (int i = 0; i < M; ++i) d[ A[i] ][ B[i] ] = C[i];
    for (int i = 0; i < K; ++i) d[ A[ U[i] ] ][ B[ U[i] ] ] = infLL;
    for (int w = 0; w < N; ++w) {
        for (int u = 0; u < N; ++u) {
            for (int v = 0; v < N; ++v) {
                asMn(d[u][v], d[u][w] + d[w][v]);
            }
        }
    }

    vector<int> group(Q, -1);
    vector<LL> ans(Q);
    for (int i = 0; i < Q; ++i) ans[i] = d[ S[i] ][ T[i] ];

    for (int i = 0; i < K; ++i) {
        vector<int> cnt(i + 1);
        for (int j = 0; j <= i; ++j) cnt[j] = count(all(group), j - 1);
        vector<int> cnt2(i + 1);
        for (int j = 0; j < Q; ++j) if (asMn(ans[j], C[ U[i] ] + d[ S[j] ][ A[ U[i] ] ] + d[ B[ U[i] ] ][ T[j] ]) ) {
            ++cnt2[ group[j] + 1 ];
            group[j] = i;
        }

        int lim = 1, tmp = 0;
        for (int j = 0; j <= i; ++j) {
            lim *= cnt[j] + 1;
            tmp *= cnt[j] + 1; tmp += cnt2[j];
        }

        for (int j = __lg(lim - 1); ~j; --j) Tap(tmp >> j & 1);
    }
}
#include<bits/stdc++.h>
using namespace std;

#include "Brunolib.h"

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const LL infLL = 4e18;

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[]) {
    vector<vector<LL> > d(N, vector<LL>(N, infLL) ),
                        trace(N, vector<LL>(N, -1) );
    for (int u = 0; u < N; ++u) d[u][u] = 0;
    for (int i = 0; i < M; ++i) {
        d[ A[i] ][ B[i] ] = C[i];
        trace[ A[i] ][ B[i] ] = i;
    }
    for (int i = 0; i < K; ++i) {
        d[ A[ U[i] ] ][ B[ U[i] ] ] = infLL;
        trace[ A[ U[i] ] ][ B[ U[i] ] ] = -1;
    }
    for (int w = 0; w < N; ++w) {
        for (int u = 0; u < N; ++u) {
            for (int v = 0; v < N; ++v) {
                if (asMn(d[u][v], d[u][w] + d[w][v]) ) trace[u][v] = trace[u][w];
            }
        }
    }

    auto get = [&](int iQ, int i, int j) {
        return d[ S[iQ] ][ A[ U[j] ] ] + d[ B[ U[j] ] ][ T[iQ] ]
             - (~i ? d[ S[iQ] ][ A[ U[i] ] ] + d[ B[ U[i] ] ][ T[iQ] ] : d[ S[iQ] ][ T[iQ] ]);
    };
    vector<int> group(Q, -1);

    for (int i = 0, iX = 0; i < K; ++i) {
        vector<vector<int> > iQ(i + 1);
        for (int j = 0; j < Q; ++j) iQ[ group[j] + 1 ].emplace_back(j);
        for (auto &j : iQ) {
            sort(all(j), [&](const int &a, const int &b) {
                return get(a, group[a], i) < get(b, group[b], i);
            });
        }

        vector<int> cnt(i + 1);
        int lim = 1;
        for (int j = 0; j <= i; ++j) {
            cnt[j] = (int)count(all(group), j - 1);
            lim *= cnt[j] + 1;
        }

        int receive = 0;
        for (int j = __lg(lim - 1); ~j; --j) if (X[iX++]) receive |= 1 << j;

        vector<int> tmp(i + 1);
        for (int j = i; ~j; --j) {
            tmp[j] = receive % (cnt[j] + 1);
            receive /= cnt[j] + 1;
        }

        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k < tmp[j]; ++k) group[ iQ[j][k] ] = i;
        }
    }

    function<void(int, int)> answer = [&](int u, int v) {
        if (u == v) return ;
        Answer(trace[u][v]);
        answer(B[ trace[u][v] ], v);
    };
    for (int i = 0; i < Q; ++i) {
        if (~group[i]) {
            answer(S[i], A[ U[ group[i] ] ]);
            Answer(U[ group[i] ]);
            answer(B[ U[ group[i] ] ], T[i]);
        }
        else answer(S[i], T[i]);
        Answer(-1);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6580 KB Output is correct - L = 27
2 Correct 65 ms 6672 KB Output is correct - L = 25
3 Correct 74 ms 6660 KB Output is correct - L = 23
4 Correct 74 ms 6556 KB Output is correct - L = 29
5 Correct 62 ms 6560 KB Output is correct - L = 26
6 Correct 61 ms 6564 KB Output is correct - L = 29
7 Correct 60 ms 6420 KB Output is correct - L = 32
8 Correct 72 ms 6840 KB Output is correct - L = 20
9 Correct 79 ms 6756 KB Output is correct - L = 20
10 Correct 86 ms 7176 KB Output is correct - L = 20
11 Correct 63 ms 6576 KB Output is correct - L = 5
12 Correct 219 ms 13628 KB Output is correct - L = 20
13 Correct 73 ms 6696 KB Output is correct - L = 29
14 Correct 75 ms 6588 KB Output is correct - L = 1

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 6928 KB Output is correct - L = 64
2 Correct 65 ms 6860 KB Output is correct - L = 64
3 Correct 62 ms 6828 KB Output is correct - L = 46
4 Correct 61 ms 6928 KB Output is correct - L = 46
5 Correct 63 ms 6692 KB Output is correct - L = 64
6 Correct 66 ms 6948 KB Output is correct - L = 63
7 Correct 63 ms 6932 KB Output is correct - L = 34
8 Correct 64 ms 7040 KB Output is correct - L = 34
9 Correct 60 ms 7024 KB Output is correct - L = 65
10 Correct 64 ms 7060 KB Output is correct - L = 65
11 Correct 63 ms 7020 KB Output is correct - L = 65
12 Correct 65 ms 6932 KB Output is correct - L = 30
13 Correct 194 ms 14268 KB Output is correct - L = 30
14 Correct 69 ms 6932 KB Output is correct - L = 62
15 Correct 64 ms 6944 KB Output is correct - L = 40
16 Correct 80 ms 7180 KB Output is correct - L = 34
17 Correct 84 ms 7152 KB Output is correct - L = 39
18 Correct 89 ms 7656 KB Output is correct - L = 42
19 Correct 63 ms 6580 KB Output is correct - L = 38
20 Correct 81 ms 8032 KB Output is correct - L = 30
21 Correct 90 ms 8016 KB Output is correct - L = 30
22 Correct 62 ms 7056 KB Output is correct - L = 64
23 Correct 63 ms 7188 KB Output is correct - L = 65
24 Correct 63 ms 7020 KB Output is correct - L = 65

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6936 KB Output is correct - L = 64
2 Correct 64 ms 6852 KB Output is correct - L = 64
3 Correct 64 ms 6828 KB Output is correct - L = 46
4 Correct 63 ms 7032 KB Output is correct - L = 46
5 Correct 65 ms 6668 KB Output is correct - L = 64
6 Correct 68 ms 6952 KB Output is correct - L = 63
7 Correct 66 ms 6916 KB Output is correct - L = 34
8 Correct 65 ms 7052 KB Output is correct - L = 34
9 Correct 65 ms 7052 KB Output is correct - L = 65
10 Correct 66 ms 6972 KB Output is correct - L = 65
11 Correct 65 ms 7172 KB Output is correct - L = 65
12 Correct 66 ms 6964 KB Output is correct - L = 30
13 Correct 194 ms 13728 KB Output is correct - L = 30
14 Correct 69 ms 7072 KB Output is correct - L = 62
15 Correct 71 ms 6912 KB Output is correct - L = 40
16 Correct 77 ms 7060 KB Output is correct - L = 34
17 Correct 84 ms 6996 KB Output is correct - L = 39
18 Correct 95 ms 7868 KB Output is correct - L = 42
19 Correct 64 ms 6684 KB Output is correct - L = 38
20 Correct 75 ms 8040 KB Output is correct - L = 30
21 Correct 96 ms 7912 KB Output is correct - L = 30
22 Correct 65 ms 7316 KB Output is correct - L = 64
23 Correct 61 ms 7032 KB Output is correct - L = 65
24 Correct 61 ms 7020 KB Output is correct - L = 65

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6832 KB Output is correct - L = 64
2 Correct 63 ms 6844 KB Output is correct - L = 64
3 Correct 62 ms 6824 KB Output is correct - L = 46
4 Correct 63 ms 7044 KB Output is correct - L = 46
5 Correct 66 ms 6708 KB Output is correct - L = 64
6 Correct 68 ms 7060 KB Output is correct - L = 63
7 Correct 64 ms 6936 KB Output is correct - L = 34
8 Correct 65 ms 6956 KB Output is correct - L = 34
9 Correct 62 ms 7108 KB Output is correct - L = 65
10 Correct 64 ms 7036 KB Output is correct - L = 65
11 Correct 68 ms 6972 KB Output is correct - L = 65
12 Correct 64 ms 6956 KB Output is correct - L = 30
13 Correct 203 ms 13904 KB Output is correct - L = 30
14 Correct 69 ms 6948 KB Output is correct - L = 62
15 Correct 72 ms 6948 KB Output is correct - L = 40
16 Correct 80 ms 6892 KB Output is correct - L = 34
17 Correct 93 ms 7440 KB Output is correct - L = 39
18 Correct 89 ms 7432 KB Output is correct - L = 42
19 Correct 66 ms 6572 KB Output is correct - L = 38
20 Correct 79 ms 8028 KB Output is correct - L = 30
21 Correct 124 ms 7784 KB Output is correct - L = 30
22 Correct 63 ms 7060 KB Output is correct - L = 64
23 Correct 65 ms 7052 KB Output is correct - L = 65
24 Correct 66 ms 6972 KB Output is correct - L = 65

Subtask #5
18.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6908 KB Output is correct - L = 64
2 Correct 66 ms 6820 KB Output is correct - L = 64
3 Correct 64 ms 7064 KB Output is correct - L = 46
4 Correct 65 ms 7036 KB Output is correct - L = 46
5 Correct 63 ms 6684 KB Output is correct - L = 64
6 Correct 69 ms 6940 KB Output is correct - L = 63
7 Correct 66 ms 6904 KB Output is correct - L = 34
8 Correct 72 ms 6968 KB Output is correct - L = 34
9 Correct 66 ms 7052 KB Output is partially correct - L = 65
10 Correct 76 ms 7308 KB Output is partially correct - L = 65
11 Correct 63 ms 7020 KB Output is partially correct - L = 65
12 Correct 65 ms 7060 KB Output is correct - L = 30
13 Correct 201 ms 13896 KB Output is correct - L = 30
14 Correct 65 ms 7052 KB Output is correct - L = 62
15 Correct 87 ms 6936 KB Output is correct - L = 40
16 Correct 78 ms 7100 KB Output is correct - L = 34
17 Correct 86 ms 7164 KB Output is correct - L = 39
18 Correct 91 ms 7520 KB Output is correct - L = 42
19 Correct 64 ms 6572 KB Output is correct - L = 38
20 Correct 90 ms 8068 KB Output is correct - L = 30
21 Correct 102 ms 8036 KB Output is correct - L = 30
22 Correct 73 ms 7056 KB Output is correct - L = 64
23 Correct 62 ms 7064 KB Output is partially correct - L = 65
24 Correct 64 ms 7044 KB Output is partially correct - L = 65