oj.uz

Submission #25891

# Submission time Handle Problem Language Result Execution time Memory
25891 2017-06-25T03:04:10 Z model_code Walk (POI13_spa) C++11
100 / 100
 4143 ms 126116 KB 
/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Spacer                                        *
 *   Autor:                Wiktor Kuropatwa                              *
 *   Zlozonosc czasowa:    O(n^2 * k)                                    *
 *   Zlozonosc pamieciowa: O(nk)                                         *
 *   Opis:                 Rozwiazanie wzorcowe                          *
 *                                                                       *
 *************************************************************************/

#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;
    bool a = graphSearch(s,t,bound);
    hashSetClear(vhash,vfree,HSIZE);
    bool b = graphSearch(t,s,bound);
    return a && b;
}

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:90: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:99: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

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 126116 KB Output is correct
2 Correct 2366 ms 126116 KB Output is correct
3 Correct 4143 ms 126116 KB Output is correct
4 Correct 1223 ms 126116 KB Output is correct
5 Correct 1236 ms 126116 KB Output is correct
6 Correct 39 ms 126116 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 126116 KB Output is correct
2 Correct 33 ms 126116 KB Output is correct
3 Correct 33 ms 126116 KB Output is correct
4 Correct 9 ms 126116 KB Output is correct
5 Correct 6 ms 126116 KB Output is correct
6 Correct 6 ms 126116 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 126116 KB Output is correct
2 Correct 13 ms 126116 KB Output is correct
3 Correct 23 ms 126116 KB Output is correct
4 Correct 56 ms 126116 KB Output is correct
5 Correct 36 ms 126116 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 126116 KB Output is correct
2 Correct 1506 ms 126116 KB Output is correct
3 Correct 2936 ms 126116 KB Output is correct
4 Correct 773 ms 126116 KB Output is correct
5 Correct 376 ms 126116 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 126116 KB Output is correct
2 Correct 209 ms 126116 KB Output is correct
3 Correct 386 ms 126116 KB Output is correct
4 Correct 1493 ms 126116 KB Output is correct
5 Correct 719 ms 126116 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 126116 KB Output is correct
2 Correct 2043 ms 126116 KB Output is correct
3 Correct 3626 ms 126116 KB Output is correct
4 Correct 1853 ms 126116 KB Output is correct
5 Correct 906 ms 126116 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 126116 KB Output is correct
2 Correct 469 ms 126116 KB Output is correct
3 Correct 833 ms 126116 KB Output is correct
4 Correct 56 ms 126116 KB Output is correct
5 Correct 1283 ms 126116 KB Output is correct