oj.uz

Submission #259148

# Submission time Handle Problem Language Result Execution time Memory
259148 2020-08-07T08:54:20 Z 반딧불(#5071) 한자 끝말잇기 (JOI14_kanji) C++14
40 / 100
 188 ms 18376 KB 
#include <bits/stdc++.h>
#include "Annalib.h"

using namespace std;

typedef long long ll;

namespace ANNA{
    ll dist[302][302];
    int track[302][302];
    int message[302];
    bool know[100002];
    ll dt[302];
};
using namespace ANNA;

void Anna(int n, int k, int A[], int B[], ll C[], int q, int S[], int T[], int m, int U[]) {
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i!=j) dist[i][j] = 4 * 1e18;
            else dist[i][j] = 0;
        }
    }
    for(int i=0; i<m; i++) know[U[i]] = 1;
    for(int i=0; i<k; i++){
        if(!know[i]) dist[A[i]][B[i]] = C[i], track[A[i]][B[i]] = -i-100;
    }
    for(int x=0; x<n; x++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(dist[i][x] + dist[x][j] < dist[i][j]){
                    track[i][j] = x;
                    dist[i][j] = dist[i][x] + dist[x][j];
                }
            }
        }
    }

    int stP = A[U[0]];

    for(int i=0; i<q; i++){
        dt[i] = dist[S[i]][T[i]];
        for(int j=0; j<m; j++){
            if(dt[i] > dist[S[i]][stP] + C[U[j]] + dist[B[U[j]]][T[i]]){
                dt[i] = dist[S[i]][stP] + C[U[j]] + dist[B[U[j]]][T[i]];
                message[i] = j+1;
            }
        }
        if(dt[i] > 3*1e18) exit(1);
//            printf("%d: %d %lld (%d %d %d %d)\n", i, message[i], dist[S[i]][A[U[0]]] + dist[B[U[message[i]-1]]][T[i]],
//                   S[i], A[U[0]], B[U[message[i]-1]], T[i]);
    }
    for(int i=0; i<60; i+=3){
        int mes = message[i] + message[i+1] * 6 + message[i+2] * 36;
        for(int j=0; j<8; j++){
            Tap(!!(mes & (1<<j)));
        }
    }
}

#include <bits/stdc++.h>
#include "Brunolib.h"

using namespace std;

typedef long long ll;

namespace BRUNO{
    ll dist[302][302];
    int track[302][302];
    int message[302];
    bool know[100002];
    ll dt[302];
};
using namespace BRUNO;

void answer(int x, int y){
    if(x==y) return;
    if(track[x][y] < 0){
        Answer(-track[x][y]-100);
        return;
    }
    int z = track[x][y];
    answer(x, z);
    answer(z, y);
}

