oj.uz

Submission #340394

# Submission time Handle Problem Language Result Execution time Memory
340394 2020-12-27T13:48:27 Z Hazem Birmingham (COCI20_birmingham) C++14
70 / 70
 176 ms 13932 KB 
/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long

const int N = 2e5 + 10;


LL LINF = 100000000000000000;
LL INF = 1000000000;
int MOD = 1e9+7;

vector<int>adj[N];
queue<int>que;
int dis[N],vis[N];

void bfs(){

    while(!que.empty()){
        int u = que.front();
        que.pop();

        if(vis[u])continue;
        vis[u] = 1;

        for(auto x:adj[u]) 
            dis[x] = min(dis[x],dis[u]+1),que.push(x);
    }
}

int main()
{
    //freopen("out.txt","w",stdout);
    int n,m,k,q;
    scanf("%d%d%d%d",&n,&m,&q,&k);

    for(int i=1;i<=n;i++)
        dis[i] = INF;

    for(int i=1;i<=q;i++){
        int x;cin>>x;
        dis[x] = 0;
        que.push(x);
    }
    
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bfs();

    for(int i=1;i<=n;i++){
        int cur = 0;
        for(int j=0;;j++)
            if(cur>=dis[i]){
                printf("%d ",j);
                break;
            }
            else cur += k*(j+1); 
    }
}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%d%d%d%d",&n,&m,&q,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
birmingham.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 12620 KB Output is correct
2 Correct 131 ms 13120 KB Output is correct
3 Correct 150 ms 13704 KB Output is correct
4 Correct 103 ms 12012 KB Output is correct
5 Correct 108 ms 12268 KB Output is correct
6 Correct 143 ms 13556 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 13164 KB Output is correct
2 Correct 131 ms 12960 KB Output is correct
3 Correct 144 ms 13420 KB Output is correct
4 Correct 146 ms 13200 KB Output is correct
5 Correct 158 ms 13036 KB Output is correct
6 Correct 150 ms 12820 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 12652 KB Output is correct
2 Correct 155 ms 13164 KB Output is correct
3 Correct 176 ms 13676 KB Output is correct
4 Correct 149 ms 13140 KB Output is correct
5 Correct 125 ms 12396 KB Output is correct
6 Correct 141 ms 12960 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 12220 KB Output is correct
2 Correct 128 ms 12908 KB Output is correct
3 Correct 137 ms 13548 KB Output is correct
4 Correct 133 ms 12524 KB Output is correct
5 Correct 115 ms 12140 KB Output is correct
6 Correct 137 ms 12872 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 12268 KB Output is correct
2 Correct 129 ms 12780 KB Output is correct
3 Correct 118 ms 12780 KB Output is correct
4 Correct 111 ms 12396 KB Output is correct
5 Correct 117 ms 12656 KB Output is correct
6 Correct 126 ms 12724 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 12396 KB Output is correct
2 Correct 124 ms 12780 KB Output is correct
3 Correct 132 ms 12652 KB Output is correct
4 Correct 122 ms 12876 KB Output is correct
5 Correct 111 ms 12488 KB Output is correct
6 Correct 136 ms 12920 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 12524 KB Output is correct
2 Correct 101 ms 12012 KB Output is correct
3 Correct 135 ms 13644 KB Output is correct
4 Correct 121 ms 12524 KB Output is correct
5 Correct 116 ms 12648 KB Output is correct
6 Correct 172 ms 13932 KB Output is correct