oj.uz

Submission #391237

# Submission time Handle Problem Language Result Execution time Memory
391237 2021-04-18T09:46:46 Z palilo Tales of seafaring (POI13_mor) C++17
100 / 100
 1422 ms 36744 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 0x3f3f3f3f;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> adj(n);
    for (int u, v; m--;) {
        cin >> u >> v, --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    vector<vector<tuple<int, int, int>>> query(n);
    for (int i = 0, u, v, d; i < k; ++i) {
        cin >> u >> v >> d, --u, --v;
        query[u].emplace_back(v, d, i);
    }

    vector<pair<int, int>> dist(n);
    auto bfs = [&](int src) {
        fill(dist.begin(), dist.end(), make_pair(INF, INF));
        dist[src].first = 0;

        queue<int> q;
        q.emplace(src);

        while (!q.empty()) {
            auto u = q.front();
            q.pop();

            const bool odd = u < 0;
            if (u < 0) u = ~u;

            for (const auto& v : adj[u])
                if (odd && dist[v].first == INF) {
                    dist[v].first = dist[u].second + 1;
                    q.emplace(v);
                } else if (!odd && dist[v].second == INF) {
                    dist[v].second = dist[u].first + 1;
                    q.emplace(~v);
                }
        }
    };

    vector<bool> ans(k);
    for (int i = 0; i < n; ++i) {
        if (query[i].empty()) continue;
        bfs(i);
        for (const auto& [v, d, id] : query[i])
            if (d & 1)
                ans[id] = dist[v].second <= d;
            else
                ans[id] = dist[v].first ? dist[v].first <= d : !adj[v].empty();
    }

    for (const auto x : ans)
        cout << (x ? "TAK\n" : "NIE\n");
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 338 ms 36744 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 323 ms 36728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 15 ms 404 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 700 KB Output is correct
2 Correct 8 ms 728 KB Output is correct
3 Correct 51 ms 736 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1076 KB Output is correct
2 Correct 9 ms 588 KB Output is correct
3 Correct 287 ms 872 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 23056 KB Output is correct
2 Correct 13 ms 588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 24896 KB Output is correct
2 Correct 83 ms 5572 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 18260 KB Output is correct
2 Correct 182 ms 7620 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 18360 KB Output is correct
2 Correct 405 ms 17972 KB Output is correct