oj.uz

Submission #91255

# Submission time Handle Problem Language Result Execution time Memory
91255 2018-12-26T17:50:34 Z tmwilliamlin168 Price List (POI13_cen) C++14
10 / 100
 114 ms 16788 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];
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;
	}
	d[k]=0;
	pq.push({0, k});
	while(pq.size()) {
		array<int, 2> u=pq.top();
		pq.pop();
		//cout << u[0] << " " << u[1] << endl;
		if(d[u[1]]<u[0])
			continue;
		//cout << u[0] << " " << u[1] << endl;
		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 : adj[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});
				}
			}
			adj[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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5108 KB Output is correct
3 Correct 5 ms 5184 KB Output is correct
4 Incorrect 6 ms 5188 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5264 KB Output is correct
2 Correct 5 ms 5340 KB Output is correct
3 Correct 6 ms 5340 KB Output is correct
4 Correct 5 ms 5340 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5356 KB Output is correct
2 Correct 6 ms 5356 KB Output is correct
3 Incorrect 6 ms 5372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6012 KB Output is correct
2 Correct 33 ms 6012 KB Output is correct
3 Incorrect 19 ms 6592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7972 KB Output is correct
2 Correct 22 ms 7972 KB Output is correct
3 Incorrect 43 ms 8552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9952 KB Output is correct
2 Correct 34 ms 9952 KB Output is correct
3 Incorrect 93 ms 12536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 12536 KB Output is correct
2 Correct 36 ms 12536 KB Output is correct
3 Incorrect 108 ms 14436 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 14436 KB Output is correct
2 Correct 46 ms 14436 KB Output is correct
3 Incorrect 114 ms 15400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 15400 KB Output is correct
2 Correct 59 ms 15400 KB Output is correct
3 Incorrect 98 ms 16344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16344 KB Output is correct
2 Correct 56 ms 16344 KB Output is correct
3 Incorrect 96 ms 16788 KB Output isn't correct
4 Halted 0 ms 0 KB -