oj.uz

Submission #6154

# Submission time Handle Problem Language Result Execution time Memory
6154 2014-06-21T07:35:17 Z gs12117 한자 끝말잇기 (JOI14_kanji) C++
10 / 100
 242 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[61][7];
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=1;
    k=Q;
    for (i = 0; i < K; i++){
		k-=cnt[i];
    	j+=hc[k][K-i];
    }
    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];
    }
    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:88: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 62 ms 92972 KB Output is correct - L = 10
2 Correct 66 ms 92972 KB Output is correct - L = 11
3 Correct 66 ms 92972 KB Output is correct - L = 11
4 Correct 65 ms 92972 KB Output is correct - L = 9
5 Correct 68 ms 92972 KB Output is correct - L = 9
6 Correct 58 ms 92972 KB Output is correct - L = 7
7 Correct 62 ms 92972 KB Output is correct - L = 9
8 Correct 75 ms 92972 KB Output is correct - L = 0
9 Correct 81 ms 92972 KB Output is correct - L = 10
10 Correct 86 ms 92972 KB Output is correct - L = 0
11 Correct 68 ms 92972 KB Output is correct - L = 2
12 Correct 242 ms 92972 KB Output is correct - L = 11
13 Correct 58 ms 92972 KB Output is correct - L = 8
14 Correct 62 ms 92972 KB Output is correct - L = 1

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 5780 KB Execution killed with signal 11 (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 29 ms 5780 KB Execution killed with signal 11 (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 29 ms 5780 KB Execution killed with signal 11 (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 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 26 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 26 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 33 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 33 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 33 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 33 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 89 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 33 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 36 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 43 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 46 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 43 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 46 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 29 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 36 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 26 ms 5780 KB Execution killed with signal 11 (could be triggered by violating memory limits)