oj.uz

Submission #1114620

# Submission time Handle Problem Language Result Execution time Memory
1114620 2024-11-19T09:18:39 Z awwads Drivers (BOI24_drivers) C++14
0 / 100
 2000 ms 6876 KB 
#include <bits/stdc++.h>
using namespace std;
bool connected(int a, int b, vector<vector<int>>graph){
    queue<int> todoset;
    set<int> doneset;
    todoset.push(a);
    while(!todoset.empty()){
        int i=todoset.front();
        todoset.pop();
        doneset.insert(i);
        for(int j: graph[i]){
            if (j==b){
                return true;
            }
            else if (doneset.count(j)==0){
                todoset.push(j);
            }
        }
    }
    return false;
}
int main() {
    int N,M,U; cin>>N>>M>>U;
    int x[M], y[M], t[M];
    for(int i=0; i<M; i++){
        cin>>x[i]>>y[i]>>t[i];
    }
    int a[U], b[U], p[U];
    for (int i=0; i<U; i++){
        cin>>a[i]>>b[i]>>p[i];
    }
    for (int i=0; i<U; i++){
        vector<vector<int>>map;
        vector<int>empty;
        for (int j=0; j<=N; j++){
            map.push_back(empty);
        }
        for (int j=0; j<M; j++){
            if (t[j]<=p[i]){
                map[x[j]].push_back(y[j]);
                map[y[j]].push_back(x[j]);
            }
        }
        if(connected(a[i],b[i],map)){
            cout<<"TAIP\n";
        }
        else{
            cout<<"NE\n";
        }
    }
    return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 336 KB Output is correct
3 Correct 191 ms 1232 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2066 ms 6876 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 24 ms 336 KB Output is correct
5 Correct 14 ms 336 KB Output is correct
6 Correct 13 ms 336 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 87 ms 592 KB Output is correct
9 Correct 22 ms 672 KB Output is correct
10 Correct 221 ms 592 KB Output is correct
11 Correct 435 ms 776 KB Output is correct
12 Correct 382 ms 888 KB Output is correct
13 Correct 201 ms 1360 KB Output is correct
14 Correct 1308 ms 916 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 136 ms 640 KB Output is correct
19 Execution timed out 2077 ms 2764 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 336 KB Output is correct
3 Correct 191 ms 1232 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2066 ms 6876 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 336 KB Output is correct
3 Correct 191 ms 1232 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2066 ms 6876 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 336 KB Output is correct
3 Correct 191 ms 1232 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2066 ms 6876 KB Time limit exceeded
6 Halted 0 ms 0 KB -