oj.uz

Submission #91258

# Submission time Handle Problem Language Result Execution time Memory
91258 2018-12-26T18:18:54 Z tmwilliamlin168 Price List (POI13_cen) C++14
100 / 100
 170 ms 28768 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, m, k, a, b, eu[mxN], ev[mxN], qu[mxN], qt, d[mxN];
vector<int> adj[mxN], ts[mxN], adj2[mxN];
bool c[mxN];
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k >> a >> b, --k;
	for(int i=0; i<m; ++i) {
		cin >> eu[i] >> ev[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	memset(d, 0x3f, 4*n);
	if(b>=a) {
		qu[qt++]=k;
		d[k]=0;
		for(int qh=0; qh<n; ++qh) {
			int u=qu[qh];
			for(int e : adj[u]) {
				int v=u^eu[e]^ev[e];
				if(d[v]>d[u]+1) {
					qu[qt++]=v;
					d[v]=d[u]+1;
				}
			}
		}
		for(int i=0; i<n; ++i)
			cout << d[i]/2*min(2*a, b)+d[i]%2*a << "\n";
		return 0;
	}
	for(int i=0; i<n; ++i) {
		for(int e : adj[i])
			c[i^eu[e]^ev[e]]=1;
		for(int e1 : adj[i]) {
			int v=i^eu[e1]^ev[e1];
			if(array<int, 2>{adj[i].size(), i}<array<int, 2>{adj[v].size(), v})
				continue;
			for(int e2 : adj[v])
				if(c[v^eu[e2]^ev[e2]])
					ts[e1].push_back(v^eu[e2]^ev[e2]);
		}
		for(int e : adj[i])
			c[i^eu[e]^ev[e]]=0;
		adj2[i]=adj[i];
	}
	d[k]=0;
	pq.push({0, k});
	while(pq.size()) {
		array<int, 2> u=pq.top();
		pq.pop();
		if(d[u[1]]<u[0])
			continue;
		for(int e1 : adj[u[1]]) {
			int v=u[1]^eu[e1]^ev[e1];
			if(d[v]>u[0]+a) {
				d[v]=u[0]+a;
				pq.push({d[v], v});
			}
			c[u[1]]=1;
			for(int t : ts[e1])
				c[t]=1;
			vector<int> na;
			for(int e2 : adj2[v]) {
				int w=v^eu[e2]^ev[e2];
				if(c[w]) {
					na.push_back(e2);
					continue;
				}
				if(d[w]>u[0]+b) {
					d[w]=u[0]+b;
					pq.push({d[w], w});
				}
			}
			adj2[v]=na;
			c[u[1]]=0;
			for(int t : ts[e1])
				c[t]=0;
		}
	}
	for(int i=0; i<n; ++i)
		cout << d[i] << "\n";
}

Compilation message

cen.cpp: In function 'int main()':
cen.cpp:43:32: warning: narrowing conversion of 'adj[i].std::vector<int>::size()' from 'std::vector<int>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
    if(array<int, 2>{adj[i].size(), i}<array<int, 2>{adj[v].size(), v})
                     ~~~~~~~~~~~^~
cen.cpp:43:64: warning: narrowing conversion of 'adj[v].std::vector<int>::size()' from 'std::vector<int>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
    if(array<int, 2>{adj[i].size(), i}<array<int, 2>{adj[v].size(), v})
                                                     ~~~~~~~~~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 7 ms 7432 KB Output is correct
4 Correct 8 ms 7448 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7448 KB Output is correct
2 Correct 7 ms 7492 KB Output is correct
3 Correct 7 ms 7508 KB Output is correct
4 Correct 7 ms 7584 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8684 KB Output is correct
2 Correct 12 ms 8684 KB Output is correct
3 Correct 24 ms 9084 KB Output is correct
4 Correct 15 ms 9084 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11644 KB Output is correct
2 Correct 25 ms 11644 KB Output is correct
3 Correct 54 ms 11644 KB Output is correct
4 Correct 34 ms 11644 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 14712 KB Output is correct
2 Correct 43 ms 14712 KB Output is correct
3 Correct 148 ms 16256 KB Output is correct
4 Correct 55 ms 16256 KB Output is correct
5 Correct 92 ms 17376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 17984 KB Output is correct
2 Correct 39 ms 17984 KB Output is correct
3 Correct 162 ms 19020 KB Output is correct
4 Correct 64 ms 19020 KB Output is correct
5 Correct 108 ms 20416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 21392 KB Output is correct
2 Correct 51 ms 21392 KB Output is correct
3 Correct 161 ms 21392 KB Output is correct
4 Correct 55 ms 21392 KB Output is correct
5 Correct 140 ms 23296 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 23296 KB Output is correct
2 Correct 63 ms 23296 KB Output is correct
3 Correct 170 ms 23460 KB Output is correct
4 Correct 51 ms 23460 KB Output is correct
5 Correct 106 ms 26068 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 26068 KB Output is correct
2 Correct 63 ms 26068 KB Output is correct
3 Correct 155 ms 26068 KB Output is correct
4 Correct 60 ms 26068 KB Output is correct
5 Correct 132 ms 28768 KB Output is correct