oj.uz

답안 #25892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25892 2017-06-25T03:04:54 Z model_code Walk (POI13_spa) C++11
24 / 100
 2156 ms 126116 KB 
/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Spacer                                        *
 *   Autor:                Wiktor Kuropatwa                              *
 *   Zlozonosc czasowa:    O(n^2 * k)                                    *
 *   Zlozonosc pamieciowa: O(nk)                                         *
 *   Opis:                 Rozwiazanie bledne                            *
 *                         Przeszukuje graf tylko blisko jednego         *
 *                         z wierzcholkow x i y.                         *
 *                                                                       *
 *************************************************************************/

#include <cstdio>

const int HSIZE = 5000011;
const int EMPTY = 0;
const int MAXK = 500009;

long long forbidden[MAXK];
int fprev[MAXK];
int fhash[MAXK];
long long visited[HSIZE];
int vprev[HSIZE];
int vhash[HSIZE];
int vfree = 1, ffree = 1;
long long q[HSIZE];

inline void hashSetInsert(long long* set, int* prev, int* hash, int &free, long long value, int size)
{
    set[free] = value;
    prev[free] = hash[value%size];
    hash[value%size] = free++;
}

inline bool hashSetLookup(long long* set, int* prev, int* hash, long long value, int size)
{
    for(int t = hash[value%size]; t>0; t=prev[t])
        if(set[t] == value) return true;
    return false;
}

inline void hashSetClear(int* hash, int &free, int size)
{
    free = 1;
    for(int i = 0; i<size; i++)
        hash[i] = 0;
}

int n,k;

bool graphSearch(long long s, long long t, int bound)
{
    int b = 0, e = 0;
    int c = 1;
    q[e++] = s;
    hashSetInsert(visited,vprev,vhash,vfree,s,HSIZE);
    while(b < e && c < bound)
    {
        long long v = q[b++];
        for(int i = 0; i<n; i++)
        {
            long long next = v ^ (1LL << i);
            if(next == t) return true;
            if(!hashSetLookup(forbidden,fprev,fhash,next,MAXK) && !hashSetLookup(visited,vprev,vhash,next,HSIZE))
            {
                q[e++] = next;
                hashSetInsert(visited,vprev,vhash,vfree,next,HSIZE);
                c++;
            }
        }
    }
    if(c >= bound) return true;
    return false;
}

bool solve(long long s, long long t)
{
    int bound = n*k+1;
    return graphSearch(s,t,bound);
}

long long x,y;

long long readBinary()
{
    char buf[100];
    scanf("%s", buf);
    long long r = 0;
    for(int i = n-1; i>=0; i--)
        if(buf[i] == '1')
            r += (1LL<<(n-i-1));
    return r;
}
void read()
{
    scanf("%d %d", &n, &k);
    x = readBinary();
    y = readBinary();
    for(int i = 0; i<k; i++)
    {
        long long a;
        a = readBinary();
        hashSetInsert(forbidden,fprev,fhash,ffree,a,MAXK);
    }
}

int main()
{
    read();
    if(solve(x,y))
        printf("TAK\n");
    else
        printf("NIE\n");
}

Compilation message

spa.cpp: In function 'long long int readBinary()':
spa.cpp:89:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", buf);
                     ^
spa.cpp: In function 'void read()':
spa.cpp:98:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
                           ^

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 126116 KB Output is correct
2 Correct 0 ms 126116 KB Output is correct
3 Correct 0 ms 126116 KB Output is correct
4 Correct 0 ms 126116 KB Output is correct
5 Correct 0 ms 126116 KB Output is correct
6 Correct 0 ms 126116 KB Output is correct
7 Correct 0 ms 126116 KB Output is correct
8 Correct 0 ms 126116 KB Output is correct
9 Correct 0 ms 126116 KB Output is correct
10 Correct 0 ms 126116 KB Output is correct
11 Correct 76 ms 126116 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 126116 KB Output is correct
2 Correct 129 ms 126116 KB Output is correct
3 Correct 2156 ms 126116 KB Output is correct
4 Correct 69 ms 126116 KB Output is correct
5 Correct 1133 ms 126116 KB Output is correct
6 Correct 33 ms 126116 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 126116 KB Output is correct
2 Incorrect 13 ms 126116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 126116 KB Output is correct
2 Correct 3 ms 126116 KB Output is correct
3 Correct 9 ms 126116 KB Output is correct
4 Correct 36 ms 126116 KB Output is correct
5 Incorrect 36 ms 126116 KB Output isn't correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 126116 KB Output is correct
2 Incorrect 1386 ms 126116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 126116 KB Output is correct
2 Incorrect 213 ms 126116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 126116 KB Output is correct
2 Incorrect 2043 ms 126116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 126116 KB Output is correct
2 Correct 39 ms 126116 KB Output is correct
3 Correct 523 ms 126116 KB Output is correct
4 Correct 86 ms 126116 KB Output is correct
5 Incorrect 1483 ms 126116 KB Output isn't correct