oj.uz

Submission #213238

# Submission time Handle Problem Language Result Execution time Memory
213238 2020-03-25T10:49:08 Z Dremix10 Birmingham (COCI20_birmingham) C++17
70 / 70
 276 ms 11384 KB 
#include <bits/stdc++.h>
using namespace std;


int main (){
int n,m,q,k;
cin>>n>>m>>q>>k;

int sources[q];
int i;

for(i=0;i<q;i++)
    cin>>sources[i];

vector <vector <int> > a(n+1,vector<int>());

for(i=0;i<m;i++){
    int x,y;
    cin>>x>>y;

    a[x].push_back(y);
    a[y].push_back(x);
}
/*
int j;
for(i=1;i<=n;i++){
    cout<<i<<" -> ";
    for(j=0;j<a[i].size();j++)
        cout<<a[i][j]<<" ";
    cout<<endl;
}
*/

vector <int> d(n+1,1000000000);
queue <int> qu;

for(i=0;i<q;i++){
    d[sources[i]]=0;
    qu.push(sources[i]);
}

while(!qu.empty()){
    int start=qu.front();
    qu.pop();

    for(i=0;i<a[start].size();i++){

        if(d[a[start][i]]>d[start]+1){
            d[a[start][i]]=d[start]+1;
            qu.push(a[start][i]);
        }

    }

}
int fix[200000];
memset(fix,0,sizeof(fix));

long long curr=1;
long long next=1;
long long counter=0;
fix[0]=0;
for(i=1;i<200000;i++){
    fix[i]=curr;
    counter++;
    if(counter==next){
        curr++;
        next++;
        counter=0;
    }

}

for(i=1;i<=n;i++){

    int ans=d[i]/k;
    if(d[i]%k>0)
        ans++;


    cout<<fix[ans]<<" ";
}
//cout<<endl;
//for(i=1;i<=n;i++)
 //   cout<<d[i]<<" ";

}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:46:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<a[start].size();i++){
             ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 10232 KB Output is correct
2 Correct 217 ms 10744 KB Output is correct
3 Correct 276 ms 11256 KB Output is correct
4 Correct 176 ms 9720 KB Output is correct
5 Correct 206 ms 9976 KB Output is correct
6 Correct 235 ms 11384 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 10744 KB Output is correct
2 Correct 210 ms 10488 KB Output is correct
3 Correct 221 ms 10872 KB Output is correct
4 Correct 216 ms 10872 KB Output is correct
5 Correct 217 ms 10488 KB Output is correct
6 Correct 203 ms 10616 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 10360 KB Output is correct
2 Correct 218 ms 10744 KB Output is correct
3 Correct 231 ms 11128 KB Output is correct
4 Correct 216 ms 10744 KB Output is correct
5 Correct 208 ms 10104 KB Output is correct
6 Correct 208 ms 10744 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 9976 KB Output is correct
2 Correct 212 ms 10492 KB Output is correct
3 Correct 221 ms 11000 KB Output is correct
4 Correct 199 ms 10232 KB Output is correct
5 Correct 179 ms 9852 KB Output is correct
6 Correct 201 ms 10616 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 9976 KB Output is correct
2 Correct 211 ms 10232 KB Output is correct
3 Correct 198 ms 10360 KB Output is correct
4 Correct 188 ms 10104 KB Output is correct
5 Correct 209 ms 10232 KB Output is correct
6 Correct 197 ms 10488 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 9976 KB Output is correct
2 Correct 199 ms 10360 KB Output is correct
3 Correct 212 ms 10360 KB Output is correct
4 Correct 209 ms 10488 KB Output is correct
5 Correct 217 ms 10104 KB Output is correct
6 Correct 213 ms 10744 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 10104 KB Output is correct
2 Correct 176 ms 9848 KB Output is correct
3 Correct 252 ms 11128 KB Output is correct
4 Correct 194 ms 10104 KB Output is correct
5 Correct 233 ms 10360 KB Output is correct
6 Correct 237 ms 11384 KB Output is correct