oj.uz

Submission #736511

# Submission time Handle Problem Language Result Execution time Memory
736511 2023-05-05T20:27:15 Z vjudge1 Birmingham (COCI20_birmingham) C++14
70 / 70
 104 ms 34684 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define N 1000005
#define big 1000000000000000007
#define pb push_back
vector<int> kim;
int uzak[N];
vector<int> adj[N];
void bfs(){
  queue<pair<int,int>> q;
  for(auto u:kim)q.push({u,0});
  while(q.size()){
    int x=q.front().first, deg=q.front().second;
    q.pop();
    if(uzak[x]!=-1)continue;
    uzak[x]=deg;
    for(auto u:adj[x]){
      if(uzak[u]!=-1)continue;
      q.push({u,deg+1});
    }
  }
  
}

int main(){
  lalala;
  memset(uzak,-1,sizeof(uzak));
  int n,m,q,k;cin>>n>>m>>q>>k;
  for(int i=0;i<q;i++){
    int a;cin>>a;
    kim.push_back(a);
  }
  vector<ll int> v;
  v.pb(1);v.pb(k+1);
  for(int i=2;;i++){
    v.pb((i*(i+1)/2)*k+1);
    if((i*(i+1)/2)*k>n)break;
  }
  for(int i=0;i<m;i++){
    int a,b;cin>>a>>b;
    adj[a].push_back(b);adj[b].push_back(a);
  }
  bfs();
  int yer=0;
  for(int i=1;i<=n;i++){
    cout<<upper_bound(v.begin(),v.end(),uzak[i])-v.begin()<<" ";
  }
  
  
}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:48:7: warning: unused variable 'yer' [-Wunused-variable]
   48 |   int yer=0;
      |       ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27720 KB Output is correct
2 Correct 14 ms 27652 KB Output is correct
3 Correct 13 ms 27676 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27768 KB Output is correct
2 Correct 17 ms 27684 KB Output is correct
3 Correct 15 ms 27688 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27716 KB Output is correct
2 Correct 14 ms 27604 KB Output is correct
3 Correct 13 ms 27732 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27640 KB Output is correct
2 Correct 14 ms 27612 KB Output is correct
3 Correct 13 ms 27720 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27716 KB Output is correct
2 Correct 13 ms 27716 KB Output is correct
3 Correct 13 ms 27604 KB Output is correct
4 Correct 16 ms 27624 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27708 KB Output is correct
2 Correct 13 ms 27608 KB Output is correct
3 Correct 14 ms 27720 KB Output is correct
4 Correct 18 ms 27720 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27696 KB Output is correct
2 Correct 13 ms 27604 KB Output is correct
3 Correct 14 ms 27604 KB Output is correct
4 Correct 14 ms 27704 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 33600 KB Output is correct
2 Correct 92 ms 33916 KB Output is correct
3 Correct 90 ms 34612 KB Output is correct
4 Correct 92 ms 33228 KB Output is correct
5 Correct 73 ms 33260 KB Output is correct
6 Correct 104 ms 34684 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 33924 KB Output is correct
2 Correct 80 ms 33792 KB Output is correct
3 Correct 84 ms 34000 KB Output is correct
4 Correct 91 ms 34008 KB Output is correct
5 Correct 90 ms 33776 KB Output is correct
6 Correct 75 ms 34048 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 33632 KB Output is correct
2 Correct 81 ms 33928 KB Output is correct
3 Correct 90 ms 34528 KB Output is correct
4 Correct 84 ms 33876 KB Output is correct
5 Correct 72 ms 33520 KB Output is correct
6 Correct 74 ms 34228 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 33312 KB Output is correct
2 Correct 80 ms 33796 KB Output is correct
3 Correct 98 ms 34132 KB Output is correct
4 Correct 88 ms 33508 KB Output is correct
5 Correct 68 ms 33340 KB Output is correct
6 Correct 77 ms 34116 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 33412 KB Output is correct
2 Correct 82 ms 33620 KB Output is correct
3 Correct 77 ms 33804 KB Output is correct
4 Correct 74 ms 33416 KB Output is correct
5 Correct 89 ms 33564 KB Output is correct
6 Correct 89 ms 33984 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 33348 KB Output is correct
2 Correct 86 ms 33640 KB Output is correct
3 Correct 73 ms 33860 KB Output is correct
4 Correct 80 ms 33752 KB Output is correct
5 Correct 73 ms 33476 KB Output is correct
6 Correct 81 ms 34248 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 33472 KB Output is correct
2 Correct 71 ms 33208 KB Output is correct
3 Correct 89 ms 34284 KB Output is correct
4 Correct 95 ms 33468 KB Output is correct
5 Correct 91 ms 33584 KB Output is correct
6 Correct 88 ms 34684 KB Output is correct