oj.uz

Submission #1089

# Submission time Handle Problem Language Result Execution time Memory
1089 2013-06-24T19:46:58 Z tncks0121 백신 (KOI13_vaccine) C++
24 / 24
 582 ms 27260 KB 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
const int INF = 987654321; 
const ll LINF = 1e15;  

const int N_ = 105, M_ = 1005;
const int SN_ = 250005;
const int lgSN_ = 20;

int N, K, A[M_];
int S[SN_], X[SN_], SN;

int SA[SN_], SS[SN_], Ord[lgSN_][SN_];
int L, lgL;

bool cmpS (const int &a, const int &b) {
    return S[a] < S[b];
}

bool cmpSA (const int &a, const int &b) {
    if(Ord[lgL][a] != Ord[lgL][b]) return Ord[lgL][a] < Ord[lgL][b];
    int ta = 0, tb = 0;
    if(a + L <= SN) ta = Ord[lgL][a + L];
    if(b + L <= SN) tb = Ord[lgL][b + L];
    return ta < tb;
}

int LCP (int x, int y) {
    int r = 0;
    for(int i = lgL; --i; ) {
        if(Ord[i][x+r] == Ord[i][y+r]) r |= 1<<i;
    }
    return r;
}

int chk[N_];

int start[SN_], lnk[SN_], val[SN_];

int main() {
    
    int i, j, k;
    
    scanf("%d%d", &N, &K);
    for(i = 1; i <= N; i++) {
        int mi; scanf("%d", &mi);
        for(j = 1; j <= mi; j++) scanf("%d", A+j);
        for(j = 1; j <= mi; j++) ++SN, S[SN] = A[j], X[SN] = i; S[++SN] = 0;
        for(j = mi; j >= 1; j--) ++SN, S[SN] = A[j], X[SN] = i; S[++SN] = 0;
    }
    
    for(i = 1; i <= SN; i++) SS[i] = SS[i - 1] + (S[i] == 0), SA[i] = i;
    for(i = 1; i <= SN; i++) Ord[0][i] = S[i];
    
    for(L = 1, lgL = 0; L <= SN * 2; L <<= 1, lgL++) {
        for(k = L; k >= 0; k -= L) {
            for(i = 1; i <= SN; i++) {
                int v = 0; if(SA[i] + k <= SN) v = Ord[lgL][SA[i] + k];
                lnk[i] = start[v]; start[v] = i; 
                val[i] = SA[i];
            }
            int sn = SN;
            i = SN; if(L == 1) i = 10000;
            for(; i >= 0; i--) {
                for(j = start[i]; j > 0; j = lnk[j]) {
                    SA[sn--] = val[j];
                    val[j] = 0;
                }
                start[i] = 0;
            }
        }
        sort(SA + 1, SA + SN + 1, cmpSA);
        int *O = Ord[lgL + 1]; O[SA[1]] = 1;
        for(i = 2; i <= SN; i++) {
            O[SA[i]] = O[SA[i - 1]];
            if(cmpSA(SA[i - 1], SA[i])) ++O[SA[i]];
        }
    }
    
    for(i = 1; i <= SN; i = j) {
        int count = 1; if(X[SA[i]] == 0) count = 0;
        chk[X[SA[i]]] = i;
        for(j = i + 1; j <= SN; j++) {
            if(LCP(SA[j - 1], SA[j]) < K) break;
            if(chk[X[SA[j]]] != i && X[SA[j]] > 0) ++count;
            chk[X[SA[j]]] = i;
        }
        if(count == N) {
            if(SS[SA[i] + K - 1] - SS[SA[i] - 1] > 0) continue;
            puts("YES");
            return 0;
        }
    }
    
    puts("NO");
    return 0;
}

Subtask #1
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27260 KB Output is correct
2 Correct 0 ms 27260 KB Output is correct
3 Correct 0 ms 27260 KB Output is correct
4 Correct 0 ms 27260 KB Output is correct
5 Correct 0 ms 27260 KB Output is correct
6 Correct 0 ms 27260 KB Output is correct
7 Correct 0 ms 27260 KB Output is correct
8 Correct 0 ms 27260 KB Output is correct
9 Correct 0 ms 27260 KB Output is correct
10 Correct 0 ms 27260 KB Output is correct

Subtask #2
3.12 / 3.12

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27260 KB Output is correct
2 Correct 0 ms 27260 KB Output is correct
3 Correct 0 ms 27260 KB Output is correct
4 Correct 0 ms 27260 KB Output is correct
5 Correct 0 ms 27260 KB Output is correct
6 Correct 0 ms 27260 KB Output is correct
7 Correct 0 ms 27260 KB Output is correct
8 Correct 0 ms 27260 KB Output is correct
9 Correct 0 ms 27260 KB Output is correct
10 Correct 0 ms 27260 KB Output is correct

Subtask #3
3.6 / 3.6

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27260 KB Output is correct
2 Correct 1 ms 27260 KB Output is correct
3 Correct 1 ms 27260 KB Output is correct
4 Correct 2 ms 27260 KB Output is correct
5 Correct 0 ms 27260 KB Output is correct
6 Correct 1 ms 27260 KB Output is correct
7 Correct 0 ms 27260 KB Output is correct
8 Correct 6 ms 27260 KB Output is correct
9 Correct 10 ms 27260 KB Output is correct
10 Correct 6 ms 27260 KB Output is correct

Subtask #4
4.32 / 4.32

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27260 KB Output is correct
2 Correct 9 ms 27260 KB Output is correct
3 Correct 8 ms 27260 KB Output is correct
4 Correct 3 ms 27260 KB Output is correct
5 Correct 4 ms 27260 KB Output is correct
6 Correct 9 ms 27260 KB Output is correct
7 Correct 9 ms 27260 KB Output is correct
8 Correct 10 ms 27260 KB Output is correct
9 Correct 8 ms 27260 KB Output is correct
10 Correct 10 ms 27260 KB Output is correct

Subtask #5
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 55 ms 27260 KB Output is correct
2 Correct 81 ms 27260 KB Output is correct
3 Correct 113 ms 27260 KB Output is correct
4 Correct 571 ms 27260 KB Output is correct
5 Correct 61 ms 27260 KB Output is correct
6 Correct 89 ms 27260 KB Output is correct
7 Correct 125 ms 27260 KB Output is correct
8 Correct 315 ms 27260 KB Output is correct
9 Correct 574 ms 27260 KB Output is correct
10 Correct 307 ms 27260 KB Output is correct

Subtask #6
5.52 / 5.52

# Verdict Execution time Memory Grader output
1 Correct 188 ms 27260 KB Output is correct
2 Correct 364 ms 27260 KB Output is correct
3 Correct 462 ms 27260 KB Output is correct
4 Correct 222 ms 27260 KB Output is correct
5 Correct 445 ms 27260 KB Output is correct
6 Correct 561 ms 27260 KB Output is correct
7 Correct 582 ms 27260 KB Output is correct
8 Correct 560 ms 27260 KB Output is correct
9 Correct 544 ms 27260 KB Output is correct
10 Correct 532 ms 27260 KB Output is correct