# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
693987 | Gital | Birmingham (COCI20_birmingham) | C++11 | 107 ms | 10456 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define endl '\n';
typedef long long ll;
int N,M,Q,K;
int dp[100005];
vector<int> v[100005];
priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > pq;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> Q >> K;
for(int i = 0; i < 100005; i++) {
dp[i] = INT_MAX;
}
for(int i = 0; i < Q; i++) {
int x; cin >> x;
dp[x] = 0;
pq.push({0,x});
}
for(int i = 0; i < M; i++) {
int a,b; cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
while(!pq.empty()) {
int a = pq.top().first + 1;
int b = pq.top().second;
int x = 1;
int k = K;
while(a > k) {
x++;
k += x * K;
}
pq.pop();
for(int i = 0; i < v[b].size(); i++) {
if(dp[v[b][i]] > x) {
dp[v[b][i]] = x;
pq.push({a,v[b][i]});
}
}
}
for(int i = 1; i <= N; i++) {
cout << dp[i] << " ";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |