#include <bits/stdc++.h>
using namespace std;
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a))
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int mxN=5e3+5;
vector <vector<int>> adj(mxN);
int dp[mxN][2];
void bfs(int node){
queue <int> q;
q.push(node);
dp[node][0]=0;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto x:adj[u]){
if(dp[u][0]+1 < dp[x][1]){
dp[x][1] = dp[u][0]+1;
q.push(x);
}
}
for(auto x:adj[u]){
if(dp[u][1]+1 < dp[x][0]){
dp[x][0] = dp[u][1]+1;
q.push(x);
}
}
}
}
int main(){
int n, m, k;
cin >> n >> m >> k;
for(int i=0; i<m; i++){
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector <pair<pii, pii>> v;
for(int i=0; i<k; i++){
int x, y, d;
cin >> x >> y >> d;
v.push_back({{x, y}, {d, i}});
}
sort(v.begin(), v.end());
vector <int> ans(k);
int cur=-1;
for(int i=0; i<v.size(); i++){
if(v[i].A.A != cur){
ms(dp, INF);
cur=v[i].A.A;
bfs(cur);
}
ans[v[i].B.B] = (dp[v[i].A.B][(v[i].B.A % 2)] <= v[i].B.A ? 1:0);
}
for(int i=0; i<k; i++)
cout << (ans[i] == 1 ? "TAK":"NIE") << '\n';
}
Compilation message
mor.cpp: In function 'int main()':
mor.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<v.size(); i++){
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
464 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
17 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
852 KB |
Output is correct |
2 |
Correct |
12 ms |
724 KB |
Output is correct |
3 |
Incorrect |
58 ms |
852 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
102 ms |
1112 KB |
Output is correct |
2 |
Correct |
9 ms |
724 KB |
Output is correct |
3 |
Incorrect |
278 ms |
992 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1109 ms |
24240 KB |
Output is correct |
2 |
Correct |
13 ms |
688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1768 ms |
24084 KB |
Output is correct |
2 |
Correct |
167 ms |
7648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1002 ms |
24240 KB |
Output is correct |
2 |
Correct |
308 ms |
12448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1053 ms |
24284 KB |
Output is correct |
2 |
Correct |
829 ms |
29392 KB |
Output is correct |