oj.uz

Submission #257940

# Submission time Handle Problem Language Result Execution time Memory
257940 2020-08-05T05:33:24 Z MrRobot_28 Birmingham (COCI20_birmingham) C++17
70 / 70
 282 ms 10616 KB 
#include<bits/stdc++.h>
using namespace std;

signed main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(NULL);
//	cout.tie(NULL);
	int n, m, q, k;
	cin >> n >> m >> q >> k;
	vector <int> dist(n, 1e9);
	queue <int> Q;
	for(int i = 0; i < q; i++)
	{
		int a;
		cin >> a;
		a--;
		dist[a] = 0;
		Q.push(a);
	}
	vector <vector <int> > g(n);
	for(int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector <int> ans(n, 0);
	for(int i = 1;; i++)
	{
		while(Q.size() > 0 && dist[Q.front()] < i * (i + 1) / 2 * k)
		{
			int v = Q.front();
			Q.pop();
			for(int j = 0; j < g[v].size(); j++)
			{
				int to = g[v][j];
				if(dist[to] > dist[v] + 1)
				{
					ans[to] = i;
					dist[to] = dist[v] + 1;
					Q.push(to);
				}
			}
		}
		if(Q.size() == 0)
		{
			break;
		}
	}
	for(int i = 0; i < n; i++)
	{
		cout << ans[i] << " ";
	}
  	return 0;
}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < g[v].size(); j++)
                   ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 9972 KB Output is correct
2 Correct 244 ms 10300 KB Output is correct
3 Correct 282 ms 10612 KB Output is correct
4 Correct 203 ms 9336 KB Output is correct
5 Correct 196 ms 9592 KB Output is correct
6 Correct 255 ms 10576 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 10408 KB Output is correct
2 Correct 242 ms 10112 KB Output is correct
3 Correct 245 ms 10360 KB Output is correct
4 Correct 265 ms 10456 KB Output is correct
5 Correct 243 ms 10160 KB Output is correct
6 Correct 249 ms 9976 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 9976 KB Output is correct
2 Correct 250 ms 10460 KB Output is correct
3 Correct 272 ms 10560 KB Output is correct
4 Correct 234 ms 10360 KB Output is correct
5 Correct 205 ms 9680 KB Output is correct
6 Correct 222 ms 9980 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 9512 KB Output is correct
2 Correct 237 ms 10044 KB Output is correct
3 Correct 260 ms 10360 KB Output is correct
4 Correct 212 ms 9976 KB Output is correct
5 Correct 194 ms 9464 KB Output is correct
6 Correct 231 ms 9872 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 9592 KB Output is correct
2 Correct 221 ms 9848 KB Output is correct
3 Correct 217 ms 9860 KB Output is correct
4 Correct 196 ms 9848 KB Output is correct
5 Correct 202 ms 9848 KB Output is correct
6 Correct 206 ms 9792 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 9720 KB Output is correct
2 Correct 241 ms 9976 KB Output is correct
3 Correct 203 ms 9848 KB Output is correct
4 Correct 216 ms 10264 KB Output is correct
5 Correct 206 ms 9848 KB Output is correct
6 Correct 208 ms 10104 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 9720 KB Output is correct
2 Correct 183 ms 9464 KB Output is correct
3 Correct 239 ms 10488 KB Output is correct
4 Correct 196 ms 9716 KB Output is correct
5 Correct 202 ms 9976 KB Output is correct
6 Correct 236 ms 10616 KB Output is correct