oj.uz

Submission #999059

# Submission time Handle Problem Language Result Execution time Memory
999059 2024-06-15T05:54:49 Z UmairAhmadMirza Birmingham (COCI20_birmingham) C++17
70 / 70
 114 ms 7788 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=1e5+5;
int const inf=1e9+7;

int dist[N];
deque<int> v;
vector<int> adj[N];

int main(){
    int n,m,q,k;
    cin>>n>>m>>q>>k;
    for(int i=0;i<=n;i++)
        dist[i]=inf;
    for(int i=1;i<=q;i++){
        int a;
        cin>>a;
        v.push_back(a);
        dist[a]=0;
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    while(v.size()){
        int node=v[0];
        // cout<<node<<' '<<dist[node]<<endl;
        v.pop_front();
        for(int u:adj[node])
            if(dist[u]>dist[node]+1){
                dist[u]=dist[node]+1;
                v.push_back(u);
            }
    }
    for(int i=1;i<=n;i++){
        int low=-1,high=100001;
        while(high-low>1){
            ll mid=(high+low)/2;
            if(k*(mid*(mid+1))>=dist[i]*2)
                high=mid;
            else
                low=mid;
        }
        cout<<high<<' ';
    }
    cout<<endl;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7508 KB Output is correct
2 Correct 102 ms 7560 KB Output is correct
3 Correct 99 ms 7608 KB Output is correct
4 Correct 74 ms 7216 KB Output is correct
5 Correct 81 ms 7248 KB Output is correct
6 Correct 97 ms 7764 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7788 KB Output is correct
2 Correct 84 ms 7508 KB Output is correct
3 Correct 97 ms 7508 KB Output is correct
4 Correct 96 ms 7684 KB Output is correct
5 Correct 87 ms 7480 KB Output is correct
6 Correct 86 ms 7268 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7500 KB Output is correct
2 Correct 95 ms 7760 KB Output is correct
3 Correct 114 ms 7764 KB Output is correct
4 Correct 90 ms 7748 KB Output is correct
5 Correct 80 ms 7248 KB Output is correct
6 Correct 86 ms 7248 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7252 KB Output is correct
2 Correct 87 ms 7504 KB Output is correct
3 Correct 94 ms 7764 KB Output is correct
4 Correct 81 ms 7504 KB Output is correct
5 Correct 77 ms 7140 KB Output is correct
6 Correct 88 ms 7244 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7248 KB Output is correct
2 Correct 83 ms 7508 KB Output is correct
3 Correct 85 ms 7248 KB Output is correct
4 Correct 83 ms 7288 KB Output is correct
5 Correct 80 ms 7504 KB Output is correct
6 Correct 82 ms 7316 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 7252 KB Output is correct
2 Correct 85 ms 7504 KB Output is correct
3 Correct 88 ms 7332 KB Output is correct
4 Correct 89 ms 7508 KB Output is correct
5 Correct 84 ms 7232 KB Output is correct
6 Correct 89 ms 7252 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7320 KB Output is correct
2 Correct 83 ms 7252 KB Output is correct
3 Correct 97 ms 7760 KB Output is correct
4 Correct 82 ms 7432 KB Output is correct
5 Correct 87 ms 7504 KB Output is correct
6 Correct 102 ms 7712 KB Output is correct