oj.uz

Submission #244418

# Submission time Handle Problem Language Result Execution time Memory
244418 2020-07-04T03:15:23 Z arnold518 Price List (POI13_cen) C++14
40 / 100
 4000 ms 16752 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int INF = 2e9;

int N, M, K, A, B;
pii E[MAXN+10];
vector<int> adj[MAXN/2+10], adj2[MAXN/2+10];

int dist[MAXN+10][2];
bool vis[MAXN+10][2];
int ans[MAXN/2+10];

struct Queue
{
	int v, w, p;
	bool operator < (const Queue &p) const { return w>p.w; }
};

bool f(int u, int v) { return binary_search(adj2[u].begin(), adj2[u].end(), v); }

int main()
{
	int i, j;

	scanf("%d%d%d%d%d", &N, &M, &K, &A, &B);
	for(i=1; i<=M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E[i*2-1]={u, v};
		E[i*2]={v, u};
		adj[u].push_back(i*2-1);
		adj[v].push_back(i*2);
		adj2[u].push_back(v);
		adj2[v].push_back(u);
	}
	for(i=1; i<=N; i++) sort(adj2[i].begin(), adj2[i].end());
	for(i=1; i<=2*M; i++) dist[i][0]=dist[i][1]=INF;

	priority_queue<Queue> PQ;
	for(auto it : adj[K])
	{
		PQ.push({it, 2*A, 0}); dist[it][0]=2*A;
		PQ.push({it, B, 1}); dist[it][1]=B;
	}
	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(vis[now.v][now.p]) continue;
		if(dist[now.v][now.p]!=now.w) continue;
		vis[now.v][now.p]=1;

		if(now.p==1)
		{
			for(auto nxt : adj[E[now.v].second])
			{
				if(f(E[now.v].first, E[nxt].second)) continue;
				if(dist[nxt][0]>now.w+B && !vis[nxt][0]) PQ.push({nxt, now.w+B, 0}), dist[nxt][0]=now.w+B;
			}
		}
		else
		{
			for(auto nxt : adj[E[now.v].second])
			{
				if(dist[nxt][0]>now.w+2*A && !vis[nxt][0]) PQ.push({nxt, now.w+2*A, 0}), dist[nxt][0]=now.w+2*A;
				if(dist[nxt][1]>now.w+B && !vis[nxt][1]) PQ.push({nxt, now.w+B, 1}), dist[nxt][1]=now.w+B;
			}
		}
	}

	for(i=1; i<=N; i++) if(i!=K) ans[i]=INF;
	for(i=1; i<=2*M; i++) ans[E[i].second]=min(ans[E[i].second], dist[i][0]);

	for(i=1; i<=N; i++) printf("%lld\n", ans[i]/2);
}

Compilation message

cen.cpp: In function 'int main()':
cen.cpp:80:47: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  for(i=1; i<=N; i++) printf("%lld\n", ans[i]/2);
                                       ~~~~~~~~^
cen.cpp:29:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
cen.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &N, &M, &K, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cen.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 10 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 6584 KB Output is correct
2 Correct 84 ms 6584 KB Output is correct
3 Correct 32 ms 6520 KB Output is correct
4 Correct 25 ms 6656 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2357 ms 10096 KB Output is correct
2 Execution timed out 4098 ms 9852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2891 ms 13808 KB Output is correct
2 Correct 1610 ms 12384 KB Output is correct
3 Correct 193 ms 13688 KB Output is correct
4 Correct 191 ms 13688 KB Output is correct
5 Execution timed out 4057 ms 14184 KB Time limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4093 ms 14196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4077 ms 15576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1435 ms 15732 KB Output is correct
2 Correct 1364 ms 15856 KB Output is correct
3 Correct 197 ms 14840 KB Output is correct
4 Correct 146 ms 13688 KB Output is correct
5 Execution timed out 4073 ms 16752 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 15992 KB Output is correct
2 Correct 123 ms 15992 KB Output is correct
3 Correct 252 ms 15996 KB Output is correct
4 Correct 157 ms 13688 KB Output is correct
5 Execution timed out 4097 ms 16616 KB Time limit exceeded