Submission #1272251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272251		flaming_top1	Birmingham (COCI20_birmingham)	C++20	70 / 70	61 ms	9172 KiB

birmingham

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

int n, m, q, k;
int a[100005];
lint dist[100005], power[100005];
vector<int> adj[100005];

void bfs()
{
    memset(dist, 0x1f, sizeof dist);
    queue<int> temp;
    for (int i = 1; i <= q; i++)
    {
        temp.emplace(a[i]);
        dist[a[i]] = 0;
    }
    while (!temp.empty())
    {
        auto now = temp.front();
        temp.pop();
        for (auto i : adj[now])
            if (dist[i] > dist[now] + 1)
            {
                dist[i] = dist[now] + 1;
                temp.emplace(i);
            }
    }
}

lint binaryu(lint x)
{
    int l = 1, r = n, mid, ans = 0;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (power[mid] >= x)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}

fami lore()
{
    SPED;
    cin >> n >> m >> q >> k;
    for (int i = 1; i <= q; i++)
        cin >> a[i];

    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        adj[l].emplace_back(r);
        adj[r].emplace_back(l);
    }

    bfs();

    for (lint i = 1; i <= n; i++)
    {
        power[i] = i * k;
        power[i] += power[i - 1];
    }

    for (int i = 1; i <= n; i++)
    {
        if (dist[i] == 0)
            cout << 0 << " ";
        else
        {
            cout << binaryu(dist[i]) << " ";
        }
    }
}
// Let your soul wander where dreams are born.

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5