oj.uz

Submission #584202

# Submission time Handle Problem Language Result Execution time Memory
584202 2022-06-27T03:18:24 Z AGE Birmingham (COCI20_birmingham) C++14
70 / 70
 209 ms 42340 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;
int a[12]={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
vector<int>adj[N];
int dist[N],ans[N];
main()
{
    queue<int>qq;
    int n,m,q,k;
    cin>>n>>m>>q>>k;

    vector<int>v;
    for(int i=0;i<q;i++){
        int x;
        cin>>x;

        v.pb(x);

    }

    for(int i=0;i<m;i++){

        int x,y;
        cin>>x>>y;

        adj[x].pb(y);
        adj[y].pb(x);

    }
    for(int i=1;i<=n;i++)
        dist[i]=1e18;


    for(int i=0;i<v.size();i++)
        qq.push(v[i]),dist[v[i]]=0;

    while(!qq.empty()){

        int node=qq.front();
        qq.pop();

        for(auto x:adj[node]){

            if(dist[x]>dist[node]+1){

                dist[x]=dist[node]+1;
                qq.push(x);

            }
        }
    }

    ans[0]=0;
    int i=0;
    int step=1;

    while(i<=1e6){


        int target=i+(k*step);
        if(target>1e6)
            break;

        int lst=i;

        i++;
        while(i<=target)
            ans[i]=ans[lst]+1,i++;

        i=target;
        step++;

    }

    for(int i=1;i<=n;i++)
        cout<<ans[dist[i]]<<" ";
    cout<<endl;

    return 0;
}

Compilation message

birmingham.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main()
      | ^~~~
birmingham.cpp: In function 'int main()':
birmingham.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31544 KB Output is correct
2 Correct 15 ms 31564 KB Output is correct
3 Correct 14 ms 31600 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 14 ms 31580 KB Output is correct
3 Correct 17 ms 31572 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 16 ms 31600 KB Output is correct
3 Correct 16 ms 31612 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31560 KB Output is correct
2 Correct 15 ms 31600 KB Output is correct
3 Correct 18 ms 31564 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31556 KB Output is correct
2 Correct 16 ms 31576 KB Output is correct
3 Correct 15 ms 31540 KB Output is correct
4 Correct 17 ms 31592 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31536 KB Output is correct
2 Correct 15 ms 31548 KB Output is correct
3 Correct 17 ms 31480 KB Output is correct
4 Correct 17 ms 31536 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31592 KB Output is correct
2 Correct 15 ms 31520 KB Output is correct
3 Correct 15 ms 31580 KB Output is correct
4 Correct 16 ms 31572 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 38648 KB Output is correct
2 Correct 152 ms 41356 KB Output is correct
3 Correct 209 ms 42120 KB Output is correct
4 Correct 158 ms 39808 KB Output is correct
5 Correct 146 ms 38420 KB Output is correct
6 Correct 174 ms 42340 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 39124 KB Output is correct
2 Correct 149 ms 41056 KB Output is correct
3 Correct 168 ms 41776 KB Output is correct
4 Correct 168 ms 41460 KB Output is correct
5 Correct 148 ms 39416 KB Output is correct
6 Correct 149 ms 41264 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 38752 KB Output is correct
2 Correct 154 ms 41492 KB Output is correct
3 Correct 173 ms 42024 KB Output is correct
4 Correct 178 ms 41484 KB Output is correct
5 Correct 138 ms 38640 KB Output is correct
6 Correct 147 ms 41324 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 38380 KB Output is correct
2 Correct 154 ms 41072 KB Output is correct
3 Correct 179 ms 41664 KB Output is correct
4 Correct 139 ms 40644 KB Output is correct
5 Correct 135 ms 40008 KB Output is correct
6 Correct 151 ms 41196 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 38348 KB Output is correct
2 Correct 145 ms 40692 KB Output is correct
3 Correct 160 ms 40796 KB Output is correct
4 Correct 139 ms 40396 KB Output is correct
5 Correct 146 ms 39980 KB Output is correct
6 Correct 145 ms 41132 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 38440 KB Output is correct
2 Correct 149 ms 40836 KB Output is correct
3 Correct 156 ms 40840 KB Output is correct
4 Correct 149 ms 41036 KB Output is correct
5 Correct 137 ms 37896 KB Output is correct
6 Correct 153 ms 41436 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 38628 KB Output is correct
2 Correct 136 ms 40012 KB Output is correct
3 Correct 167 ms 41980 KB Output is correct
4 Correct 143 ms 40380 KB Output is correct
5 Correct 160 ms 39944 KB Output is correct
6 Correct 171 ms 42200 KB Output is correct