oj.uz

Submission #244530

# Submission time Handle Problem Language Result Execution time Memory
244530 2020-07-04T09:17:47 Z arnold518 Price List (POI13_cen) C++14
90 / 100
 4000 ms 15448 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 ll INF = 1e15;

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

ll dist1[MAXN+10], dist2[MAXN+10];
bool vis1[MAXN+10], vis2[MAXN+10];

struct Queue
{
	int v, w, p;
};

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);
		adj[u].push_back(v);
		adj[v].push_back(u);
		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<=N; i++) dist1[i]=dist2[i]=INF;
	queue<Queue> Q;
	Q.push({K, 0, 0}); vis1[K]=1; dist1[K]=0;
	while(!Q.empty())
	{
		Queue now=Q.front(); Q.pop();
		for(auto nxt : adj[now.v])
		{
			if(vis1[nxt]) continue;
			dist1[nxt]=now.w+1;
			vis1[nxt]=true;
			Q.push({nxt, now.w+1, 0});
		}
	}

	Q.push({K, 0, -1}); vis2[K]=1; dist2[K]=0;
	while(!Q.empty())
	{
		Queue now=Q.front(); Q.pop();
		if(now.p==-1)
		{
			for(auto nxt : adj[now.v])
			{
				Q.push({nxt, now.w, now.v});
			}
		}
		else
		{
			for(auto &nxt : adj[now.v])
			{
				if(vis2[nxt]) continue;
				if(f(nxt, now.p)) continue;
				Q.push({nxt, now.w+1, -1});
				vis2[nxt]=true;
				dist2[nxt]=now.w+1;
				//nxt=-1;
			}
			for(i=adj[now.v].size()-1; i>=0; i--)
			{
				if(adj[now.v][i]!=-1) continue;
				swap(adj[now.v][i], adj[now.v].back());
				adj[now.v].pop_back();
			}
		}
	}

	for(i=1; i<=N; i++)
	{
		if(dist1[i]%2==0) printf("%lld\n", min(dist1[i]*A, dist1[i]/2*B));
		else printf("%lld\n", min({dist1[i]*A, dist1[i]/2*B+A, dist2[i]*B}));
	}
}

Compilation message

cen.cpp: In function 'int main()':
cen.cpp:27:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
cen.cpp:29: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:33: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 7 ms 4992 KB Output is correct
3 Correct 8 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 7 ms 4992 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6136 KB Output is correct
2 Correct 33 ms 6144 KB Output is correct
3 Correct 21 ms 6144 KB Output is correct
4 Correct 21 ms 6272 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 8824 KB Output is correct
2 Correct 748 ms 8952 KB Output is correct
3 Correct 42 ms 7672 KB Output is correct
4 Correct 60 ms 9208 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 11608 KB Output is correct
2 Correct 302 ms 10744 KB Output is correct
3 Correct 112 ms 11384 KB Output is correct
4 Correct 128 ms 12024 KB Output is correct
5 Correct 2261 ms 13168 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 12840 KB Output is correct
2 Correct 115 ms 10872 KB Output is correct
3 Correct 128 ms 11520 KB Output is correct
4 Correct 120 ms 12128 KB Output is correct
5 Correct 2922 ms 14024 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 14200 KB Output is correct
2 Correct 291 ms 13176 KB Output is correct
3 Correct 142 ms 12152 KB Output is correct
4 Correct 121 ms 12152 KB Output is correct
5 Correct 3397 ms 14960 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 13432 KB Output is correct
2 Correct 285 ms 13560 KB Output is correct
3 Correct 138 ms 12536 KB Output is correct
4 Correct 119 ms 12152 KB Output is correct
5 Correct 3659 ms 15448 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 13816 KB Output is correct
2 Correct 118 ms 13816 KB Output is correct
3 Correct 157 ms 13892 KB Output is correct
4 Correct 125 ms 12280 KB Output is correct
5 Execution timed out 4062 ms 14960 KB Time limit exceeded