Submission #25903

#	Time	Username	Problem	Language	Result	Execution time	Memory
25903		model_code	Tales of seafaring (POI13_mor)	C++11	50 / 100	3000 ms	20088 KiB

mor

/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Morskie opowiesci                             *
 *   Autor:                Mateusz Baranowski                            *
 *   Zlozonosc czasowa:    O(k(n + m))                                   *
 *   Zlozonosc pamieciowa: O(n + m + k)                                  *
 *   Opis:                 Rozwiazanie wolne                             *
 *                         Sprawdza kazda opowiesc osobno                *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_N 10000
#define MAX_M 10000
#define MAX_K 1000000
#define INFTY 1000000000

typedef pair< pair<int, int>, int> przygoda_t;

int n, m, k;
vector<int> szlaki[MAX_N + 1];
vector<przygoda_t> przygody;

void wczytaj_dane() {
    scanf("%d %d %d", &n, &m, &k);
    int u, v, len;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &u, &v);
        szlaki[u].push_back(v);
        szlaki[v].push_back(u);
    }
    for (int i = 0; i < k; ++i) {
        scanf("%d %d %d", &u, &v, &len);
        przygody.push_back(make_pair(make_pair(u, v), len));
    }
}

bool sprawdz_przygode(przygoda_t przygoda) {
    int a = przygoda.first.first;
    int b = przygoda.first.second;
    int c = przygoda.second;
    int odl[2][2 * MAX_N + 1];
    for (int l = 0; l <= n; ++l) {
        odl[0][l] = INFTY;
        odl[1][l] = INFTY;
    }
    int pocz[2], kon[2], q[2][MAX_N];
    pocz[0] = 0;
    kon[0] = 1;
    pocz[1] = 0;
    kon[1] = 0;
    q[0][0] = a;
    int k = 0;
    int d = 1;
    while (pocz[k] < kon[k] && odl[c%2][b] == INFTY) {
        int u = q[k][pocz[k]++];
        vector<int>::const_iterator it;
        for (it = szlaki[u].begin(); it != szlaki[u].end(); ++it) {
            if (odl[1 - k][*it] == INFTY) {
                odl[1 - k][*it] = d;
                q[1 - k][kon[1 - k]++] = *it;
            }
        }
        if (pocz[k] == kon[k]) {
            k = 1 - k;
            ++d;
        }
    }
    return (odl[c%2][b] <= c);
}

int main() {
    wczytaj_dane();
    for (int i = 0; i < k; ++i) {
        if (sprawdz_przygode(przygody[i])) {
            printf("TAK\n");
        } else {
            printf("NIE\n");
        }
    }
    return 0;
}

Compilation message (stderr)

mor.cpp: In function 'void wczytaj_dane()':
mor.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
                                  ^
mor.cpp:34:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
                               ^
mor.cpp:39:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &u, &v, &len);
                                        ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10