oj.uz

Submission #259099

# Submission time Handle Problem Language Result Execution time Memory
259099 2020-08-07T07:58:31 Z 강태규(#5095) 한자 끝말잇기 (JOI14_kanji) C++14
0 / 100
 862 ms 262148 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 < 7; ++i) {
        val[i] *= 6;
        if (val[i] >> 20) val[i + 1] += val[i] >> 20, val[i] &= (1 << 20) - 1;
    }
    val[7] *= 6;
    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);
    }
}

Compilation message

Anna.cpp: In function 'void dijkstra(std::vector<std::pair<long long int, long long int> >*, llong*, int*, int)':
Anna.cpp:12:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [d, x] = pq.top(); pq.pop();
              ^
Anna.cpp:15:19: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for (auto [i, c] : edge[x]) {
                   ^

Bruno.cpp: In function 'void dijkstra(std::vector<std::pair<long long int, long long int> >*, llong*, int*, int)':
Bruno.cpp:12:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [d, x] = pq.top(); pq.pop();
              ^
Bruno.cpp:15:19: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for (auto [i, c] : edge[x]) {
                   ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4548 KB Output isn't correct - Wrong Answer [9]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 754 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 758 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 751 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 770 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 9 ms 4860 KB Output isn't correct - Wrong Answer [7]
3 Runtime error 827 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 728 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Incorrect 9 ms 4556 KB Output isn't correct - Wrong Answer [7]
6 Incorrect 10 ms 4780 KB Output isn't correct - Wrong Answer [9]
7 Runtime error 723 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 12 ms 4916 KB Output isn't correct - Wrong Answer [9]
9 Incorrect 9 ms 5052 KB Output isn't correct - Wrong Answer [9]
10 Incorrect 8 ms 5172 KB Output isn't correct - Wrong Answer [9]
11 Incorrect 8 ms 4924 KB Output isn't correct - Wrong Answer [9]
12 Correct 11 ms 4908 KB Output isn't correct - L = 160
13 Correct 219 ms 23328 KB Output isn't correct - L = 160
14 Runtime error 719 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 769 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Incorrect 17 ms 5004 KB Output isn't correct - Wrong Answer [9]
17 Incorrect 25 ms 5600 KB Output isn't correct - Wrong Answer [9]
18 Incorrect 32 ms 6408 KB Output isn't correct - Wrong Answer [9]
19 Runtime error 862 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Correct 27 ms 7188 KB Output isn't correct - L = 160
21 Correct 41 ms 7144 KB Output isn't correct - L = 160
22 Incorrect 8 ms 5052 KB Output isn't correct - Wrong Answer [9]
23 Incorrect 8 ms 4924 KB Output isn't correct - Wrong Answer [9]
24 Incorrect 8 ms 5052 KB Output isn't correct - Wrong Answer [9]