oj.uz

Submission #709951

# Submission time Handle Problem Language Result Execution time Memory
709951 2023-03-15T01:21:37 Z pcc Birmingham (COCI20_birmingham) C++14
70 / 70
 229 ms 10240 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int mxn = 1e5+10;
vector<int> paths[mxn];
int dist[mxn];

int main(){
    ll n,m,qq,k;
    fill(dist,dist+mxn,-1);
    cin>>n>>m>>qq>>k;
    queue<int> q;
    for(int i = 0;i<qq;i++){
        int x;
        cin>>x;
        q.push(x);
        dist[x] = 0;
    }
    for(int i = 0;i<m;i++){
        int a,b;
        cin>>a>>b;
        paths[a].push_back(b);
        paths[b].push_back(a);
    }
    while(!q.empty()){
        auto now = q.front();
        q.pop();
        for(auto nxt:paths[now]){
            if(dist[nxt] != -1)continue;
            dist[nxt] = dist[now]+1;
            q.push(nxt);
        }
    }
    for(int i = 1;i<=n;i++){
        ll l = 0,r = n;
        while(l != r){
            ll mid = (l+r)>>1;
            if(mid*(mid+1)/2*k>=dist[i])r = mid;
            else l = mid+1;
        }
        cout<<l<<' ';
    }
}
/*
6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6


*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 9440 KB Output is correct
2 Correct 168 ms 9776 KB Output is correct
3 Correct 229 ms 10108 KB Output is correct
4 Correct 129 ms 8848 KB Output is correct
5 Correct 146 ms 9080 KB Output is correct
6 Correct 202 ms 10240 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 9980 KB Output is correct
2 Correct 169 ms 9616 KB Output is correct
3 Correct 180 ms 9804 KB Output is correct
4 Correct 159 ms 9948 KB Output is correct
5 Correct 186 ms 9668 KB Output is correct
6 Correct 144 ms 9492 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 9444 KB Output is correct
2 Correct 163 ms 9900 KB Output is correct
3 Correct 176 ms 10108 KB Output is correct
4 Correct 166 ms 9864 KB Output is correct
5 Correct 176 ms 9232 KB Output is correct
6 Correct 143 ms 9488 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 9068 KB Output is correct
2 Correct 153 ms 9560 KB Output is correct
3 Correct 173 ms 9904 KB Output is correct
4 Correct 164 ms 9320 KB Output is correct
5 Correct 139 ms 8932 KB Output is correct
6 Correct 148 ms 9492 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 9144 KB Output is correct
2 Correct 137 ms 9344 KB Output is correct
3 Correct 142 ms 9328 KB Output is correct
4 Correct 158 ms 9272 KB Output is correct
5 Correct 136 ms 9364 KB Output is correct
6 Correct 148 ms 9292 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 9064 KB Output is correct
2 Correct 157 ms 9444 KB Output is correct
3 Correct 147 ms 9296 KB Output is correct
4 Correct 181 ms 9528 KB Output is correct
5 Correct 178 ms 9236 KB Output is correct
6 Correct 157 ms 9552 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9240 KB Output is correct
2 Correct 145 ms 8900 KB Output is correct
3 Correct 160 ms 10092 KB Output is correct
4 Correct 169 ms 9108 KB Output is correct
5 Correct 165 ms 9388 KB Output is correct
6 Correct 170 ms 10112 KB Output is correct