oj.uz

Submission #689634

# Submission time Handle Problem Language Result Execution time Memory
689634 2023-01-29T03:20:51 Z Warinchai Birmingham (COCI20_birmingham) C++14
45 / 70
 172 ms 12812 KB 
#include<bits/stdc++.h>
using namespace std;
queue<pair<int,int> >q;
vector<int>v[200000];
int path[200005];
int main(){
	int n,m,nn,k;
	cin>>n>>m>>nn>>k;
	for(int i=1;i<=n;i++){
		path[i]=INT_MAX;
	}
	for(int i=0;i<nn;i++){
		int a;
		cin>>a;
		q.push({a,0});
		path[a]=0;
	}
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	//cout<<"info\n";
	while(!q.empty()){
		int a=q.front().first;
		int b=q.front().second;
		//cout<<a<<" "<<b<<endl;
		q.pop();
		for(int i=0;i<v[a].size();i++){
			if(b+1<path[v[a][i]]){
				path[v[a][i]]=b+1;
				q.push({v[a][i],b+1});
			}
		}
	}
	for(int i=1;i<=n;i++){
		int st=0,en=700,ans=0;
		while(en>=st){
			int md=(st+en)/2;
			if(md*(md+1)/2*k>=path[i]){
				ans=md;
				en=md-1;
			}else{
				st=md+1;
			}
		}
		cout<<ans<<" ";
	}
}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=0;i<v[a].size();i++){
      |               ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 10504 KB Output is correct
2 Correct 172 ms 12320 KB Output is correct
3 Correct 161 ms 12808 KB Output is correct
4 Correct 122 ms 11312 KB Output is correct
5 Correct 126 ms 11596 KB Output is correct
6 Correct 157 ms 12812 KB Output is correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 11032 KB Output is correct
2 Correct 147 ms 12104 KB Output is correct
3 Correct 166 ms 12380 KB Output is correct
4 Correct 162 ms 12424 KB Output is correct
5 Incorrect 153 ms 12328 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 10700 KB Output is correct
2 Correct 149 ms 12344 KB Output is correct
3 Correct 167 ms 12700 KB Output is correct
4 Correct 154 ms 12388 KB Output is correct
5 Incorrect 140 ms 11908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 10184 KB Output is correct
2 Correct 170 ms 12060 KB Output is correct
3 Correct 162 ms 12504 KB Output is correct
4 Correct 147 ms 11824 KB Output is correct
5 Incorrect 128 ms 11684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 10328 KB Output is correct
2 Correct 151 ms 11888 KB Output is correct
3 Correct 144 ms 11844 KB Output is correct
4 Correct 136 ms 11692 KB Output is correct
5 Correct 136 ms 11884 KB Output is correct
6 Correct 135 ms 11924 KB Output is correct

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 10320 KB Output is correct
2 Correct 139 ms 11940 KB Output is correct
3 Correct 134 ms 11944 KB Output is correct
4 Correct 154 ms 12124 KB Output is correct
5 Incorrect 145 ms 11992 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 10528 KB Output is correct
2 Correct 139 ms 11340 KB Output is correct
3 Correct 156 ms 12584 KB Output is correct
4 Correct 140 ms 11716 KB Output is correct
5 Incorrect 138 ms 12188 KB Output isn't correct
6 Halted 0 ms 0 KB -