oj.uz

Submission #1019097

# Submission time Handle Problem Language Result Execution time Memory
1019097 2024-07-10T13:28:34 Z Tri_Pahm Birmingham (COCI20_birmingham) C++14
70 / 70
 84 ms 32084 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, sz;
queue<int> q;
vector<int> g[N];
bool dd[N], ddd[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() {
    sz=Q;
    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();
    ll val=0;
    for (int i=1;i<=1e7/n;i++) {
        val+=k*i;
        for (int j=1;j<=n;j++)
            if (d[j]<=val && !ddd[j]) {
                day[j]=i;
                ddd[j]=1;
            }
    }
    for (int i=1;i<=n;i++)
        cout<<day[i]<<" ";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen(file".inp","r",stdin);
//    freopen(file".out","w",stdout);
    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 23 ms 23900 KB Output is correct
2 Correct 20 ms 23900 KB Output is correct
3 Correct 18 ms 23896 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23900 KB Output is correct
2 Correct 19 ms 23900 KB Output is correct
3 Correct 18 ms 23848 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23900 KB Output is correct
2 Correct 17 ms 23800 KB Output is correct
3 Correct 18 ms 23976 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23900 KB Output is correct
2 Correct 19 ms 23892 KB Output is correct
3 Correct 18 ms 23900 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23896 KB Output is correct
2 Correct 19 ms 23896 KB Output is correct
3 Correct 18 ms 23896 KB Output is correct
4 Correct 18 ms 23956 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23900 KB Output is correct
2 Correct 18 ms 23900 KB Output is correct
3 Correct 19 ms 23900 KB Output is correct
4 Correct 18 ms 23896 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23896 KB Output is correct
2 Correct 18 ms 23896 KB Output is correct
3 Correct 18 ms 23968 KB Output is correct
4 Correct 18 ms 23980 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 31312 KB Output is correct
2 Correct 64 ms 31640 KB Output is correct
3 Correct 69 ms 32080 KB Output is correct
4 Correct 58 ms 30608 KB Output is correct
5 Correct 79 ms 30760 KB Output is correct
6 Correct 71 ms 32084 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 31572 KB Output is correct
2 Correct 71 ms 31392 KB Output is correct
3 Correct 63 ms 31824 KB Output is correct
4 Correct 68 ms 31892 KB Output is correct
5 Correct 61 ms 31412 KB Output is correct
6 Correct 60 ms 31216 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 31204 KB Output is correct
2 Correct 67 ms 31748 KB Output is correct
3 Correct 67 ms 31960 KB Output is correct
4 Correct 67 ms 31828 KB Output is correct
5 Correct 67 ms 31080 KB Output is correct
6 Correct 65 ms 31300 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 30800 KB Output is correct
2 Correct 83 ms 31316 KB Output is correct
3 Correct 84 ms 32028 KB Output is correct
4 Correct 57 ms 31124 KB Output is correct
5 Correct 52 ms 30736 KB Output is correct
6 Correct 58 ms 31172 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 30996 KB Output is correct
2 Correct 60 ms 31280 KB Output is correct
3 Correct 59 ms 31316 KB Output is correct
4 Correct 58 ms 31064 KB Output is correct
5 Correct 56 ms 31316 KB Output is correct
6 Correct 61 ms 31060 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31056 KB Output is correct
2 Correct 59 ms 31312 KB Output is correct
3 Correct 57 ms 31160 KB Output is correct
4 Correct 65 ms 31564 KB Output is correct
5 Correct 60 ms 31056 KB Output is correct
6 Correct 57 ms 31484 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31060 KB Output is correct
2 Correct 52 ms 30800 KB Output is correct
3 Correct 64 ms 31824 KB Output is correct
4 Correct 58 ms 31060 KB Output is correct
5 Correct 59 ms 31312 KB Output is correct
6 Correct 64 ms 31888 KB Output is correct