oj.uz

Submission #980083

# Submission time Handle Problem Language Result Execution time Memory
980083 2024-05-11T22:25:18 Z MarwenElarbi Tales of seafaring (POI13_mor) C++17
40 / 100
 3000 ms 131072 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1708 ms 19876 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1768 ms 19816 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 2908 KB Output is correct
2 Correct 31 ms 1112 KB Output is correct
3 Correct 579 ms 4188 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 6232 KB Output is correct
2 Execution timed out 3018 ms 10472 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 35676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 63400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -