oj.uz

Submission #1111489

# Submission time Handle Problem Language Result Execution time Memory
1111489 2024-11-12T08:53:25 Z Informatics271 Drivers (BOI24_drivers) C++17
0 / 100
 83 ms 8784 KB 
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

int N;
int M;
int U;

int X[200005];
int Y[200005];
int T[200005];
int D[200005];

int A[200005];
int B[200005];
int P[200005];

vector<pair<int, int>> E[200005];

int main(){
	cin >> N >> M >> U;
	for (int i=0;i<M;i++) cin>>X[i]>>Y[i]>>T[i];
	for (int i=0;i<U;i++) cin>>A[i]>>B[i]>>P[i];
	for (int i=0;i<M;i++){
		E[X[i]].push_back({T[i], Y[i]});
		E[Y[i]].push_back({T[i], X[i]});
	}
	
	for (int i=0;i<U;i++){
		fill_n(D, N+5, 1<<30);
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq{};
		pq.push({0, A[i]});
		while (pq.size()){
			int t=pq.top().first;
			int a=pq.top().second;
			pq.pop();
			//cout << t << a << '\n';
			if (D[a]<=t) continue;
			D[a]=t;
			for (int i=0; i<E[a].size(); i++) pq.push({max(t,E[a][i].first),E[a][i].second});
		}
		if (D[B[i]]<(1<<30)&&D[B[i]]<P[i]) cout << "TAIP\n";
		else cout << "NE\n";
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for (int i=0; i<E[a].size(); i++) pq.push({max(t,E[a][i].first),E[a][i].second});
      |                  ~^~~~~~~~~~~~

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Incorrect 83 ms 8784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Incorrect 20 ms 8784 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Incorrect 83 ms 8784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Incorrect 83 ms 8784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Incorrect 83 ms 8784 KB Output isn't correct
3 Halted 0 ms 0 KB -