Submission #1234419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234419		erering	Tales of seafaring (POI13_mor)	C++20	30 / 100	1189 ms	102720 KiB

mor

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
//#define int long long
const int N=5000+5,inf=32766,MOD=1e9+7;
vector<int> adj[N];
short dist[N][N][2];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dist[i][j][0]=inf;
            dist[i][j][1]=inf;
        }
    }
    int n,m,q; cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int x,y; cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1;i<=n;i++){
        dist[i][i][0]=0;
        queue<pair<int,int>> bfs;
        bfs.push({i,0});
        while(!bfs.empty()){
            int node=bfs.front().first,type=bfs.front().second;
            bfs.pop();
            type++;
            for(auto j:adj[node]){
                if(dist[i][j][type%2]==inf){
                    bfs.push({j,type});
                    dist[i][j][type%2]=type;
                }
            }
        }
    }
    while(q--){
        int x,y,d; cin>>x>>y>>d;
        if(x==y && d%2==0 && adj[x].empty()){
            cout<<"NIE"<<endl;
            continue;
        }
        if(dist[x][y][d%2]<=d)cout<<"TAK"<<endl;
        else cout<<"NIE"<<endl;
    }
}

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