Submission #570054

#TimeUsernameProblemLanguageResultExecution timeMemory
570054angelo_torresBirmingham (COCI20_birmingham)C++17
70 / 70
219 ms14712 KiB
#include <bits/stdc++.h> #define f(i,j,n) for(ll i = j; i < n; ++i) #define sz(s) (ll) (s.size()) using namespace std; typedef long long ll; typedef vector<ll> vll; const int N = 1e5 + 20; const ll mod = 1e9 + 7; ll n,m,q,k,dis[N],vis[N]; vll ih,adj[N]; void multi_bfs(){ f(i,1,n+1) dis[i] = (n<<1), vis[i] = 0; queue<ll> qe; for(auto it : ih){ dis[it] = 0; qe.push(it); } while(!qe.empty()){ ll v = qe.front(); qe.pop(); if(vis[v]) continue; vis[v] = 1; for(auto u : adj[v]){ dis[u] = min(dis[u],dis[v]+1); if(vis[u]) continue; qe.push(u); } } } int main(){ cin >> n >> m >> q >> k; ih.resize(q); f(i,0,q) cin >> ih[i]; f(i,0,m){ ll u,v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } multi_bfs(); f(i,1,n+1){ if(dis[i] == 0){ cout << 0 << " "; continue; } ll gr = (dis[i]+k-1)/k; ll tr = (ll) sqrt(8*gr+1); if(tr*tr != 8*gr+1) tr++; cout << (tr>>1) << " "; } cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...