Submission #25900

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
25900	2017-06-25T03:20:34 Z	model_code	Tales of seafaring (POI13_mor)	C++11	100 / 100	2029 ms	21908 KB

/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Morskie opowiesci                             *
 *   Autor:                Mateusz Baranowski                            *
 *   Zlozonosc czasowa:    O(n(n + m) + k)                               *
 *   Zlozonosc pamieciowa: O(n + m + k)                                  *
 *   Opis:                 Rozwiazanie wzorcowe                          *
 *                         Dla kazdego wierzcholka szukamy najkrotszej   *
 *                         sciezki dlugosci parzystej i nieparzystej     *
 *                                                                       *
 *************************************************************************/

#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> przygody_t;

int n, m, k;
vector<int> szlaki[MAX_N + 1];
vector<przygody_t> przygody;
bool wyniki[MAX_K];

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));
    }
}

void sprawdz_przygody() {
    vector<int> poczatek[MAX_N + 1];
    for (size_t i = 0; i < przygody.size(); ++i) {
        int u = przygody[i].first.first, v = przygody[i].first.second;
        if (poczatek[u].empty()) {
            poczatek[v].push_back(i);
        } else {
            poczatek[u].push_back(i);
        }
    }
    int odl[2][MAX_N + 1];
    for (int i = 1; i <= n; ++i) {
        for (int l = 0; l <= n; ++l) {
            odl[0][l] = INFTY;
            odl[1][l] = INFTY;
        }
        if (!poczatek[i].empty()) {
            int pocz[2], kon[2], q[2][MAX_N + 2];
            pocz[0] = 0;
            kon[0] = 1;
            pocz[1] = 0;
            kon[1] = 0;
            q[0][0] = i;
            int k = 0;
            int d = 1;
            while (pocz[k] < kon[k]) {
                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;
                }
            }
        }
        vector<int>::const_iterator it;
        for (it = poczatek[i].begin(); it != poczatek[i].end(); ++it) {
            int d = przygody[*it].second;
            int u = przygody[*it].first.first;
            if (u == i) {
                u = przygody[*it].first.second;
            }
            wyniki[*it] = (odl[d % 2][u] <= d);
        }
    }
}

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

Compilation message

mor.cpp: In function 'void wczytaj_dane()':
mor.cpp:33: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:36: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:41: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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2656 KB	Output is correct
2	Correct	0 ms	2656 KB	Output is correct
3	Correct	0 ms	2652 KB	Output is correct
4	Correct	556 ms	21852 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2656 KB	Output is correct
2	Correct	0 ms	2652 KB	Output is correct
3	Correct	0 ms	2652 KB	Output is correct
4	Correct	523 ms	21908 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	2656 KB	Output is correct
2	Correct	2652 KB	Output is correct
3	Correct	2648 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2792 KB	Output is correct
2	Correct	0 ms	2784 KB	Output is correct
3	Correct	9 ms	2656 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2956 KB	Output is correct
2	Correct	9 ms	2956 KB	Output is correct
3	Correct	46 ms	2968 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	3296 KB	Output is correct
2	Correct	9 ms	2948 KB	Output is correct
3	Correct	229 ms	3016 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	803 ms	21208 KB	Output is correct
2	Correct	13 ms	2784 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1539 ms	21620 KB	Output is correct
2	Correct	123 ms	7172 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1566 ms	21072 KB	Output is correct
2	Correct	283 ms	11844 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2029 ms	21064 KB	Output is correct
2	Correct	579 ms	21052 KB	Output is correct