oj.uz

Submission #259171

# Submission time Handle Problem Language Result Execution time Memory
259171 2020-08-07T09:51:09 Z imeimi2000 한자 끝말잇기 (JOI14_kanji) C++17
100 / 100
 216 ms 27360 KB 
#include "Annalib.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

static void dijkstra(vector<pll> edge[], llong dist[], int prev[], int s) {
    priority_queue<pll> pq;
    pq.emplace(dist[s] = 0, s);
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        d = -d;
        if (dist[x] != d) continue;
        for (auto [i, c] : edge[x]) {
            if (d + c < dist[i]) pq.emplace(-(dist[i] = d + c), i), prev[i] = x;
        }
    }
}

const static llong inf = 4e18;
static vector<pll> edge[300];
static llong distK[6][300], distQ[60][300];
static int par[300], a;

static llong get_dist(int i, int x, int k) {
    if (k) return distQ[i][a] + distK[k][x];
    return distQ[i][x];
}

void Anna(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[]) {
    a = A[U[0]];
    for (int i = 0; i < m; ++i) {
        bool in = 0;
        for (int j = 0; j < k; ++j) if (i == U[j]) in = 1;
        if (!in) edge[A[i]].emplace_back(B[i], C[i]);
    }
    memset(distQ, 0x3f, sizeof(distQ));
    for (int i = 0; i < q; ++i) {
        dijkstra(edge, distQ[i], par, S[i]);
    }
    memset(distK, 0x3f, sizeof(distK));
    for (int i = 1; i <= k; ++i) {
        dijkstra(edge, distK[i], par, B[U[i - 1]]);
        for (int j = 0; j < n; ++j) distK[i][j] += C[U[i - 1]];
    }
    vector<int> G[6];
    for (int i = 0; i < q; ++i) G[0].push_back(i);
    unsigned long long ret = 0;
    vector<unsigned> mul, add;
    for (int w = 1; w <= k; ++w) {
        for (int i = 0; i < w; ++i) {
            vector<int> O, N;
            for (int g : G[i]) {
                if (distQ[g][a] >= inf || distK[w][T[g]] >= inf) O.push_back(g);
                else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                else (get_dist(g, T[g], i) <= get_dist(g, T[g], w) ? O : N).push_back(g);
            }
            mul.push_back(G[i].size() + 1u);
            add.push_back(O.size());
            G[i] = O;
            for (int j : N) G[w].push_back(j);
        }
    }
    for (int i = mul.size(); i--; ) ret = ret * mul[i] + add[i];
    while (ret) Tap(ret & 1u), ret >>= 1;
}
#include "Brunolib.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

static void dijkstra(vector<pll> edge[], llong dist[], int prev[], int s) {
    priority_queue<pll> pq;
    pq.emplace(dist[s] = 0, s);
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        d = -d;
        if (dist[x] != d) continue;
        for (auto [i, c] : edge[x]) {
            if (d + c < dist[i]) pq.emplace(-(dist[i] = d + c), i), prev[i] = x;
        }
    }
}

const static llong inf = 4e18;
static vector<pll> edge[300];
static llong distK[6][300], distQ[60][300];
static int parK[6][300], parQ[60][300], a;

static llong get_dist(int i, int x, int k) {
    if (k) return distQ[i][a] + distK[k][x];
    return distQ[i][x];
}

