Submission #595771

#TimeUsernameProblemLanguageResultExecution timeMemory
595771nguyen31hoang08minh2003Birmingham (COCI20_birmingham)C++14
70 / 70
116 ms10228 KiB
/* /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \ \ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \ \ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \ \ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ / \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ */ #include <bits/stdc++.h> #define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i) #define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i) #define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i) #define fi first #define se second #define pb push_back #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;}; template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;}; typedef unsigned long long ull; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; const int maxN = 1e5 + 5, inf = 0x3f3f3f3f; int n, m, k, q, d[maxN]; queue<int> r; vi adj[maxN]; int main() { #ifdef LOCAL freopen("input.INP", "r", stdin); #endif // LOCAL cin.tie(0) -> sync_with_stdio(0); cout.tie(0); cin >> n >> m >> q >> k; memset(d, inf, sizeof(d)); for (int i = 1, x; i <= q; ++i) { cin >> x; d[x] = 0; r.push(x); } for (int i = 1, x, y; i <= m; ++i) { cin >> x >> y; adj[x].pb(y); adj[y].pb(x); } for (; !r.empty(); r.pop()) { const int &u = r.front(); for (const int &v : adj[u]) if (mini(d[v], d[u] + 1)) r.push(v); } for (int i = 1, lo, hi, mid; i <= n; ++i) { lo = -1; hi = n + 1; while (lo + 1 < hi) { mid = lo + hi >> 1; if (k * (mid * (mid + 1LL) >> 1) >= d[i]) hi = mid; else lo = mid; } cout << hi << ' '; } cout << '\n'; return 0; }

Compilation message (stderr)

birmingham.cpp: In function 'int main()':
birmingham.cpp:77:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |             mid = lo + hi >> 1;
      |                   ~~~^~~~
#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...