oj.uz

답안 #259094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259094 2020-08-07T07:35:27 Z 강태규(#5095) 한자 끝말잇기 (JOI14_kanji) C++17
0 / 100
 1000 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], V[160], N[160];

static void add(int x) {
    memcpy(N, V, sizeof(N));
    memset(V, 0, sizeof(N));
    for (int i = 0; i < 160; ++i) {
        if (i - 2 >= 0) V[i] += N[i - 2];
        if (i - 1 >= 0) V[i] += N[i - 1];
        if (V[i] >= 2) V[i + 1] += V[i] / 2, V[i] %= 2;
    }
    for (int i = 0; i < 3; ++i) {
        if (x & 1) ++V[i];
        x >>= 1;
    }
    for (int i = 0; i < 160; ++i) if (V[i] >= 2) V[i + 1] += V[i] / 2, V[i] %= 2;
}

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(V[i]);
}
#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], * V;

static int sub() {
    int val[8] = {};
    for (int i = 0; i < 160; ++i) {
        if (V[i]) val[i / 20] |= 1 << i % 20;
    }
    int ret = 0;
    for (int i = 8; i--; ) ret = (ret << 20 | val[i]) % 6;
    for (int i = 0; i < 3; ++i) {
        if ((ret >> i) & 1) --V[i];
    }
    for (int i = 0; i < 160; ++i) {
        if (V[i] < 0) V[i] += 2, --V[i + 1];
    }
    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 X[]) {
    V = X;
    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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4564 KB Output isn't correct - Wrong Answer [9]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 775 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 787 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 784 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 800 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 8 ms 4772 KB Output isn't correct - Wrong Answer [7]
3 Execution timed out 1069 ms 136312 KB Time limit exceeded
4 Runtime error 743 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Incorrect 9 ms 4696 KB Output isn't correct - Wrong Answer [9]
6 Runtime error 755 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Incorrect 11 ms 5196 KB Output isn't correct - Wrong Answer [9]
8 Incorrect 11 ms 5036 KB Output isn't correct - Wrong Answer [9]
9 Incorrect 9 ms 5168 KB Output isn't correct - Wrong Answer [9]
10 Incorrect 8 ms 5180 KB Output isn't correct - Wrong Answer [9]
11 Incorrect 9 ms 5156 KB Output isn't correct - Wrong Answer [9]
12 Correct 11 ms 4908 KB Output isn't correct - L = 160
13 Correct 223 ms 22804 KB Output isn't correct - L = 160
14 Incorrect 11 ms 4820 KB Output isn't correct - Wrong Answer [7]
15 Runtime error 847 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Incorrect 16 ms 5084 KB Output isn't correct - Wrong Answer [9]
17 Incorrect 23 ms 5608 KB Output isn't correct - Wrong Answer [9]
18 Incorrect 34 ms 6376 KB Output isn't correct - Wrong Answer [9]
19 Execution timed out 1097 ms 136224 KB Time limit exceeded
20 Correct 27 ms 6936 KB Output isn't correct - L = 160
21 Correct 40 ms 6888 KB Output isn't correct - L = 160
22 Incorrect 8 ms 5172 KB Output isn't correct - Wrong Answer [9]
23 Incorrect 8 ms 5052 KB Output isn't correct - Wrong Answer [9]
24 Incorrect 9 ms 4924 KB Output isn't correct - Wrong Answer [9]