void Bruno(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[], int l, int V[]) {
    unsigned long long ret = 0;
    while (l--) ret = ret << 1 | unsigned(V[l]);
    a = A[U[0]];
    map<pll, int> idx;
    for (int i = 0; i < m; ++i) {
        idx[pll(A[i], B[i])] = i;
        if (C[i] != -1) edge[A[i]].emplace_back(B[i], C[i]);
    }
    memset(distQ, 0x3f, sizeof(distQ));
    for (int i = 0; i < q; ++i) {
        dijkstra(edge, distQ[i], parQ[i], S[i]);
    }
    memset(distK, 0x3f, sizeof(distK));
    for (int i = 1; i <= k; ++i) {
        dijkstra(edge, distK[i], parK[i], B[U[i - 1]]);
    }
    vector<int> G[6];
    for (int i = 0; i < q; ++i) G[0].push_back(i);
    for (int w = 1; w <= k; ++w) {
        for (int i = 0; i < w; ++i) {
            int cnt = ret % (G[i].size() + 1u);
            ret /= G[i].size() + 1u;
            vector<int> nG, O, N;
            for (int g : G[i]) {
                if (distQ[g][a] >= inf || distK[w][T[g]] >= inf) O.push_back(g), --cnt;
                else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                else nG.push_back(g);
            }
            sort(nG.begin(), nG.end(), [&](int a, int b) {
                return get_dist(a, T[a], i) - get_dist(a, T[a], w) < get_dist(b, T[b], i) - get_dist(b, T[b], w);
            });
            for (int j = 0; j < int(nG.size()); ++j) (j < cnt ? O : N).push_back(nG[j]);
            G[i] = O;
            for (int j : N) G[w].push_back(j);
        }
    }
    int res[60];
    for (int i = 0; i <= k; ++i) for (int j : G[i]) res[j] = i;
    for (int i = 0; i < q; ++i) {
        int x = T[i];
        vector<int> path;
        if (res[i]) {
            for (; x != B[U[res[i] - 1]]; x = parK[res[i]][x]) path.push_back(idx[pll(parK[res[i]][x], x)]);
            path.push_back(U[res[i] - 1]);
            x = a;
        }
        for (; x != S[i]; x = parQ[i][x]) path.push_back(idx[pll(parQ[i][x], x)]);
        for (int j = path.size(); j--; ) Answer(path[j]);
        Answer(-1);
    }
}

Compilation message

