Submission #238427

#	Time	Username	Problem	Language	Result	Execution time	Memory
238427		MishoKostov	Birmingham (COCI20_birmingham)	C++14	70 / 70	156 ms	11380 KiB

birmingham

#include<bits/stdc++.h>
#define endl "\n"

using namespace std;

struct edge
{
    int x, time;
    edge() { }
    edge(int x, int time) :x(x), time(time) { }
};

const int nmax=200010;
int n, m, qr, k;
vector<int> g;
vector<int> v[nmax];
int ans[nmax];
int dp[nmax];

void bfs()
{
    bool used[nmax];
    memset(used, 0, sizeof(used));
    queue<edge> q;
    for(int i=0; i<qr; ++i) q.push(edge(g[i], 0)), used[g[i]]=true;
    while(!q.empty())
    {
        edge w=q.front();
        q.pop();
        //used[w.x]=true;
        ans[w.x]=w.time;
        for(int i=0; i<v[w.x].size(); ++i)
        {
            int nb=v[w.x][i];
            if(!used[nb]) q.push(edge(nb, w.time+1)), used[nb]=true;
        }
    }
}

int bin_search(int x, int l, int r)
{
    int ann=100000000;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(dp[mid]>=x) ann=mid, r=mid-1;
        else l=mid+1;
    }
    return ann;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int x, y;
	cin>>n>>m>>qr>>k;
	for(int i=0; i<qr; ++i) cin>>x, g.push_back(x);
	for(int i=0; i<m; ++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs();
    dp[0]=0;
    int e=1;
    while(dp[e-1]<=m) dp[e]=dp[e-1]+k*e, e++;
    for(int i=1; i<=n; ++i) cout<<bin_search(ans[i], 0, e-1)<<" ";
    cout<<endl;
	return 0;
}

Compilation message (stderr)

birmingham.cpp: In function 'void bfs()':
birmingham.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v[w.x].size(); ++i)
                      ~^~~~~~~~~~~~~~

• 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