oj.uz

Submission #259102

# Submission time Handle Problem Language Result Execution time Memory
259102 2020-08-07T08:08:02 Z 강태규(#5095) 한자 끝말잇기 (JOI14_kanji) C++17
40 / 100
 228 ms 26852 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;
        }
    }
}

static vector<pll> edge[300];
static llong dist[300];
static int par[300], val[8];

static void add(int x) {
    for (int i = 0; i < 8; ++i) {
        val[i] *= 6;
    }
    for (int i = 0; i < 7; ++i) {
        if (val[i] >> 20) val[i + 1] += val[i] >> 20, val[i] &= (1 << 20) - 1;
    }
    val[0] += x;
    for (int i = 0; i < 7; ++i) {
        if (val[i] >> 20) val[i + 1] += val[i] >> 20, val[i] &= (1 << 20) - 1;
    }
}

void Anna(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[]) {
    for (int i = 0; i < m; ++i) edge[A[i]].emplace_back(B[i], C[i]);
    for (int i = 0; i < q; ++i) {
        memset(dist, 0x3f, sizeof(dist));
        dijkstra(edge, dist, par, S[i]);
        int idx = 0;
        for (int x = T[i]; x != S[i]; x = par[x]) if (par[x] == A[U[0]]) {
            for (int j = 0; j < k; ++j) if (x == B[U[j]]) idx = j + 1;
        }
        add(idx);
    }
    for (int i = 0; i < 160; ++i) Tap((val[i / 20] >> i % 20) & 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;
        }
    }
}

static vector<pll> edge[300];
static llong dist[300];
static int par[300], val[8];

static int sub() {
    int ret;
    for (int i = 8; i--; ) {
        if (i) val[i - 1] += val[i] % 6 << 20;
        else ret = val[i] % 6;
        val[i] /= 6;
    }
    return ret;
}

