oj.uz

Submission #238702

# Submission time Handle Problem Language Result Execution time Memory
238702 2020-06-12T11:46:08 Z TrayanaG Birmingham (COCI20_birmingham) C++14
70 / 70
 273 ms 11128 KB 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m,q,k;
int a[200020];
int used[200020];
vector <int> v[200020];
int br = 0;
queue<int>g;
void read()
{
    memset(used, -1, sizeof(used));
    cin>>n>>m>>q>>k;
    for(int i=1; i<=q; i++)
    {
        cin>>a[i];
        used[a[i]] = 0;
        g.push(a[i]);
    }
    int x,y;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

}

void BFS()
{
    while(!g.empty())
    {
        int w = g.front();
        g.pop();
        int nb;
        int sz = v[w].size();
        for(int j=0; j<sz; j++)
        {
            nb = v[w][j];
            if(used[nb]==-1)
            {
                used[nb] = used[w]+1;
                g.push(nb);
            }
        }
    }
}
int answer[200500];
int main()
{
    read();
    BFS();
    int k1 = k;
    for(int j=1; j<=200000; j++)
    {
        int lamp=0;
        for(int i=1; i<=n; i++)
        {
            if(used[i]>0)
            {
                lamp = 1;
                used[i]-=j*k;
                if(used[i]<=0)answer[i] = j;
            }
        }
       if(lamp==0)break;
    }

    cout<<answer[1];
    for(int i=2; i<=n; i++)
    {
        cout<<" "<<answer[i];
    }
    cout<<endl;

    return 0;
}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:54:9: warning: unused variable 'k1' [-Wunused-variable]
     int k1 = k;
         ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5888 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 7 ms 5888 KB Output is correct
4 Correct 6 ms 5760 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 10616 KB Output is correct
2 Correct 235 ms 10960 KB Output is correct
3 Correct 237 ms 11000 KB Output is correct
4 Correct 175 ms 10232 KB Output is correct
5 Correct 196 ms 10548 KB Output is correct
6 Correct 241 ms 11128 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 10872 KB Output is correct
2 Correct 228 ms 10744 KB Output is correct
3 Correct 229 ms 10872 KB Output is correct
4 Correct 231 ms 10872 KB Output is correct
5 Correct 208 ms 10744 KB Output is correct
6 Correct 219 ms 10756 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 10616 KB Output is correct
2 Correct 242 ms 10888 KB Output is correct
3 Correct 260 ms 11128 KB Output is correct
4 Correct 240 ms 10872 KB Output is correct
5 Correct 208 ms 10488 KB Output is correct
6 Correct 230 ms 10872 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 10360 KB Output is correct
2 Correct 218 ms 10744 KB Output is correct
3 Correct 264 ms 11000 KB Output is correct
4 Correct 204 ms 10488 KB Output is correct
5 Correct 201 ms 10360 KB Output is correct
6 Correct 220 ms 10744 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 10360 KB Output is correct
2 Correct 209 ms 10592 KB Output is correct
3 Correct 212 ms 10616 KB Output is correct
4 Correct 209 ms 10488 KB Output is correct
5 Correct 215 ms 10616 KB Output is correct
6 Correct 222 ms 10744 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 10360 KB Output is correct
2 Correct 212 ms 10616 KB Output is correct
3 Correct 218 ms 10616 KB Output is correct
4 Correct 246 ms 10744 KB Output is correct
5 Correct 209 ms 10488 KB Output is correct
6 Correct 211 ms 10872 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 10588 KB Output is correct
2 Correct 182 ms 10360 KB Output is correct
3 Correct 273 ms 11000 KB Output is correct
4 Correct 209 ms 10592 KB Output is correct
5 Correct 208 ms 10616 KB Output is correct
6 Correct 242 ms 11128 KB Output is correct