oj.uz

답안 #299178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299178 2020-09-14T14:27:59 Z quanmcvn Birmingham (COCI20_birmingham) C++14
15 / 70
 184 ms 17268 KB 
#include <bits/stdc++.h>
#define fff "main"
#define For(i,a,b) for (auto i = a; i < b; ++i)
#define pb push_back
#define en cout << '\n';
using namespace std;

typedef signed long long int ll;
typedef std::vector<ll> vll;

vector<pair<ll,ll> > ct[100001];
ll d[100001];
ll know_first[100001];
ll n,m,q,k;

void spf(){
	priority_queue<pair<ll, ll >, vector<pair<ll,ll > >, greater<pair<ll, ll > > >pq;
	For (i,1,n+1) {
		d[i] = 99999999999;
		if (know_first[i]){
			d[i] = 0;
			pq.push({0,i});
		}
	}
	while (pq.size()) {
		ll u = pq.top().second;
		ll du = pq.top().first;
		pq.pop();
		if (du > d[u]) continue;
		for (ll i = 0; i < ct[u].size(); i++) {
			ll v = ct[u][i].second;
			ll w = ct[u][i].first;
			if (d[v] > du + w) {
				d[v] = du + w;
				pq.push({d[v], v});
			}
		}
	}
}

int main()
{
//	if (fopen(fff".inp","r")) {
//		freopen(fff".inp","r",stdin);
//		freopen(fff".out","w",stdout);
//	}
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q >> k;
	while (q--) {
		ll f;
		cin >> f;
		know_first[f] = 1;
	}
	while (m--){
		ll u, v; cin >> u >> v;
		ct[u].pb({1,v});
		ct[v].pb({1,u});
	}
	spf();
	For (i,1,n+1){
		cout << (d[i] + k - 1) / k << ' ';
	}
    return 0;
}

Compilation message

birmingham.cpp: In function 'void spf()':
birmingham.cpp:30:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (ll i = 0; i < ct[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 2 ms 2752 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2720 KB Output is correct
4 Correct 2 ms 2720 KB Output is correct

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 151 ms 16116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 163 ms 17268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 163 ms 16440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 143 ms 15324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 15476 KB Output is correct
2 Incorrect 142 ms 16240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 139 ms 15476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 15988 KB Output isn't correct
2 Halted 0 ms 0 KB -