# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
706770 | 2023-03-07T17:00:58 Z | aedmhsn | Tales of seafaring (POI13_mor) | C++17 | 891 ms | 39328 KB |
#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(){ ms(dp, INF); 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=v[0].A.A; for(int i=0; i<v.size(); i++){ if(v[i].A.A != cur){ 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 516 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 852 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 1284 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 891 ms | 38032 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 839 ms | 37548 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 861 ms | 39328 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 856 ms | 39196 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |