oj.uz

Submission #1019186

# Submission time Handle Problem Language Result Execution time Memory
1019186 2024-07-10T14:56:52 Z Tri_Pahm Birmingham (COCI20_birmingham) C++14
70 / 70
 78 ms 36568 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define X first
#define Y second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define file "BMH"

using namespace std;

const int N=1e6+5;
const int NN=1e3+9;
const int MOD=1e9+7;
const ll INF=1e18;
const ld eps=1e-6;
const ld pi=acos(-1); // 48 digits

int n, m, Q, k;
queue<int> q;
vector<int> g[N];
bool dd[N], ddd[N];
ll b[N];
int d[N], day[N];

void inp() {
    cin>>n>>m>>Q>>k;
    for (int i=1;i<=Q;i++) {
        int x;
        cin>>x;
        q.push(x);
        dd[x]=1;
        ddd[x]=1;
    }
    for (int i=1;i<=m;i++) {
        int x, y;
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
}

void bfs() {
    int tam=1;
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        for (int v : g[u])
            if (!dd[v]){
                q.push(v);
                dd[v]=1;
//                cout<<v<<" "<<tam<<endl;
                d[v]=d[u]+1;

            }
    }
}

void process() {
    bfs();
    for (int i=1;i<=446;i++)
        b[i]=b[i-1]+i*k;
    for (int i=1;i<=n;i++) {
        int pos=lower_bound(b+1,b+447,d[i])-b;
//        cout<<d[i]<<endl;
        day[i]=pos;
        if (ddd[i]) day[i]=0;
    }
    for (int i=1;i<=n;i++)
        cout<<day[i]<<" ";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
//    cin>>t;
    while (t--) {
        inp();
        process();
    }
    return 0;
}
/*
6 8 1 1
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

6 8 2 1
6 4
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6

6 8 1 2
6
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
*/

Compilation message

birmingham.cpp: In function 'void bfs()':
birmingham.cpp:45:9: warning: unused variable 'tam' [-Wunused-variable]
   45 |     int tam=1;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24920 KB Output is correct
2 Correct 7 ms 24824 KB Output is correct
3 Correct 7 ms 24924 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24872 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 7 ms 24920 KB Output is correct
4 Correct 8 ms 24924 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24924 KB Output is correct
2 Correct 8 ms 24920 KB Output is correct
3 Correct 9 ms 24920 KB Output is correct
4 Correct 7 ms 24924 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24924 KB Output is correct
2 Correct 8 ms 24920 KB Output is correct
3 Correct 8 ms 24924 KB Output is correct
4 Correct 7 ms 24924 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31404 KB Output is correct
2 Correct 53 ms 31568 KB Output is correct
3 Correct 59 ms 32080 KB Output is correct
4 Correct 46 ms 30840 KB Output is correct
5 Correct 52 ms 33292 KB Output is correct
6 Correct 53 ms 31824 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 31568 KB Output is correct
2 Correct 49 ms 31604 KB Output is correct
3 Correct 55 ms 31532 KB Output is correct
4 Correct 66 ms 31576 KB Output is correct
5 Correct 52 ms 31572 KB Output is correct
6 Correct 48 ms 31316 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31312 KB Output is correct
2 Correct 54 ms 31904 KB Output is correct
3 Correct 68 ms 32084 KB Output is correct
4 Correct 56 ms 31564 KB Output is correct
5 Correct 50 ms 31312 KB Output is correct
6 Correct 57 ms 31312 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 31052 KB Output is correct
2 Correct 61 ms 31316 KB Output is correct
3 Correct 55 ms 31984 KB Output is correct
4 Correct 46 ms 31312 KB Output is correct
5 Correct 43 ms 31056 KB Output is correct
6 Correct 49 ms 31364 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31236 KB Output is correct
2 Correct 60 ms 31316 KB Output is correct
3 Correct 50 ms 31308 KB Output is correct
4 Correct 48 ms 31316 KB Output is correct
5 Correct 50 ms 33636 KB Output is correct
6 Correct 49 ms 32084 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 31824 KB Output is correct
2 Correct 50 ms 32124 KB Output is correct
3 Correct 56 ms 32064 KB Output is correct
4 Correct 55 ms 32384 KB Output is correct
5 Correct 54 ms 31828 KB Output is correct
6 Correct 59 ms 32416 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 31980 KB Output is correct
2 Correct 55 ms 31564 KB Output is correct
3 Correct 63 ms 36568 KB Output is correct
4 Correct 50 ms 31756 KB Output is correct
5 Correct 56 ms 32132 KB Output is correct
6 Correct 60 ms 32864 KB Output is correct