oj.uz

Submission #238427

# Submission time Handle Problem Language Result Execution time Memory
238427 2020-06-11T07:59:51 Z MishoKostov Birmingham (COCI20_birmingham) C++14
70 / 70
 156 ms 11380 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 9 ms 5272 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5168 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9976 KB Output is correct
2 Correct 105 ms 10920 KB Output is correct
3 Correct 106 ms 11128 KB Output is correct
4 Correct 87 ms 10472 KB Output is correct
5 Correct 90 ms 10456 KB Output is correct
6 Correct 102 ms 11380 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10232 KB Output is correct
2 Correct 102 ms 10800 KB Output is correct
3 Correct 107 ms 11016 KB Output is correct
4 Correct 114 ms 11040 KB Output is correct
5 Correct 97 ms 10800 KB Output is correct
6 Correct 88 ms 10988 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 10060 KB Output is correct
2 Correct 106 ms 10916 KB Output is correct
3 Correct 102 ms 11128 KB Output is correct
4 Correct 107 ms 11000 KB Output is correct
5 Correct 94 ms 10700 KB Output is correct
6 Correct 89 ms 10992 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 9820 KB Output is correct
2 Correct 156 ms 10812 KB Output is correct
3 Correct 138 ms 11000 KB Output is correct
4 Correct 104 ms 10616 KB Output is correct
5 Correct 89 ms 10584 KB Output is correct
6 Correct 109 ms 10868 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 9816 KB Output is correct
2 Correct 95 ms 10048 KB Output is correct
3 Correct 94 ms 10744 KB Output is correct
4 Correct 91 ms 10572 KB Output is correct
5 Correct 88 ms 10688 KB Output is correct
6 Correct 91 ms 10996 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9852 KB Output is correct
2 Correct 152 ms 10688 KB Output is correct
3 Correct 108 ms 10744 KB Output is correct
4 Correct 140 ms 10872 KB Output is correct
5 Correct 90 ms 10576 KB Output is correct
6 Correct 92 ms 10996 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 9932 KB Output is correct
2 Correct 113 ms 10464 KB Output is correct
3 Correct 105 ms 11068 KB Output is correct
4 Correct 100 ms 10572 KB Output is correct
5 Correct 96 ms 10684 KB Output is correct
6 Correct 110 ms 11248 KB Output is correct