void Bruno(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[], int, int V[]) {
    for (int i = 0; i < 160; ++i) {
        if (V[i]) val[i / 20] |= 1 << i % 20;
    }
    map<pll, int> ei;
    for (int i = 0; i < m; ++i) {
        if (C[i] == -1) continue;
        edge[A[i]].emplace_back(B[i], C[i]);
        ei[pll(A[i], B[i])] = i;
    }
    int idxes[100];
    for (int i = q; i--; ) {
        idxes[i] = sub();
    }
    for (int i = 0; i < q; ++i) {
        int idx = idxes[i];
        int mid1 = idx ? A[U[0]] : S[i], mid2 = idx ? B[U[idx - 1]] : S[i];
        vector<int> path;
        memset(dist, 0x3f, sizeof(dist));
        dijkstra(edge, dist, par, mid2);
        for (int x = T[i]; x != mid2; x = par[x]) path.push_back(ei[pll(par[x], x)]);
        if (idx) path.push_back(U[idx - 1]);
        memset(dist, 0x3f, sizeof(dist));
        dijkstra(edge, dist, par, S[i]);
        for (int x = mid1; x != S[i]; x = par[x]) path.push_back(ei[pll(par[x], x)]);
        for (int j = path.size(); j--; ) Answer(path[j]);
        Answer(-1);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4504 KB Output is correct - L = 160
2 Correct 7 ms 4548 KB Output is correct - L = 160
3 Correct 8 ms 4800 KB Output is correct - L = 160
4 Correct 6 ms 4576 KB Output is correct - L = 160
5 Correct 6 ms 4564 KB Output is correct - L = 160
6 Correct 6 ms 4508 KB Output is correct - L = 160
7 Correct 6 ms 4500 KB Output is correct - L = 160
8 Correct 8 ms 4864 KB Output is correct - L = 160
9 Correct 10 ms 5012 KB Output is correct - L = 160
10 Correct 12 ms 5444 KB Output is correct - L = 160
11 Correct 6 ms 4596 KB Output is correct - L = 160
12 Correct 176 ms 25344 KB Output is correct - L = 160
13 Correct 7 ms 4540 KB Output is correct - L = 160
14 Correct 6 ms 4592 KB Output is correct - L = 160

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4772 KB Output is correct - L = 160
2 Correct 9 ms 4644 KB Output is correct - L = 160
3 Correct 8 ms 4788 KB Output is correct - L = 160
4 Correct 9 ms 4788 KB Output is correct - L = 160
5 Correct 9 ms 4540 KB Output is correct - L = 160
6 Correct 11 ms 4796 KB Output is correct - L = 160
7 Correct 10 ms 4924 KB Output is correct - L = 160
8 Correct 11 ms 4924 KB Output is correct - L = 160
9 Correct 8 ms 5156 KB Output is correct - L = 160
10 Correct 8 ms 4940 KB Output is correct - L = 160
11 Correct 9 ms 5160 KB Output is correct - L = 160
12 Correct 11 ms 4932 KB Output is correct - L = 160
13 Correct 214 ms 26696 KB Output is correct - L = 160
14 Correct 9 ms 4944 KB Output is correct - L = 160
15 Correct 11 ms 4796 KB Output is correct - L = 160
16 Correct 16 ms 5276 KB Output is correct - L = 160
17 Correct 20 ms 5544 KB Output is correct - L = 160
18 Correct 32 ms 6892 KB Output is correct - L = 160
19 Correct 8 ms 4540 KB Output is correct - L = 160
20 Correct 26 ms 7056 KB Output is correct - L = 160
21 Correct 43 ms 7160 KB Output is correct - L = 160
22 Correct 8 ms 5068 KB Output is correct - L = 160
23 Correct 9 ms 5172 KB Output is correct - L = 160
24 Correct 8 ms 4940 KB Output is correct - L = 160

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4804 KB Output is correct - L = 160
2 Correct 8 ms 4644 KB Output is correct - L = 160
3 Correct 9 ms 4832 KB Output is correct - L = 160
4 Correct 9 ms 4788 KB Output is correct - L = 160
5 Correct 10 ms 4684 KB Output is correct - L = 160
6 Correct 11 ms 4796 KB Output is correct - L = 160
7 Correct 12 ms 5060 KB Output is correct - L = 160
8 Correct 11 ms 5052 KB Output is correct - L = 160
9 Correct 8 ms 5160 KB Output is correct - L = 160
10 Correct 10 ms 5068 KB Output is correct - L = 160
11 Correct 8 ms 5068 KB Output is correct - L = 160
12 Correct 12 ms 4924 KB Output is correct - L = 160
13 Correct 228 ms 26852 KB Output is correct - L = 160
14 Correct 9 ms 4940 KB Output is correct - L = 160
15 Correct 9 ms 4796 KB Output is correct - L = 160
16 Correct 20 ms 5272 KB Output is correct - L = 160
17 Correct 22 ms 5596 KB Output is correct - L = 160
18 Correct 31 ms 6632 KB Output is correct - L = 160
19 Correct 8 ms 4572 KB Output is correct - L = 160
20 Correct 34 ms 7188 KB Output is correct - L = 160
21 Correct 40 ms 7164 KB Output is correct - L = 160
22 Correct 9 ms 5040 KB Output is correct - L = 160
23 Correct 8 ms 5168 KB Output is correct - L = 160
24 Correct 8 ms 5168 KB Output is correct - L = 160

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4772 KB Output isn't correct - L = 160
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4808 KB Output isn't correct - L = 160
2 Correct 8 ms 4756 KB Output isn't correct - L = 160
3 Correct 9 ms 4968 KB Output isn't correct - L = 160
4 Correct 8 ms 4772 KB Output isn't correct - L = 160
5 Correct 9 ms 4556 KB Output isn't correct - L = 160
6 Correct 10 ms 4760 KB Output isn't correct - L = 160
7 Correct 11 ms 4908 KB Output isn't correct - L = 160
8 Correct 12 ms 5016 KB Output isn't correct - L = 160
9 Correct 8 ms 4920 KB Output isn't correct - L = 160
10 Correct 8 ms 4768 KB Output isn't correct - L = 160
11 Correct 8 ms 4912 KB Output isn't correct - L = 160
12 Correct 11 ms 4924 KB Output isn't correct - L = 160
13 Correct 219 ms 22760 KB Output isn't correct - L = 160
14 Correct 10 ms 4940 KB Output isn't correct - L = 160
15 Correct 9 ms 4908 KB Output isn't correct - L = 160
16 Correct 16 ms 5232 KB Output isn't correct - L = 160
17 Correct 20 ms 5352 KB Output isn't correct - L = 160
18 Correct 31 ms 5960 KB Output isn't correct - L = 160
19 Correct 8 ms 4564 KB Output isn't correct - L = 160
20 Correct 26 ms 6532 KB Output isn't correct - L = 160
21 Correct 41 ms 6652 KB Output isn't correct - L = 160
22 Correct 8 ms 4768 KB Output isn't correct - L = 160
23 Correct 8 ms 4768 KB Output isn't correct - L = 160
24 Correct 8 ms 4768 KB Output isn't correct - L = 160