# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244549 | 2020-07-04T09:32:09 Z | arnold518 | Price List (POI13_cen) | C++14 | 160 ms | 14168 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; const ll INF = 1e15; int N, M, K, A, B; pii E[MAXN+10]; vector<int> adj[MAXN/2+10], adj2[MAXN/2+10]; ll dist1[MAXN+10], dist2[MAXN+10]; bool vis1[MAXN+10], vis2[MAXN+10]; struct Queue { int v, w; }; bool f(int u, int v) { return binary_search(adj2[u].begin(), adj2[u].end(), v); } int main() { int i, j; scanf("%d%d%d%d%d", &N, &M, &K, &A, &B); for(i=1; i<=M; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); adj2[u].push_back(v); adj2[v].push_back(u); } for(i=1; i<=N; i++) sort(adj2[i].begin(), adj2[i].end()); for(i=1; i<=N; i++) dist1[i]=dist2[i]=INF; queue<Queue> Q; Q.push({K, 0}); vis1[K]=1; dist1[K]=0; while(!Q.empty()) { Queue now=Q.front(); Q.pop(); for(auto nxt : adj[now.v]) { if(vis1[nxt]) continue; dist1[nxt]=now.w+1; vis1[nxt]=true; Q.push({nxt, now.w+1}); } } Q.push({K, 0}); vis2[K]=1; dist2[K]=0; while(!Q.empty()) { Queue now=Q.front(); Q.pop(); for(auto nxt : adj[now.v]) { for(auto &nxt2 : adj[nxt]) { if(vis2[nxt2]) { nxt2=-1; continue; } if(f(now.v, nxt2)) continue; Q.push({nxt2, now.w+1}); dist2[nxt2]=now.w+1; vis2[nxt2]=true; } vector<int> V; for(auto it : adj[nxt]) if(it!=-1) V.push_back(it); swap(adj[nxt], V); } } for(i=1; i<=N; i++) { if(dist1[i]%2==0) printf("%lld\n", min(dist1[i]*A, dist1[i]/2*B)); else printf("%lld\n", min({dist1[i]*A, dist1[i]/2*B+A, dist2[i]*B})); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 7 ms | 4992 KB | Output is correct |
4 | Incorrect | 7 ms | 4992 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Incorrect | 7 ms | 4992 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 5120 KB | Output is correct |
2 | Correct | 8 ms | 5120 KB | Output is correct |
3 | Correct | 8 ms | 5120 KB | Output is correct |
4 | Correct | 9 ms | 5120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 6144 KB | Output is correct |
2 | Correct | 18 ms | 6144 KB | Output is correct |
3 | Incorrect | 21 ms | 6144 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 42 ms | 8852 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 73 ms | 11608 KB | Output is correct |
2 | Correct | 74 ms | 10748 KB | Output is correct |
3 | Correct | 129 ms | 11424 KB | Output is correct |
4 | Correct | 111 ms | 11132 KB | Output is correct |
5 | Correct | 88 ms | 12016 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 95 ms | 12848 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 111 ms | 14168 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 110 ms | 13496 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 13816 KB | Output is correct |
2 | Correct | 122 ms | 13816 KB | Output is correct |
3 | Incorrect | 160 ms | 13816 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |