oj.uz

Submission #237635

# Submission time Handle Problem Language Result Execution time Memory
237635 2020-06-07T23:33:02 Z akat Birmingham (COCI20_birmingham) C++14
70 / 70
 138 ms 10744 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m,s,k,i,j,a,b,dist[N],wave[N];
	vector<int>adj[N];
	cin>>n>>m>>s>>k;
	memset(dist,-1,sizeof(dist));
	queue<int>q;
	for(i = 0; i < s; i++)
	{
		cin>>a;
		q.push(a);
		dist[a] = 0;
	}
	for(i = 0; i < m; i++)
	{
		cin>>a>>b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	while(q.size())
	{
		a = q.front();
		q.pop();
		for(int x:adj[a])
		{
			if(dist[x] == -1)
			{
				dist[x] = dist[a] + 1;
				q.push(x);
			}
		}
	}
	wave[0] = 0;
	int curr = 0, old = 0;
	for(i = 1; curr < n; i++)
	{
		old = curr;
		curr += k * i;
		for(j = old + 1; j <= min(n,curr); j++)
			wave[j] = i;
	}
	for(i=1;i<=n;i++)
		cout<<wave[dist[i]]<<" \n"[i==n];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 7800 KB Output is correct
2 Correct 138 ms 10464 KB Output is correct
3 Correct 127 ms 10608 KB Output is correct
4 Correct 87 ms 9336 KB Output is correct
5 Correct 101 ms 9592 KB Output is correct
6 Correct 121 ms 10716 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 8056 KB Output is correct
2 Correct 99 ms 10232 KB Output is correct
3 Correct 113 ms 10360 KB Output is correct
4 Correct 112 ms 10616 KB Output is correct
5 Correct 125 ms 10096 KB Output is correct
6 Correct 92 ms 9952 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 7904 KB Output is correct
2 Correct 132 ms 10360 KB Output is correct
3 Correct 136 ms 10644 KB Output is correct
4 Correct 129 ms 10460 KB Output is correct
5 Correct 90 ms 9720 KB Output is correct
6 Correct 87 ms 9976 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7788 KB Output is correct
2 Correct 97 ms 10104 KB Output is correct
3 Correct 105 ms 10424 KB Output is correct
4 Correct 89 ms 9848 KB Output is correct
5 Correct 128 ms 9464 KB Output is correct
6 Correct 92 ms 9904 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7672 KB Output is correct
2 Correct 93 ms 9848 KB Output is correct
3 Correct 102 ms 9952 KB Output is correct
4 Correct 117 ms 9720 KB Output is correct
5 Correct 85 ms 9832 KB Output is correct
6 Correct 114 ms 9848 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7672 KB Output is correct
2 Correct 103 ms 10104 KB Output is correct
3 Correct 87 ms 9848 KB Output is correct
4 Correct 95 ms 10108 KB Output is correct
5 Correct 88 ms 9720 KB Output is correct
6 Correct 95 ms 9976 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7800 KB Output is correct
2 Correct 84 ms 9336 KB Output is correct
3 Correct 102 ms 10744 KB Output is correct
4 Correct 90 ms 9852 KB Output is correct
5 Correct 93 ms 9976 KB Output is correct
6 Correct 97 ms 10616 KB Output is correct