Submission #1135888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135888		MateiKing80	Tales of seafaring (POI13_mor)	C++20	100 / 100	1250 ms	102752 KiB

mor

#include <bits/stdc++.h>

using namespace std;


const short INF = 1e9;

int N, M, K;
vector<int> adj[5005];

short dist[5005][5005][2];

void bfs(int p)
{
    queue<pair<int, int>> q;
    dist[p][p][0] = 0;
    q.push(make_pair(p, 0));
    while(!q.empty())
    {
        int cn = q.front().first;
        int cd = q.front().second;
        q.pop();
        for(int i = 0; i < adj[cn].size(); i ++)
        {
            int nn = adj[cn][i];
            if(dist[p][nn][(cd + 1) % 2] > cd + 1)
            {
                dist[p][nn][(cd + 1) % 2] = cd + 1;
                q.push(make_pair(nn, cd + 1));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0; i < 5005; i ++)
    {
        for(int j = 0; j < 5005; j ++)
        {
            if(i != j)
                dist[i][j][0] = INF;
            dist[i][j][1] = INF;
        }
    }
    cin >> N >> M >> K;
    int u, v;
    for(int i = 0; i < M; i ++)
    {
        cin >> u >> v;
        u --;
        v --;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 0; i < N; i ++)
        bfs(i);
    int a, b, d;
    for(int i = 0; i < K; i ++)
    {
        cin >> a >> b >> d;
        a --;
        b --;
        if((dist[a][b][d % 2] != INF && dist[a][b][d % 2] <= d) && !(d > 0 && adj[a].size() == 0) )
            cout << "TAK" << '\n';
        else
            cout << "NIE" << '\n';
    }
}

Compilation message (stderr)

mor.cpp:6:19: warning: overflow in conversion from 'double' to 'short int' changes value from '1.0e+9' to '32767' [-Woverflow]
    6 | const short INF = 1e9;
      |                   ^~~

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