oj.uz

Submission #246479

# Submission time Handle Problem Language Result Execution time Memory
246479 2020-07-09T11:52:19 Z arnold518 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 11224 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 = 200;
const int MAXM = 5e4;
const ll INF = 1e18;

struct Edge
{
	int u, v, p; ll c, d;
};

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

int N, M;
vector<Edge> adj[MAXN+10], radj[MAXN+10];
Edge E[MAXM+10];
ll D1[MAXN+10], DR1[MAXN+10], D2[MAXN+10], DR2[MAXN+10], D[MAXN+10];
int T1[MAXM+10], TR1[MAXM+10], T2[MAXM+10], TR2[MAXM+10], T[MAXM+10];
ll V[MAXM+10];

void dijk(int S, vector<Edge> *aadj, ll *DD, int *TT)
{
	int i, j;

	priority_queue<Queue> PQ;
	for(i=1; i<=N; i++) DD[i]=INF;
	for(i=1; i<=M; i++) TT[i]=0;
	PQ.push({S, -1, 0});
	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(DD[now.u]<=now.w) continue;
		DD[now.u]=now.w;
		if(now.p>0) TT[now.p]=1;
		for(auto nxt : aadj[now.u]) PQ.push({nxt.v, nxt.p, now.w+nxt.c});
	}
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++)
	{
		int u, v, c, d;
		scanf("%d%d%d%d", &u, &v, &c, &d);

		E[i]={u, v, i, c, d};
		adj[u].push_back({u, v, i, c, d});
		radj[v].push_back({v, u, i, c, d});
	}

	dijk(1, adj, D1, T1);
	dijk(1, radj, DR1, TR1);

	dijk(N, adj, D2, T2);
	dijk(N, radj, DR2, TR2);

	for(i=1; i<=M; i++) V[i]+=E[i].d;
	for(i=1; i<=M; i++)
	{
		if(T1[i])
		{
			for(auto &it : adj[E[i].u]) if(it.p==i) it.c=1e16;
			adj[E[i].v].push_back({E[i].v, E[i].u, i, E[i].c, E[i].d});
			dijk(1, adj, D, T);
			V[i]+=D[N];
			adj[E[i].v].pop_back();
			for(auto &it : adj[E[i].u]) if(it.p==i) it.c=E[i].c;
		}
		else
		{
			ll t=D1[N];
			t=min(t, D1[E[i].v]+DR2[E[i].u]+E[i].c);
			V[i]+=t;
		}
	}

	for(i=1; i<=M; i++)
	{
		if(T2[i])
		{
			for(auto &it : adj[E[i].u]) if(it.p==i) it.c=1e16;
			adj[E[i].v].push_back({E[i].v, E[i].u, i, E[i].c, E[i].d});
			dijk(N, adj, D, T);
			V[i]+=D[1];

			adj[E[i].v].pop_back();
			for(auto &it : adj[E[i].u]) if(it.p==i) it.c=E[i].c;
		}
		else
		{
			ll t=D2[1];
			t=min(t, D2[E[i].v]+DR1[E[i].u]+E[i].c);
			V[i]+=t;
		}
	}

	ll ans=INF;
	ans=min(ans, D1[N]+D2[1]);
	for(i=1; i<=M; i++) ans=min(ans, V[i]);
	if(ans==INF) ans=-1;
	printf("%lld\n", ans);
}

Compilation message

ho_t4.cpp: In function 'void dijk(int, std::vector<Edge>*, ll*, int*)':
ho_t4.cpp:32:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:50:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
ho_t4.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &u, &v, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 40 ms 640 KB Output is correct
4 Correct 42 ms 632 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 919 ms 8800 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Execution timed out 1080 ms 11008 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 40 ms 640 KB Output is correct
4 Correct 42 ms 632 KB Output is correct
5 Correct 12 ms 640 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -