oj.uz

Submission #238541

# Submission time Handle Problem Language Result Execution time Memory
238541 2020-06-11T17:16:26 Z Salito Birmingham (COCI20_birmingham) C++14
70 / 70
 270 ms 9272 KB 
#include<bits/stdc++.h>
using namespace std;
int const maxn = 100005;

int n,m,q,k;
int a[maxn];
vector<int>v[maxn];

void read()
{
    int i;
	cin>>n>>m>>q>>k;

	for(i=0;i<q;i++)
        cin>>a[i];

    int x,y;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

int ans[maxn];
void bfs_solve()
{
    queue<int>l;
    int i,sz;
    for(i=0;i<q;i++)
    {
        l.push(a[i]);
        ans[a[i]] = 1;
    }

    while(!l.empty())
    {
        int t = l.front();
        l.pop();

        sz = v[t].size();
        for(i=0;i<sz;i++)
        {
            int nb = v[t][i];
            if(!ans[nb])
            {
                ans[nb] = ans[t]+1;
                l.push(nb);
            }
        }
    }
}

int get_ans(int x)
{
    if(x == 1)
        return 0;
    int t;
    x--;
    int i = 1;
    while(x - i*k > 0)
    {
        x-=i*k;
        i++;
    }
    return i;
}

void print()
{
    int i;
    for(i=1;i<=n;i++)
        cout<<get_ans(ans[i])<<" ";
    cout<<endl;
}

int main()
{
    read();

    bfs_solve();

    print();
	return 0;
}

Compilation message

birmingham.cpp: In function 'int get_ans(int)':
birmingham.cpp:59:9: warning: unused variable 't' [-Wunused-variable]
     int t;
         ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 7332 KB Output is correct
2 Correct 237 ms 9040 KB Output is correct
3 Correct 247 ms 9224 KB Output is correct
4 Correct 179 ms 8560 KB Output is correct
5 Correct 191 ms 8680 KB Output is correct
6 Correct 234 ms 9272 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 7632 KB Output is correct
2 Correct 219 ms 9020 KB Output is correct
3 Correct 219 ms 9128 KB Output is correct
4 Correct 222 ms 9036 KB Output is correct
5 Correct 215 ms 8916 KB Output is correct
6 Correct 201 ms 8872 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 7512 KB Output is correct
2 Correct 225 ms 9132 KB Output is correct
3 Correct 244 ms 9268 KB Output is correct
4 Correct 230 ms 9168 KB Output is correct
5 Correct 191 ms 8804 KB Output is correct
6 Correct 212 ms 8892 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 7272 KB Output is correct
2 Correct 217 ms 9080 KB Output is correct
3 Correct 259 ms 9124 KB Output is correct
4 Correct 206 ms 8796 KB Output is correct
5 Correct 181 ms 8552 KB Output is correct
6 Correct 198 ms 8824 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 7144 KB Output is correct
2 Correct 195 ms 8668 KB Output is correct
3 Correct 241 ms 8760 KB Output is correct
4 Correct 194 ms 8800 KB Output is correct
5 Correct 197 ms 8800 KB Output is correct
6 Correct 208 ms 8824 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 7272 KB Output is correct
2 Correct 212 ms 8792 KB Output is correct
3 Correct 202 ms 8852 KB Output is correct
4 Correct 214 ms 9044 KB Output is correct
5 Correct 190 ms 8800 KB Output is correct
6 Correct 227 ms 8936 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 7396 KB Output is correct
2 Correct 192 ms 8584 KB Output is correct
3 Correct 223 ms 9240 KB Output is correct
4 Correct 229 ms 8808 KB Output is correct
5 Correct 232 ms 8920 KB Output is correct
6 Correct 270 ms 9140 KB Output is correct