# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
706776 | 2023-03-07T17:10:29 Z | aedmhsn | Tales of seafaring (POI13_mor) | C++17 | 1815 ms | 39692 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(){ 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 && adj[v[i].A.A].size() != 0 ? 1:0); } for(int i=0; i<k; i++) cout << (ans[i] == 1 ? "TAK":"NIE") << '\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 424 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 884 ms | 39692 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 428 KB | Output is correct |
4 | Correct | 889 ms | 39440 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 2 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 468 KB | Output is correct |
2 | Correct | 3 ms | 468 KB | Output is correct |
3 | Correct | 16 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 952 KB | Output is correct |
2 | Correct | 13 ms | 852 KB | Output is correct |
3 | Correct | 57 ms | 980 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 103 ms | 1260 KB | Output is correct |
2 | Correct | 9 ms | 724 KB | Output is correct |
3 | Correct | 289 ms | 1072 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1163 ms | 24476 KB | Output is correct |
2 | Correct | 13 ms | 676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1815 ms | 24604 KB | Output is correct |
2 | Correct | 172 ms | 5508 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1030 ms | 24416 KB | Output is correct |
2 | Correct | 312 ms | 9208 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1073 ms | 24376 KB | Output is correct |
2 | Correct | 737 ms | 18444 KB | Output is correct |