oj.uz

Submission #6155

# Submission time Handle Problem Language Result Execution time Memory
6155 2014-06-21T07:38:22 Z gs12117 한자 끝말잇기 (JOI14_kanji) C++
100 / 100
 872 ms 92972 KB 
#include "Annalib.h"
#define ull unsigned long long
#define INF 4000000000000000000LL
#include<stdio.h>
static ull w[301][301];
static bool v[90010];
static int R[61], cnt[5];
static int hc[62][6];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
    int i, j, k, x, y, xx, yy;
    ull g;
    for (i = 0; i < K; i++){
        v[U[i]] = true;
    }
    for (i = 0; i < Q; i++)R[i] = -1;
    for (i = 0; i < N; i++){
        for (j = 0; j < N; j++){
            if (i != j)w[i][j] = INF;
            else w[i][j] = 0;
        }
    }
    for (i = 0; i < M; i++){
        if (!v[i])w[A[i]][B[i]] = C[i];
    }
    for (k = 0; k < N; k++){
        for (i = 0; i < N; i++){
            for (j = 0; j < N; j++){
                if (w[i][j]>w[i][k] + w[k][j])w[i][j] = w[i][k] + w[k][j];
            }
        }
    }
    for (i = 0; i < K; i++){
        x = A[U[i]], y = B[U[i]];
        for (j = 0; j < Q; j++){
            xx = S[j], yy = T[j];
            g = w[xx][x] + w[y][yy] + C[U[i]];
            if (w[xx][yy]>g){
                w[xx][yy] = g;
                R[j] = i;
            }
        }
    }
    for (i = 0; i < Q; i++){
        if (R[i] != -1)cnt[R[i]]++;
    }
    hc[1][0]=1;
    for(i=0;i<=Q+1;i++){
    	for(j=0;j<=K;j++){
    		if(i!=0){
    			hc[i][j]+=hc[i-1][j];
    		}
    		if(j!=0){
    			hc[i][j]+=hc[i][j-1];
    		}
    	}
    }
    j=0;
    k=Q;
    for (i = 0; i < K; i++){
		k-=cnt[i];
    	j+=hc[k][K-i];
    }
    j=hc[Q+1][K]-j;
    for(i=0;j;i++){
    	if(j>1){
    		Tap(j%2);
    	}
    	j/=2;
    }
}

#include "Brunolib.h"
#define ull unsigned long long
#define INF 4000000000000000000LL
#include<stdio.h>
static ull w[310][310], w3[310][310];
static int w2[310][310];
static ull P[5][60];
static ull D[321293][2], G[6], cnt[6];
static int par[60][321293], Res[60];
static int n;
static int hc[62][6];
void Do(int a, int b)
{
    int i;
    ull gap = w[a][b];
    while (1){
        if (a == b)break;
        for (i = 0; i < n; i++){
            if (a != i && w2[a][i]&& w3[a][i] + w[i][b] == gap)break;
        }
        gap -= w3[a][i];
        Answer(w2[a][i] - 1);
        a = i;
    }
}
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
    n = N;
    int i, j, k, x, y;
    ull t1, t2, t3;
    for (i = 0; i < N; i++){
        for (j = 0; j < N; j++){
            if (i != j)w[i][j] = INF;
            else w[i][j] = 0;
        }
    }
    for (i = 0; i < M; i++){
        if (C[i] != -1){
            w[A[i]][B[i]] = C[i];
        }
        w2[A[i]][B[i]] = i + 1;
        w3[A[i]][B[i]] = C[i];
    }
    for (k = 0; k < N; k++){
        for (i = 0; i < N; i++){
            for (j = 0; j < N; j++){
                if (w[i][j]>w[i][k] + w[k][j])w[i][j] = w[i][k] + w[k][j];
            }
        }
    }
    for (i = 0; i < K; i++){
        for (j = 0; j < Q; j++){
            t1 = w[S[j]][T[j]];
            t2 = w[S[j]][A[U[i]]];
            t3 = w[B[U[i]]][T[j]];
            if (t2 == INF || t3 == INF)continue;
            if (t2 + t3 >= t1)continue;
            P[i][j] = t1 - t2 - t3;
        }
    }
    hc[1][0]=1;
    for(i=0;i<=Q+1;i++){
    	for(j=0;j<=K;j++){
    		if(i!=0){
    			hc[i][j]+=hc[i-1][j];
    		}
    		if(j!=0){
    			hc[i][j]+=hc[i][j-1];
    		}
    	}
    }
    j=1;
    for(i=0;i<L;i++){
		j*=2;
		j+=X[L-1-i];
    }
    j=hc[Q+1][K]-j+1;
    G[0] = 1;
    int l=Q;
    for (i = 0; i < K; i++){
		for(k=0;k<=Q;k++){
			if(hc[k+1][K-i]>=j)break;
		}
		j-=hc[k][K-i];
		cnt[i]=l-k;
		l=k;
        G[i + 1] = G[i] * (cnt[i] + 1);
    }
    for (i = 0; i < Q; i++){
        for (j = 0; j < G[K]; j++)par[i][j] = -1;
        for (j = G[K] - 1; j >= 0; j--){
            if (j && (!D[j][0] && !D[j][1]))continue;
            for (k = 0; k < K; k++){
                if (!P[k][i])continue;
                if ((j % G[k + 1]) / G[k] == cnt[k])continue;
                t1 = D[j][0];
                t2 = P[k][i] + D[j][1];
                t1 += t2 >> 40, t2 &= ((1ll << 40) - 1);
                if (D[j + G[k]][0] < t1 || (D[j + G[k]][0] == t1&&D[j + G[k]][1] < t2)){
                    D[j + G[k]][0] = t1;
                    D[j + G[k]][1] = t2;
                    par[i][j + G[k]] = k;
                }
            }
        }
    }
    x = G[K] - 1, y = Q - 1;
    for (i = 0; i < Q; i++)Res[i] = -1;
    while (x){
        if (par[y][x] == -1){
            y--;
            continue;
        }
        Res[y] = par[y][x];
        x -= G[par[y][x]];
        y--;
    }
    for (i = 0; i < Q; i++){
        if (Res[i] == -1){
            Do(S[i], T[i]);
        }
        else{
            Do(S[i], A[U[Res[i]]]);
            Answer(U[Res[i]]);
            Do(B[U[Res[i]]], T[i]);
        }
        Answer(-1);
    }
}

