Submission #1134093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134093		alexdd	Tales of seafaring (POI13_mor)	C++20	100 / 100	1584 ms	50804 KiB

mor

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int dima=1000008;
const int maxN=5003;
vector <vector <int>> adj(maxN);
//map <int, vector <pair <int, int>>> qry;
vector<pair<pair<int,int>,int>> qrys[maxN];
int n, m, q;
int ans[dima];

int dist[maxN][3];
#define inf 100000000000000

void bfs(int st)
{
    for (int i=1; i<=n; i++) {dist[i][0]=inf; dist[i][1]=inf;}

    queue <pair <int, int>> q; dist[st][0]=0; q.push({st, 0});
    while (!q.empty())
    {
        int node=q.front().first; int stare=q.front().second;
        q.pop();

        for (auto aux:adj[node])
        {
            if (dist[aux][1-stare]!=inf) continue;

            dist[aux][1-stare]=dist[node][stare]+1;
            q.push({aux, 1-stare});
        }
    }
}

signed main()
{
    cin>>n>>m>>q;
    for (int i=1; i<=m; i++)
    {
        int a, b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i=1; i<=q; i++)
    {
        int a, b, c; cin>>a>>b>>c;
        qrys[a].push_back({{b, c}, i});
    }

    for(int i=1;i<=n;i++)
    {
        bfs(i);
        for(auto q:qrys[i])
        {
            int t=q.first.first; int d=q.first.second; int id=q.second;

            if (dist[t][d%2]<=d) ans[id]=1;
            if (i==t && d>0 && adj[i].empty()) ans[id]=0;
        }
    }

    for (int i=1; i<=q; i++) cout<<(ans[i] ? "TAK" : "NIE")<<"\n";
    return 0;
}

• 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