oj.uz

Submission #299192

# Submission time Handle Problem Language Result Execution time Memory
299192 2020-09-14T14:38:36 Z quanmcvn Birmingham (COCI20_birmingham) C++14
70 / 70
 522 ms 18800 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 (auto f : ct[u]){
			ll v = f.second;
			ll w = f.first;
			if (d[v] > du + w) {
				d[v] = du + w;
				pq.push({d[v], v});
			}
		}
	}
}

ll sum_to(const ll &x){
	return (x * (x + 1)) / 2;
}

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();
	vll check;
	for (ll i = 0; sum_to(i) <= n / k; ++i){
		check.pb(sum_to(i) * k);
	}
	For (i,1,n+1){
		cout << lower_bound(check.begin(),check.end(),d[i]) - check.begin() << ' ';
	}
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 14580 KB Output is correct
2 Correct 179 ms 17268 KB Output is correct
3 Correct 159 ms 18288 KB Output is correct
4 Correct 136 ms 14832 KB Output is correct
5 Correct 150 ms 15348 KB Output is correct
6 Correct 179 ms 18800 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 15476 KB Output is correct
2 Correct 222 ms 17008 KB Output is correct
3 Correct 178 ms 17784 KB Output is correct
4 Correct 178 ms 17648 KB Output is correct
5 Correct 182 ms 16884 KB Output is correct
6 Correct 171 ms 17008 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 14704 KB Output is correct
2 Correct 177 ms 17524 KB Output is correct
3 Correct 170 ms 18160 KB Output is correct
4 Correct 161 ms 17520 KB Output is correct
5 Correct 151 ms 15860 KB Output is correct
6 Correct 147 ms 17136 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 13808 KB Output is correct
2 Correct 168 ms 16752 KB Output is correct
3 Correct 236 ms 17908 KB Output is correct
4 Correct 235 ms 16240 KB Output is correct
5 Correct 188 ms 15196 KB Output is correct
6 Correct 156 ms 16872 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 13940 KB Output is correct
2 Correct 177 ms 14576 KB Output is correct
3 Correct 164 ms 16624 KB Output is correct
4 Correct 162 ms 15896 KB Output is correct
5 Correct 179 ms 16164 KB Output is correct
6 Correct 153 ms 16632 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 13940 KB Output is correct
2 Correct 188 ms 16368 KB Output is correct
3 Correct 146 ms 16108 KB Output is correct
4 Correct 169 ms 16800 KB Output is correct
5 Correct 154 ms 15856 KB Output is correct
6 Correct 137 ms 17264 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 14324 KB Output is correct
2 Correct 149 ms 14964 KB Output is correct
3 Correct 228 ms 18164 KB Output is correct
4 Correct 334 ms 15856 KB Output is correct
5 Correct 522 ms 16368 KB Output is correct
6 Correct 190 ms 18668 KB Output is correct