Submission #1019186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019186		Tri_Pahm	Birmingham (COCI20_birmingham)	C++14	70 / 70	78 ms	36568 KiB

birmingham

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define X first
#define Y second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define file "BMH"

using namespace std;

const int N=1e6+5;
const int NN=1e3+9;
const int MOD=1e9+7;
const ll INF=1e18;
const ld eps=1e-6;
const ld pi=acos(-1); // 48 digits

int n, m, Q, k;
queue<int> q;
vector<int> g[N];
bool dd[N], ddd[N];
ll b[N];
int d[N], day[N];

void inp() {
    cin>>n>>m>>Q>>k;
    for (int i=1;i<=Q;i++) {
        int x;
        cin>>x;
        q.push(x);
        dd[x]=1;
        ddd[x]=1;
    }
    for (int i=1;i<=m;i++) {
        int x, y;
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
}

void bfs() {
    int tam=1;
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        for (int v : g[u])
            if (!dd[v]){
                q.push(v);
                dd[v]=1;
//                cout<<v<<" "<<tam<<endl;
                d[v]=d[u]+1;

            }
    }
}

void process() {
    bfs();
    for (int i=1;i<=446;i++)
        b[i]=b[i-1]+i*k;
    for (int i=1;i<=n;i++) {
        int pos=lower_bound(b+1,b+447,d[i])-b;
//        cout<<d[i]<<endl;
        day[i]=pos;
        if (ddd[i]) day[i]=0;
    }
    for (int i=1;i<=n;i++)
        cout<<day[i]<<" ";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
//    cin>>t;
    while (t--) {
        inp();
        process();
    }
    return 0;
}
/*
6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

6 8 2 1
6 4
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

6 8 1 2
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
*/

Compilation message (stderr)

birmingham.cpp: In function 'void bfs()':
birmingham.cpp:45:9: warning: unused variable 'tam' [-Wunused-variable]
   45 |     int tam=1;
      |         ^~~

• 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