Submission #238617

#	Time	Username	Problem	Language	Result	Execution time	Memory
238617		SamAnd	Birmingham (COCI20_birmingham)	C++17	70 / 70	153 ms	10748 KiB

birmingham

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005;

int n, m, q, k;
vector<int> g[N];

int ans[N];

bool c[N];
int dist[N];

void solv()
{
    scanf("%d%d%d%d", &n, &m, &q, &k);
    for (int i = 1; i <= n; ++i)
        ans[i] = -1;
    while (q--)
    {
        int x;
        scanf("%d", &x);
        ans[x] = 0;
    }
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int d = 1; ; ++d)
    {
        bool z = true;
        for (int i = 1; i <= n; ++i)
        {
            if (ans[i] == -1)
            {
                z = false;
                break;
            }
        }
        if (z)
            break;
        queue<int> q;
        for (int i = 1; i <= n; ++i)
        {
            c[i] = false;
            if (ans[i] != -1)
            {
                c[i] = true;
                dist[i] = 0;
                q.push(i);
            }
        }
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            if (dist[x] > d * k)
                continue;
            if (ans[x] == -1)
                ans[x] = d;
            for (int i = 0; i < g[x].size(); ++i)
            {
                int h = g[x][i];
                if (!c[h])
                {
                    c[h] = true;
                    dist[h] = dist[x] + 1;
                    q.push(h);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    printf("\n");
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

birmingham.cpp: In function 'void solv()':
birmingham.cpp:71:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < g[x].size(); ++i)
                             ~~^~~~~~~~~~~~~
birmingham.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &q, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
birmingham.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
birmingham.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

• 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