Submission #440521

#TimeUsernameProblemLanguageResultExecution timeMemory
440521mashrur_hossainBirmingham (COCI20_birmingham)C++14
70 / 70
128 ms12880 KiB
#include <bits/stdc++.h> #define fast_cin ios_base::sync_with_stdio(0); cin.tie(NULL); cerr.tie(NULL); #define endl "\n" #define dbg(x) cerr << #x << ": " << x << endl; #define DBG cerr << __LINE__ << ": I GOT STUCK\n"; using namespace std; typedef long long ll; typedef long double db; const ll mxn = 1e5 + 10; const ll INF = 1e8; ll n,m,Q,k; vector<ll>adj[mxn]; vector<ll>dist(mxn, INF); ll sum(ll x){ return x * (x + 1)/2; } bool good(ll x, ll d){ return (k * sum(x) >= d); } ll find(ll d){ ll l = 0, r = 1e5+10; ll ans = 0; while(l <= r){ ll mid = l + (r - l)/2; if(good(mid, d)){ ans = mid; r = mid - 1; } else l = mid + 1; } return ans; } void solve(){ cin >> n >> m >> Q >> k; queue<ll>q; for(ll i = 0;i<Q;i++){ ll x;cin >> x; q.push(x); dist[x] = 0; } for(ll i = 0;i<m;i++){ ll a, b;cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } while(!q.empty()){ ll node = q.front(); q.pop(); for(auto child: adj[node]){ if(dist[child] > dist[node] + 1){ dist[child] = dist[node] + 1; q.push(child); } } } for(ll i = 1;i<=n;i++){ cout << find(dist[i]) << " \n"[i == n]; } } // 6 8 1 1 // 6 // 1 3 // 1 5 // 1 6 // 2 5 // 2 6 // 3 4 // 3 5 // 5 6 int main() { fast_cin; int test;test = 1; // int test;cin >>test; while(test--){ solve(); } 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...