Submission #845118

#	Time	Username	Problem	Language	Result	Execution time	Memory
845118		vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	233 ms	8828 KiB

birmingham

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define pb push_back
#define CDIV(a,b) (((a)+(b)-(1))/(b))

 
int mod_(int a, int b)
{
    if(a >= 0)return a % b;
    a += (-a/b + 1) * b;
    return a % b;
}

int k;
ll c(ll x)
{
    return k * x * (x + 1) / 2;
}

ll calc(ll x)
{
    int l = 1, r = 10;
    while(l <= r)
    {
        int m = (l + r)/2;
        if(c(m) >= x)r = m - 1;
        else l = m + 1;
    }
    return l;

}

void solve()
{
    int n, m, f;
    cin >> n >> m >> f >> k;
    vector<int> g[n + 1];
    vector<int>dist(n + 1, INT32_MAX);
    queue<array<int, 2> >q;
    vector<bool>vis(n + 1);

    while(f--)
    {
        int u;
        cin >> u;
        q.push({u, 0});
    }

    for(int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    while(!q.empty())
    {
        int node = q.front()[0], d = q.front()[1];
        //cerr << node << endl;
        q.pop();
        dist[node] = min(d, dist[node]);
        if(vis[node])continue;
        vis[node] = true;

        for(int next : g[node])
        {
            if(!vis[next])
                q.push({next, d + 1});
        }
    }

    for(int i = 1; i <= n; ++i)
    {
        if(dist[i])
        {
            //cout << i << ' ' << dist[i] << ' ';
            cout <<  calc(dist[i]) << endl;
        }
        else cout << 0 << endl;
    }

}
    

int main()
{
    //fio;
    //int t; cin >> t; while(t--)
    {
        solve();
    }
}

• 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