Compilation message

Bruno.cpp: In function 'void Bruno(int, int, int*, int*, long long int*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < G[K]; j++)par[i][j] = -1;
                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 92972 KB Output is correct - L = 10
2 Correct 62 ms 92972 KB Output is correct - L = 9
3 Correct 58 ms 92972 KB Output is correct - L = 8
4 Correct 78 ms 92972 KB Output is correct - L = 11
5 Correct 58 ms 92972 KB Output is correct - L = 11
6 Correct 66 ms 92972 KB Output is correct - L = 11
7 Correct 66 ms 92972 KB Output is correct - L = 11
8 Correct 65 ms 92972 KB Output is correct - L = 11
9 Correct 78 ms 92972 KB Output is correct - L = 9
10 Correct 95 ms 92972 KB Output is correct - L = 11
11 Correct 62 ms 92972 KB Output is correct - L = 1
12 Correct 202 ms 92972 KB Output is correct - L = 0
13 Correct 62 ms 92972 KB Output is correct - L = 11
14 Correct 78 ms 92972 KB Output is correct - L = 0

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 92972 KB Output is correct - L = 22
2 Correct 201 ms 92972 KB Output is correct - L = 22
3 Correct 72 ms 92972 KB Output is correct - L = 22
4 Correct 66 ms 92972 KB Output is correct - L = 22
5 Correct 262 ms 92972 KB Output is correct - L = 22
6 Correct 216 ms 92972 KB Output is correct - L = 21
7 Correct 59 ms 92972 KB Output is correct - L = 19
8 Correct 66 ms 92972 KB Output is correct - L = 19
9 Correct 792 ms 92972 KB Output is correct - L = 22
10 Correct 785 ms 92972 KB Output is correct - L = 22
11 Correct 792 ms 92972 KB Output is correct - L = 22
12 Correct 69 ms 92972 KB Output is correct - L = 0
13 Correct 222 ms 92972 KB Output is correct - L = 0
14 Correct 132 ms 92972 KB Output is correct - L = 22
15 Correct 69 ms 92972 KB Output is correct - L = 17
16 Correct 81 ms 92972 KB Output is correct - L = 15
17 Correct 95 ms 92972 KB Output is correct - L = 22
18 Correct 96 ms 92972 KB Output is correct - L = 19
19 Correct 72 ms 92972 KB Output is correct - L = 15
20 Correct 78 ms 92972 KB Output is correct - L = 0
21 Correct 106 ms 92972 KB Output is correct - L = 0
22 Correct 872 ms 92972 KB Output is correct - L = 22
23 Correct 782 ms 92972 KB Output is correct - L = 22
24 Correct 812 ms 92972 KB Output is correct - L = 22

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 92972 KB Output is correct - L = 22
2 Correct 201 ms 92972 KB Output is correct - L = 22
3 Correct 66 ms 92972 KB Output is correct - L = 22
4 Correct 65 ms 92972 KB Output is correct - L = 22
5 Correct 236 ms 92972 KB Output is correct - L = 22
6 Correct 222 ms 92972 KB Output is correct - L = 21
7 Correct 66 ms 92972 KB Output is correct - L = 19
8 Correct 68 ms 92972 KB Output is correct - L = 19
9 Correct 798 ms 92972 KB Output is correct - L = 22
10 Correct 798 ms 92972 KB Output is correct - L = 22
11 Correct 822 ms 92972 KB Output is correct - L = 22
12 Correct 69 ms 92972 KB Output is correct - L = 0
13 Correct 212 ms 92972 KB Output is correct - L = 0
14 Correct 129 ms 92972 KB Output is correct - L = 22
15 Correct 62 ms 92972 KB Output is correct - L = 17
16 Correct 75 ms 92972 KB Output is correct - L = 15
17 Correct 108 ms 92972 KB Output is correct - L = 22
18 Correct 98 ms 92972 KB Output is correct - L = 19
19 Correct 62 ms 92972 KB Output is correct - L = 15
20 Correct 81 ms 92972 KB Output is correct - L = 0
21 Correct 109 ms 92972 KB Output is correct - L = 0
22 Correct 832 ms 92972 KB Output is correct - L = 22
23 Correct 788 ms 92972 KB Output is correct - L = 22
24 Correct 818 ms 92972 KB Output is correct - L = 22

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 92972 KB Output is correct - L = 22
2 Correct 198 ms 92972 KB Output is correct - L = 22
3 Correct 81 ms 92972 KB Output is correct - L = 22
4 Correct 65 ms 92972 KB Output is correct - L = 22
5 Correct 252 ms 92972 KB Output is correct - L = 22
6 Correct 229 ms 92972 KB Output is correct - L = 21
7 Correct 62 ms 92972 KB Output is correct - L = 19
8 Correct 66 ms 92972 KB Output is correct - L = 19
9 Correct 798 ms 92972 KB Output is correct - L = 22
10 Correct 832 ms 92972 KB Output is correct - L = 22
11 Correct 768 ms 92972 KB Output is correct - L = 22
12 Correct 55 ms 92972 KB Output is correct - L = 0
13 Correct 231 ms 92972 KB Output is correct - L = 0
14 Correct 135 ms 92972 KB Output is correct - L = 22
15 Correct 72 ms 92972 KB Output is correct - L = 17
16 Correct 81 ms 92972 KB Output is correct - L = 15
17 Correct 92 ms 92972 KB Output is correct - L = 22
18 Correct 95 ms 92972 KB Output is correct - L = 19
19 Correct 65 ms 92972 KB Output is correct - L = 15
20 Correct 81 ms 92972 KB Output is correct - L = 0
21 Correct 102 ms 92972 KB Output is correct - L = 0
22 Correct 782 ms 92972 KB Output is correct - L = 22
23 Correct 799 ms 92972 KB Output is correct - L = 22
24 Correct 782 ms 92972 KB Output is correct - L = 22

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 92972 KB Output is correct - L = 22
2 Correct 206 ms 92972 KB Output is correct - L = 22
3 Correct 66 ms 92972 KB Output is correct - L = 22
4 Correct 69 ms 92972 KB Output is correct - L = 22
5 Correct 222 ms 92972 KB Output is correct - L = 22
6 Correct 215 ms 92972 KB Output is correct - L = 21
7 Correct 62 ms 92972 KB Output is correct - L = 19
8 Correct 66 ms 92972 KB Output is correct - L = 19
9 Correct 795 ms 92972 KB Output is correct - L = 22
10 Correct 772 ms 92972 KB Output is correct - L = 22
11 Correct 826 ms 92972 KB Output is correct - L = 22
12 Correct 69 ms 92972 KB Output is correct - L = 0
13 Correct 215 ms 92972 KB Output is correct - L = 0
14 Correct 135 ms 92972 KB Output is correct - L = 22
15 Correct 62 ms 92972 KB Output is correct - L = 17
16 Correct 86 ms 92972 KB Output is correct - L = 15
17 Correct 88 ms 92972 KB Output is correct - L = 22
18 Correct 84 ms 92972 KB Output is correct - L = 19
19 Correct 66 ms 92972 KB Output is correct - L = 15
20 Correct 78 ms 92972 KB Output is correct - L = 0
21 Correct 108 ms 92972 KB Output is correct - L = 0
22 Correct 802 ms 92972 KB Output is correct - L = 22
23 Correct 812 ms 92972 KB Output is correct - L = 22
24 Correct 799 ms 92972 KB Output is correct - L = 22