Anna.cpp: In function 'void Anna(int, int, int*, int*, llong*, int, int*, int*, int, int*)':
Anna.cpp:56:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, int*, int*, llong*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:57:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4912 KB Output is correct - L = 24
2 Correct 6 ms 4908 KB Output is correct - L = 23
3 Correct 6 ms 5168 KB Output is correct - L = 20
4 Correct 6 ms 4764 KB Output is correct - L = 27
5 Correct 7 ms 4892 KB Output is correct - L = 24
6 Correct 6 ms 4864 KB Output is correct - L = 27
7 Correct 6 ms 4716 KB Output is correct - L = 30
8 Correct 7 ms 5048 KB Output is correct - L = 18
9 Correct 10 ms 5240 KB Output is correct - L = 18
10 Correct 13 ms 5700 KB Output is correct - L = 18
11 Correct 7 ms 4824 KB Output is correct - L = 4
12 Correct 176 ms 26280 KB Output is correct - L = 18
13 Correct 7 ms 4908 KB Output is correct - L = 26
14 Correct 7 ms 4824 KB Output is correct - L = 1

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5012 KB Output is correct - L = 63
2 Correct 8 ms 5232 KB Output is correct - L = 63
3 Correct 8 ms 5028 KB Output is correct - L = 45
4 Correct 10 ms 5168 KB Output is correct - L = 44
5 Correct 8 ms 4908 KB Output is correct - L = 61
6 Correct 10 ms 5188 KB Output is correct - L = 60
7 Correct 10 ms 5292 KB Output is correct - L = 34
8 Correct 10 ms 5292 KB Output is correct - L = 34
9 Correct 8 ms 5436 KB Output is correct - L = 64
10 Correct 8 ms 5436 KB Output is correct - L = 64
11 Correct 8 ms 5308 KB Output is correct - L = 64
12 Correct 10 ms 5420 KB Output is correct - L = 30
13 Correct 205 ms 25328 KB Output is correct - L = 30
14 Correct 9 ms 5176 KB Output is correct - L = 60
15 Correct 9 ms 5164 KB Output is correct - L = 38
16 Correct 16 ms 5512 KB Output is correct - L = 34
17 Correct 20 ms 5928 KB Output is correct - L = 37
18 Correct 28 ms 6988 KB Output is correct - L = 42
19 Correct 6 ms 4924 KB Output is correct - L = 37
20 Correct 26 ms 7552 KB Output is correct - L = 30
21 Correct 36 ms 7792 KB Output is correct - L = 30
22 Correct 8 ms 5524 KB Output is correct - L = 63
23 Correct 8 ms 5688 KB Output is correct - L = 64
24 Correct 8 ms 5436 KB Output is correct - L = 64

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5140 KB Output is correct - L = 63
2 Correct 8 ms 5228 KB Output is correct - L = 63
3 Correct 8 ms 5184 KB Output is correct - L = 45
4 Correct 8 ms 5168 KB Output is correct - L = 44
5 Correct 8 ms 4908 KB Output is correct - L = 61
6 Correct 10 ms 5176 KB Output is correct - L = 60
7 Correct 10 ms 5416 KB Output is correct - L = 34
8 Correct 10 ms 5400 KB Output is correct - L = 34
9 Correct 7 ms 5308 KB Output is correct - L = 64
10 Correct 7 ms 5524 KB Output is correct - L = 64
11 Correct 8 ms 5308 KB Output is correct - L = 64
12 Correct 12 ms 5416 KB Output is correct - L = 30
13 Correct 216 ms 25132 KB Output is correct - L = 30
14 Correct 10 ms 5172 KB Output is correct - L = 60
15 Correct 13 ms 5164 KB Output is correct - L = 38
16 Correct 20 ms 5512 KB Output is correct - L = 34
17 Correct 20 ms 6344 KB Output is correct - L = 37
18 Correct 30 ms 7116 KB Output is correct - L = 42
19 Correct 7 ms 5052 KB Output is correct - L = 37
20 Correct 26 ms 7552 KB Output is correct - L = 30
21 Correct 37 ms 7656 KB Output is correct - L = 30
22 Correct 8 ms 5536 KB Output is correct - L = 63
23 Correct 8 ms 5664 KB Output is correct - L = 64
24 Correct 7 ms 5308 KB Output is correct - L = 64

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5140 KB Output is correct - L = 63
2 Correct 8 ms 5184 KB Output is correct - L = 63
3 Correct 8 ms 5044 KB Output is correct - L = 45
4 Correct 8 ms 5560 KB Output is correct - L = 44
5 Correct 8 ms 5164 KB Output is correct - L = 61
6 Correct 10 ms 5180 KB Output is correct - L = 60
7 Correct 10 ms 5416 KB Output is correct - L = 34
8 Correct 10 ms 5396 KB Output is correct - L = 34
9 Correct 8 ms 5392 KB Output is correct - L = 64
10 Correct 8 ms 5664 KB Output is correct - L = 64
11 Correct 8 ms 5512 KB Output is correct - L = 64
12 Correct 10 ms 5308 KB Output is correct - L = 30
13 Correct 207 ms 27360 KB Output is correct - L = 30
14 Correct 10 ms 5436 KB Output is correct - L = 60
15 Correct 10 ms 5424 KB Output is correct - L = 38
16 Correct 14 ms 5516 KB Output is correct - L = 34
17 Correct 20 ms 6108 KB Output is correct - L = 37
18 Correct 28 ms 6948 KB Output is correct - L = 42
19 Correct 7 ms 4924 KB Output is correct - L = 37
20 Correct 26 ms 7568 KB Output is correct - L = 30
21 Correct 37 ms 7672 KB Output is correct - L = 30
22 Correct 8 ms 5528 KB Output is correct - L = 63
23 Correct 8 ms 5452 KB Output is correct - L = 64
24 Correct 7 ms 5524 KB Output is correct - L = 64

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5012 KB Output is correct - L = 63
2 Correct 8 ms 5140 KB Output is correct - L = 63
3 Correct 7 ms 5192 KB Output is correct - L = 45
4 Correct 9 ms 5164 KB Output is correct - L = 44
5 Correct 8 ms 4888 KB Output is correct - L = 61
6 Correct 12 ms 5144 KB Output is correct - L = 60
7 Correct 8 ms 5016 KB Output is correct - L = 34
8 Correct 10 ms 5396 KB Output is correct - L = 34
9 Correct 8 ms 5528 KB Output is correct - L = 64
10 Correct 8 ms 5540 KB Output is correct - L = 64
11 Correct 8 ms 5408 KB Output is correct - L = 64
12 Correct 10 ms 5144 KB Output is correct - L = 30
13 Correct 212 ms 23124 KB Output is correct - L = 30
14 Correct 11 ms 5300 KB Output is correct - L = 60
15 Correct 9 ms 5144 KB Output is correct - L = 38
16 Correct 19 ms 5516 KB Output is correct - L = 34
17 Correct 24 ms 5956 KB Output is correct - L = 37
18 Correct 35 ms 6476 KB Output is correct - L = 42
19 Correct 7 ms 4932 KB Output is correct - L = 37
20 Correct 26 ms 7044 KB Output is correct - L = 30
21 Correct 37 ms 7588 KB Output is correct - L = 30
22 Correct 8 ms 5532 KB Output is correct - L = 63
23 Correct 8 ms 5532 KB Output is correct - L = 64
24 Correct 8 ms 5520 KB Output is correct - L = 64