void Bruno(int n, int k, int A[], int B[], ll C[], int q, int S[], int T[], int m, int U[], int L, int X[]) {
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i!=j) dist[i][j] = 4 * 1e18;
            else dist[i][j] = 0;
        }
    }
    for(int i=0; i<m; i++) know[U[i]] = 1;
    for(int i=0; i<k; i++){
        if(!know[i]) dist[A[i]][B[i]] = C[i], track[A[i]][B[i]] = -i-100;
    }
    for(int x=0; x<n; x++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(dist[i][x] + dist[x][j] < dist[i][j]){
                    track[i][j] = x;
                    dist[i][j] = dist[i][x] + dist[x][j];
                }
            }
        }
    }

    for(int i=0; i<60; i+=3){
        int mes = 0;
        for(int j=0; j<8; j++){
            mes += (1<<j) * X[i/3*8+j];
        }
        message[i] = mes % 6;
        message[i+1] = mes / 6 % 6;
        message[i+2] = mes / 36;
    }

    for(int i=0; i<q; i++){
        if(message[i] == 0){
            answer(S[i], T[i]);
        }
        else{
            answer(S[i], A[U[0]]);
            Answer(U[message[i] - 1]);
            answer(B[U[message[i]-1]], T[i]);
//            printf("%d: %d %lld (%d %d %d %d)\n", i, message[i], dist[S[i]][A[U[0]]] + dist[B[U[message[i]-1]]][T[i]],
//                   S[i], A[U[0]], B[U[message[i]-1]], T[i]);
        }
        Answer(-1);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6668 KB Output is correct - L = 160
2 Correct 59 ms 6792 KB Output is correct - L = 160
3 Correct 56 ms 6572 KB Output is correct - L = 160
4 Correct 53 ms 6416 KB Output is correct - L = 160
5 Correct 52 ms 6416 KB Output is correct - L = 160
6 Correct 54 ms 6576 KB Output is correct - L = 160
7 Correct 56 ms 6688 KB Output is correct - L = 160
8 Correct 63 ms 6544 KB Output is correct - L = 160
9 Correct 71 ms 6908 KB Output is correct - L = 160
10 Correct 74 ms 6892 KB Output is correct - L = 160
11 Correct 55 ms 6612 KB Output is correct - L = 160
12 Correct 184 ms 13920 KB Output is correct - L = 160
13 Correct 54 ms 6580 KB Output is correct - L = 160
14 Correct 53 ms 6732 KB Output is correct - L = 160

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6892 KB Output is correct - L = 160
2 Correct 54 ms 6876 KB Output is correct - L = 160
3 Correct 53 ms 6832 KB Output is correct - L = 160
4 Correct 56 ms 6884 KB Output is correct - L = 160
5 Correct 57 ms 6800 KB Output is correct - L = 160
6 Correct 57 ms 6832 KB Output is correct - L = 160
7 Correct 57 ms 6948 KB Output is correct - L = 160
8 Correct 58 ms 7060 KB Output is correct - L = 160
9 Correct 53 ms 6964 KB Output is correct - L = 160
10 Correct 54 ms 7328 KB Output is correct - L = 160
11 Correct 54 ms 7176 KB Output is correct - L = 160
12 Correct 58 ms 6948 KB Output is correct - L = 160
13 Correct 188 ms 18248 KB Output is correct - L = 160
14 Correct 56 ms 6828 KB Output is correct - L = 160
15 Correct 59 ms 6904 KB Output is correct - L = 160
16 Correct 68 ms 7200 KB Output is correct - L = 160
17 Correct 89 ms 7436 KB Output is correct - L = 160
18 Correct 83 ms 7680 KB Output is correct - L = 160
19 Correct 54 ms 6572 KB Output is correct - L = 160
20 Correct 67 ms 8560 KB Output is correct - L = 160
21 Correct 86 ms 8192 KB Output is correct - L = 160
22 Correct 52 ms 7200 KB Output is correct - L = 160
23 Correct 53 ms 7092 KB Output is correct - L = 160
24 Correct 55 ms 7180 KB Output is correct - L = 160

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6824 KB Output is correct - L = 160
2 Correct 56 ms 6876 KB Output is correct - L = 160
3 Correct 55 ms 6840 KB Output is correct - L = 160
4 Correct 54 ms 6820 KB Output is correct - L = 160
5 Correct 57 ms 6692 KB Output is correct - L = 160
6 Correct 58 ms 6928 KB Output is correct - L = 160
7 Correct 57 ms 6828 KB Output is correct - L = 160
8 Correct 57 ms 6948 KB Output is correct - L = 160
9 Correct 52 ms 7184 KB Output is correct - L = 160
10 Correct 52 ms 7200 KB Output is correct - L = 160
11 Correct 53 ms 7180 KB Output is correct - L = 160
12 Correct 56 ms 6956 KB Output is correct - L = 160
13 Correct 185 ms 18376 KB Output is correct - L = 160
14 Correct 55 ms 6828 KB Output is correct - L = 160
15 Correct 54 ms 7068 KB Output is correct - L = 160
16 Correct 69 ms 7140 KB Output is correct - L = 160
17 Correct 75 ms 7588 KB Output is correct - L = 160
18 Correct 80 ms 7680 KB Output is correct - L = 160
19 Correct 54 ms 6584 KB Output is correct - L = 160
20 Correct 71 ms 8184 KB Output is correct - L = 160
21 Correct 80 ms 8172 KB Output is correct - L = 160
22 Correct 53 ms 7100 KB Output is correct - L = 160
23 Correct 53 ms 6980 KB Output is correct - L = 160
24 Correct 53 ms 7196 KB Output is correct - L = 160

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 6916 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 56 ms 6820 KB Output isn't correct - L = 160
2 Correct 54 ms 6676 KB Output isn't correct - L = 160
3 Correct 55 ms 6836 KB Output isn't correct - L = 160
4 Correct 53 ms 6796 KB Output isn't correct - L = 160
5 Correct 54 ms 6580 KB Output isn't correct - L = 160
6 Correct 55 ms 6680 KB Output isn't correct - L = 160
7 Correct 61 ms 6832 KB Output isn't correct - L = 160
8 Correct 58 ms 6928 KB Output isn't correct - L = 160
9 Correct 56 ms 6976 KB Output isn't correct - L = 160
10 Correct 57 ms 6936 KB Output isn't correct - L = 160
11 Correct 52 ms 6948 KB Output isn't correct - L = 160
12 Correct 60 ms 6816 KB Output isn't correct - L = 160
13 Correct 181 ms 13952 KB Output isn't correct - L = 160
14 Correct 57 ms 6840 KB Output isn't correct - L = 160
15 Correct 58 ms 6800 KB Output isn't correct - L = 160
16 Correct 69 ms 6972 KB Output isn't correct - L = 160
17 Correct 75 ms 7176 KB Output isn't correct - L = 160
18 Correct 82 ms 7392 KB Output isn't correct - L = 160
19 Correct 57 ms 6564 KB Output isn't correct - L = 160
20 Correct 67 ms 7792 KB Output isn't correct - L = 160
21 Correct 80 ms 7896 KB Output isn't correct - L = 160
22 Correct 55 ms 6928 KB Output isn't correct - L = 160
23 Correct 56 ms 6944 KB Output isn't correct - L = 160
24 Correct 53 ms 7184 KB Output isn't correct - L = 160