oj.uz

Submission #361213

# Submission time Handle Problem Language Result Execution time Memory
361213 2021-01-28T17:24:27 Z HoneyBadger Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 8556 KB 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <algorithm>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <ctime>
#include <chrono>


/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
*/


#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << x << endl;
#else
    #define dbg(x)
#endif

#define int long long
#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a, b) for (int i = a; i < b; i++)
#define fj(a, b) for (int j = a; j < b; j++)
#define fk(a, b) for (int k = a; k < b; k++)
#define fi1(a, b) for (int i = a - 1; i >= b; i--)
#define fj1(a, b) for (int j = a - 1; j >= b; j--)
#define fk1(a, b) for (int k = a - 1; k >= b; k--)
#define fx(x, a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; }

ostream& operator << (ostream &out, const vector<int> &b) {
    for (auto k : b) out << k << ' ';
    return out;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 200010;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
vi g[MX];
int c[MX];
int from[MX];
int to[MX];
int dist[MX];

int dij(int s, int t, int ban) {
	if (ban != -1) {
		g[to[ban]].pb(m);
		from[m] = to[ban];
		to[m] = from[ban];
		c[m] = c[ban];
	}
	fill(dist, dist + n, BIG);
	dist[s] = 0;
	priority_queue<pii> q;
	q.push({0, s});
	while (q.size()) {
		auto[d, v] = q.top();
		q.pop();
		d *= -1;
		if (dist[v] < d) continue;
		fx(id, g[v]) {
			if (id == ban) continue;
			if (dist[to[id]] >  d + c[id]) {
				dist[to[id]] = d + c[id];
				q.push({-dist[to[id]], to[id]});
			}
		}
	}
	if (ban != -1)
		g[to[ban]].ppb;
	return dist[t];
}


int d[MX];

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

   
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
    	int u;
    	cin >> u >> to[i] >> c[i] >> d[i];
    	--u, --to[i];
    	g[u].pb(i);
    	from[i] = u;
	}
	int ans = BIG;
	for (int ban = -1; ban < m; ++ban) {
		int res = dij(0, n - 1, ban) + dij(n - 1, 0, ban);
		if (ban != -1) res += d[ban];
		mine(ans, res);
	}
	cout << (ans == BIG ? -1 : ans) << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 52 ms 5248 KB Output is correct
4 Correct 57 ms 5100 KB Output is correct
5 Correct 20 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5112 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 7 ms 5100 KB Output is correct
10 Correct 80 ms 5100 KB Output is correct
11 Correct 78 ms 5100 KB Output is correct
12 Correct 91 ms 5100 KB Output is correct
13 Correct 28 ms 5100 KB Output is correct
14 Correct 37 ms 5100 KB Output is correct
15 Correct 32 ms 5100 KB Output is correct
16 Correct 37 ms 5100 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Execution timed out 1094 ms 7532 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 52 ms 5248 KB Output is correct
4 Correct 57 ms 5100 KB Output is correct
5 Correct 20 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5112 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 7 ms 5100 KB Output is correct
10 Correct 80 ms 5100 KB Output is correct
11 Correct 78 ms 5100 KB Output is correct
12 Correct 91 ms 5100 KB Output is correct
13 Correct 28 ms 5100 KB Output is correct
14 Correct 37 ms 5100 KB Output is correct
15 Correct 32 ms 5100 KB Output is correct
16 Correct 37 ms 5100 KB Output is correct
17 Execution timed out 1079 ms 8556 KB Time limit exceeded
18 Halted 0 ms 0 KB -