Submission #980083

#	Time	Username	Problem	Language	Result	Execution time	Memory
980083		MarwenElarbi	Tales of seafaring (POI13_mor)	C++17	40 / 100	3082 ms	131072 KiB

mor

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<int> adj[n];
    ll odd[n][n];
    ll even[n][n];
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            odd[i][j]=even[i][j]=1e9;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        even[i][i]=0;
    }
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
        odd[x][y]=odd[y][x]=1;
    }
    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                odd[i][j]=min(odd[i][j],min(odd[i][k]+even[k][j],even[i][k]+odd[k][j]));
                even[i][j]=min(even[i][j],min(even[i][k]+even[k][j],odd[i][k]+odd[k][j]));
                odd[j][i]=min(odd[i][j],odd[j][i]);
                even[j][i]=min(even[i][j],even[j][i]);
            }
        }
    }
    while(q--){
        ll x,y,z;
        cin>>x>>y>>z;
        x--;y--;
        if(z%2==0&&z>=even[x][y]&&(adj[x].size()>0&&adj[y].size()>0)) cout <<"TAK"<<endl;
        else if(z%2&&z>=odd[x][y]) cout <<"TAK"<<endl;
        else cout <<"NIE"<<endl;
    }
}

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