oj.uz

Submission #998983

# Submission time Handle Problem Language Result Execution time Memory
998983 2024-06-15T03:12:22 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 101 ms 8276 KB 
#include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 1;

vector<int> nei[M];
int dis[M];
bool vis[M];

void bfs(vector<int> v)
{
	for (int i=0;i<M;i++)
		dis[i]=M;
	queue<int> q;
	for (int i:v)
		dis[i]=0,q.push(i);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int i:nei[u])
			if (!vis[i] && dis[i]>dis[u]+1)
			{
				vis[i]=true;
				dis[i]=dis[u]+1;
				q.push(i);
			}
	}
}

int wtf(int d)
{
	for (int i=0;i<=d;i++)
		if (i*(i+1)/2>=d)
			return i;
}

int main()
{
	int n,m,q,k;
	cin>>n>>m>>q>>k;
	vector<int> v(q);
	for (int i=0;i<q;i++)
		cin>>v[i];
	for (int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	bfs(v);
	for (int i=1;i<=n;i++)
	{
		int d=(dis[i]+k-1)/k;
		cout<<wtf(d)<<' ';
	}
	cout<<endl;
	
	return 0;
}

Compilation message

birmingham.cpp: In function 'int wtf(int)':
birmingham.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
   37 | }
      | ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7484 KB Output is correct
2 Correct 87 ms 7764 KB Output is correct
3 Correct 96 ms 8148 KB Output is correct
4 Correct 72 ms 7332 KB Output is correct
5 Correct 74 ms 7400 KB Output is correct
6 Correct 95 ms 8276 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7744 KB Output is correct
2 Correct 82 ms 7668 KB Output is correct
3 Correct 91 ms 7884 KB Output is correct
4 Correct 94 ms 7760 KB Output is correct
5 Correct 87 ms 7764 KB Output is correct
6 Correct 81 ms 7856 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7504 KB Output is correct
2 Correct 87 ms 7764 KB Output is correct
3 Correct 101 ms 8104 KB Output is correct
4 Correct 92 ms 7764 KB Output is correct
5 Correct 75 ms 7508 KB Output is correct
6 Correct 82 ms 7764 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7248 KB Output is correct
2 Correct 81 ms 7632 KB Output is correct
3 Correct 93 ms 8008 KB Output is correct
4 Correct 76 ms 7512 KB Output is correct
5 Correct 72 ms 7252 KB Output is correct
6 Correct 86 ms 7764 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7248 KB Output is correct
2 Correct 79 ms 7508 KB Output is correct
3 Correct 82 ms 7764 KB Output is correct
4 Correct 77 ms 7504 KB Output is correct
5 Correct 76 ms 7520 KB Output is correct
6 Correct 81 ms 7812 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7252 KB Output is correct
2 Correct 80 ms 7504 KB Output is correct
3 Correct 79 ms 7564 KB Output is correct
4 Correct 82 ms 7760 KB Output is correct
5 Correct 80 ms 7508 KB Output is correct
6 Correct 83 ms 7764 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7508 KB Output is correct
2 Correct 71 ms 7248 KB Output is correct
3 Correct 92 ms 8020 KB Output is correct
4 Correct 73 ms 7500 KB Output is correct
5 Correct 79 ms 7504 KB Output is correct
6 Correct 91 ms 8072 KB Output is correct