oj.uz

Submission #595771

# Submission time Handle Problem Language Result Execution time Memory
595771 2022-07-14T06:21:36 Z nguyen31hoang08minh2003 Birmingham (COCI20_birmingham) C++14
70 / 70
 116 ms 10228 KB 
/*
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
 /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \  /    \
/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \/      \
\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /\      /
 \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \    /
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \
\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /
 \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/  \/
*/
#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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3060 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3060 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3056 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3060 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3072 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3056 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3064 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 9432 KB Output is correct
2 Correct 78 ms 9872 KB Output is correct
3 Correct 110 ms 10196 KB Output is correct
4 Correct 59 ms 8908 KB Output is correct
5 Correct 63 ms 9016 KB Output is correct
6 Correct 113 ms 10228 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 9876 KB Output is correct
2 Correct 76 ms 9716 KB Output is correct
3 Correct 73 ms 9860 KB Output is correct
4 Correct 80 ms 9932 KB Output is correct
5 Correct 88 ms 9704 KB Output is correct
6 Correct 65 ms 9448 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 9396 KB Output is correct
2 Correct 116 ms 9912 KB Output is correct
3 Correct 96 ms 10192 KB Output is correct
4 Correct 98 ms 9916 KB Output is correct
5 Correct 78 ms 9176 KB Output is correct
6 Correct 86 ms 9564 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8988 KB Output is correct
2 Correct 72 ms 9664 KB Output is correct
3 Correct 87 ms 9984 KB Output is correct
4 Correct 87 ms 9332 KB Output is correct
5 Correct 74 ms 8936 KB Output is correct
6 Correct 67 ms 9420 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 8992 KB Output is correct
2 Correct 103 ms 9464 KB Output is correct
3 Correct 99 ms 9416 KB Output is correct
4 Correct 71 ms 9184 KB Output is correct
5 Correct 74 ms 9336 KB Output is correct
6 Correct 69 ms 9356 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 9124 KB Output is correct
2 Correct 73 ms 9380 KB Output is correct
3 Correct 64 ms 9368 KB Output is correct
4 Correct 102 ms 9628 KB Output is correct
5 Correct 102 ms 9264 KB Output is correct
6 Correct 66 ms 9548 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 9216 KB Output is correct
2 Correct 77 ms 8860 KB Output is correct
3 Correct 94 ms 10056 KB Output is correct
4 Correct 74 ms 9348 KB Output is correct
5 Correct 78 ms 9436 KB Output is correct
6 Correct 106 ms 10188 KB Output is correct