# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
36225 | 2017-12-06T11:38:11 Z | WhipppedCream | Price List (POI13_cen) | C++14 | 126 ms | 9380 KB |
#include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vvi vector< vi > #define vii vector< ii > #define mp make_pair #define pb push_back const int maxn = 1e5+5; int n, m, k, a, b; vector<int> adj[maxn]; int odd[maxn]; int eve[maxn]; int dist[maxn]; int p[maxn]; ll cost(int x) { if(x%2) return a+min(1LL*b*(x/2), 1LL*a*(x-1)); return min(1LL*b*x/2, 1LL*a*x); } int main() { //#ifndef atom //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); //#endif scanf("%d %d %d %d %d", &n, &m, &k, &a, &b); for(int i = 1; i<= n; i++) dist[i] = odd[i] = eve[i] = 1e9; for(int i = 1; i<= m; i++) { int a, b; scanf("%d %d", &a, &b); adj[a].pb(b); adj[b].pb(a); } eve[k] = dist[k] = 0; queue<ii> Q; Q.push(ii(k, 0)); while(!Q.empty()) { int u = Q.front().X; Q.pop(); for(auto v : adj[u]) { if(dist[v]> dist[u]+1) { dist[v] = dist[u]+1; p[v] = u; Q.push(ii(v, 0)); } } } Q.push(ii(k, 0)); while(!Q.empty()) { int u = Q.front().X; int par = Q.front().Y; Q.pop(); for(auto v : adj[u]) { if(p[v] == p[u]) continue; if(par) { if(eve[v]> odd[u]+1) { eve[v] = odd[u]+1; Q.push(ii(v, 0)); } } else { if(odd[v]> eve[u]+1) { odd[v] = eve[u]+1; Q.push(ii(v, 1)); } } } } //for(int i = 1; i<= n; i++) printf("%d %d [%d] {%d}\n", odd[i], eve[i], dist[i], p[i]); for(int i = 1; i<= n; i++) { if(odd[i] != 1) printf("%lld\n", min(cost(odd[i]), cost(eve[i]))); else printf("%lld\n", cost(odd[i])); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5924 KB | Output is correct |
2 | Correct | 0 ms | 5924 KB | Output is correct |
3 | Correct | 0 ms | 5924 KB | Output is correct |
4 | Incorrect | 0 ms | 5924 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5924 KB | Output is correct |
2 | Correct | 0 ms | 5924 KB | Output is correct |
3 | Incorrect | 0 ms | 5924 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5924 KB | Output is correct |
2 | Correct | 0 ms | 5924 KB | Output is correct |
3 | Incorrect | 0 ms | 5924 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 6324 KB | Output is correct |
2 | Correct | 9 ms | 6324 KB | Output is correct |
3 | Correct | 9 ms | 6320 KB | Output is correct |
4 | Correct | 9 ms | 6320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 7508 KB | Output is correct |
2 | Correct | 36 ms | 7508 KB | Output is correct |
3 | Incorrect | 29 ms | 6848 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 8472 KB | Output is correct |
2 | Correct | 79 ms | 8076 KB | Output is correct |
3 | Incorrect | 93 ms | 8168 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 8888 KB | Output is correct |
2 | Correct | 59 ms | 8056 KB | Output is correct |
3 | Incorrect | 99 ms | 8300 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 99 ms | 9380 KB | Output is correct |
2 | Correct | 86 ms | 8852 KB | Output is correct |
3 | Incorrect | 86 ms | 8564 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 96 ms | 8976 KB | Output is correct |
2 | Correct | 69 ms | 8976 KB | Output is correct |
3 | Incorrect | 123 ms | 8564 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 126 ms | 9092 KB | Output is correct |
2 | Correct | 103 ms | 8960 KB | Output is correct |
3 | Incorrect | 119 ms | 9092 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |