oj.uz

Submission #341531

# Submission time Handle Problem Language Result Execution time Memory
341531 2020-12-29T23:06:41 Z A_D Birmingham (COCI20_birmingham) C++14
70 / 70
 225 ms 16876 KB 
/*
ID: antwand1
TASK: pprime
LANG: C++
*/
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define du long double
#define F first
#define S second
#define FOR(a,b) for(int a=1;a<=b;a++)
#define FORl(a,b) for(a=1;a<=b;a++)
#define FOR0(a,b) for(int a=1;a<b;a++)
#define FORl0(a,b) for(a=0;a<b;a++)
#define ii pair<int,int>
using namespace std;
const int N=2e5+1;
int vis[N];
int mp[N];
vector<int> vec;
vector<int> g[N];
deque<int> deq;
main()
{
    int n,m,q,k;
    cin>>n>>m>>q>>k;
    int sum=0,idx=k;
    for(idx=k;sum<=2e5;idx+=k){
        sum=sum+idx;
        if(sum>2e5)break;
        vec.push_back(sum);
    }
    idx=1;
    int j=0;
    while(j<vec.size()){
        while(idx<=vec[j]){
            mp[idx]=j+1;
            idx++;
        }
        j++;
    }
    for(int i=1;i<=n;i++)vis[i]=1e18;
    while(q--){
        int a;
        cin>>a;
        vis[a]=0;
        deq.push_back(a);
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    while(deq.empty()==0){
        int v=deq[0];
        deq.pop_front();
        for(auto x:g[v]){
            if(vis[x]>vis[v]+1){
                vis[x]=vis[v]+1;
                deq.push_back(x);
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<mp[vis[i]]<<" ";
    }
    cout<<endl;
}

Compilation message

birmingham.cpp:24:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main()
      |      ^
birmingham.cpp: In function 'int main()':
birmingham.cpp:36:12: 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]
   36 |     while(j<vec.size()){
      |           ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 4 ms 6636 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 5 ms 6784 KB Output is correct
3 Correct 5 ms 6636 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 5 ms 6636 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 4 ms 6636 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 5 ms 6636 KB Output is correct
4 Correct 4 ms 6636 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6616 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 5 ms 6636 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 15724 KB Output is correct
2 Correct 206 ms 16364 KB Output is correct
3 Correct 225 ms 16876 KB Output is correct
4 Correct 161 ms 14828 KB Output is correct
5 Correct 177 ms 14316 KB Output is correct
6 Correct 209 ms 16748 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 16392 KB Output is correct
2 Correct 199 ms 16108 KB Output is correct
3 Correct 202 ms 16364 KB Output is correct
4 Correct 224 ms 16620 KB Output is correct
5 Correct 195 ms 15980 KB Output is correct
6 Correct 189 ms 15724 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 15852 KB Output is correct
2 Correct 215 ms 16492 KB Output is correct
3 Correct 216 ms 16876 KB Output is correct
4 Correct 204 ms 16600 KB Output is correct
5 Correct 173 ms 15212 KB Output is correct
6 Correct 190 ms 15852 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 15192 KB Output is correct
2 Correct 192 ms 16108 KB Output is correct
3 Correct 213 ms 16620 KB Output is correct
4 Correct 180 ms 15724 KB Output is correct
5 Correct 170 ms 15212 KB Output is correct
6 Correct 190 ms 15724 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 15212 KB Output is correct
2 Correct 180 ms 15724 KB Output is correct
3 Correct 195 ms 15596 KB Output is correct
4 Correct 188 ms 15468 KB Output is correct
5 Correct 180 ms 14956 KB Output is correct
6 Correct 181 ms 15468 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 15340 KB Output is correct
2 Correct 193 ms 15724 KB Output is correct
3 Correct 201 ms 15788 KB Output is correct
4 Correct 197 ms 16108 KB Output is correct
5 Correct 200 ms 14572 KB Output is correct
6 Correct 203 ms 15852 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 15596 KB Output is correct
2 Correct 164 ms 14956 KB Output is correct
3 Correct 219 ms 16824 KB Output is correct
4 Correct 190 ms 15468 KB Output is correct
5 Correct 192 ms 15724 KB Output is correct
6 Correct 207 ms 16692 KB Output is correct