oj.uz

Submission #735275

# Submission time Handle Problem Language Result Execution time Memory
735275 2023-05-03T19:51:46 Z DangerNoodle7591 Birmingham (COCI20_birmingham) C++17
70 / 70
 103 ms 36128 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 27732 KB Output is correct
2 Correct 14 ms 27600 KB Output is correct
3 Correct 13 ms 27620 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27720 KB Output is correct
2 Correct 13 ms 27732 KB Output is correct
3 Correct 16 ms 27616 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27652 KB Output is correct
2 Correct 14 ms 27604 KB Output is correct
3 Correct 14 ms 27716 KB Output is correct
4 Correct 14 ms 27720 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 14 ms 27724 KB Output is correct
3 Correct 14 ms 27720 KB Output is correct
4 Correct 16 ms 27604 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 34452 KB Output is correct
2 Correct 86 ms 34928 KB Output is correct
3 Correct 89 ms 35916 KB Output is correct
4 Correct 95 ms 33844 KB Output is correct
5 Correct 80 ms 34028 KB Output is correct
6 Correct 91 ms 36044 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 34928 KB Output is correct
2 Correct 81 ms 34744 KB Output is correct
3 Correct 100 ms 35296 KB Output is correct
4 Correct 86 ms 34984 KB Output is correct
5 Correct 88 ms 34784 KB Output is correct
6 Correct 79 ms 35120 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 34452 KB Output is correct
2 Correct 97 ms 35016 KB Output is correct
3 Correct 101 ms 35792 KB Output is correct
4 Correct 97 ms 35000 KB Output is correct
5 Correct 75 ms 34300 KB Output is correct
6 Correct 86 ms 35280 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 33988 KB Output is correct
2 Correct 95 ms 34740 KB Output is correct
3 Correct 103 ms 35256 KB Output is correct
4 Correct 96 ms 34316 KB Output is correct
5 Correct 73 ms 33940 KB Output is correct
6 Correct 82 ms 35084 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 34036 KB Output is correct
2 Correct 87 ms 34384 KB Output is correct
3 Correct 84 ms 34724 KB Output is correct
4 Correct 82 ms 34172 KB Output is correct
5 Correct 77 ms 34332 KB Output is correct
6 Correct 76 ms 34948 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 34136 KB Output is correct
2 Correct 94 ms 34468 KB Output is correct
3 Correct 95 ms 34784 KB Output is correct
4 Correct 97 ms 34688 KB Output is correct
5 Correct 90 ms 34188 KB Output is correct
6 Correct 79 ms 35228 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 34296 KB Output is correct
2 Correct 74 ms 33932 KB Output is correct
3 Correct 98 ms 35548 KB Output is correct
4 Correct 78 ms 34212 KB Output is correct
5 Correct 80 ms 34464 KB Output is correct
6 Correct 100 ms 36128 KB Output is correct