oj.uz

Submission #314702

# Submission time Handle Problem Language Result Execution time Memory
314702 2020-10-20T23:08:27 Z aZvezda Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 6008 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e12 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const ll MAX_N = 2e2 + 10, MAX_W = 1e5 + 10;
vector<pair<pair<ll, ll>, pair<ll, ll> > > edges;
bool off[MAX_W];
vector<pair<pair<ll, ll>, ll> > g[MAX_N];
ll dist[4][MAX_N];
ll n, m;

void dij(ll ind, ll start) {
	for(ll i = 0; i < MAX_N; i ++) {
		dist[ind][i] = mod;
	}
	priority_queue<pair<ll, ll> > pq;
	pq.push({0, start});
	dist[ind][start] = 0;
	while(!pq.empty()) {
		auto curr = pq.top(); pq.pop();
		curr.first *= -1;
		for(auto it : g[curr.second]) {
			if(off[it.second]) {continue;}
			ll nxt = it.first.first;
			if(dist[ind][nxt] > curr.first + it.first.second) {
				dist[ind][nxt] = curr.first + it.first.second;
				pq.push({-dist[ind][nxt], nxt});
			}	
		}
	}
	return;
	cout << "Started from " << start << endl;
	for(ll i = 1; i <= n; i ++) {
		cout << dist[ind][i] << " ";
	}
	cout << endl;
} 

ll distFull[MAX_N][MAX_N];

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for(int i = 0; i < MAX_N; i ++) {
		for(int j = 0; j < MAX_N; j ++) {
			distFull[i][j] = mod;
		}
	}
	
	cin >> n >> m;
	edges.resize(m);
	for(ll i = 0; i < m; i ++) {
		cin >> edges[i];
		off[2 * i] = false;
		off[2 * i + 1] = true;
		g[edges[i].first.first].push_back({{edges[i].first.second, edges[i].second.first}, 2 * i}); 
		g[edges[i].first.second].push_back({{edges[i].first.first, edges[i].second.first}, 2 * i + 1}); 
		chkmin(distFull[edges[i].first.first][edges[i].first.second], edges[i].second.first);
	}
	for(int k = 1; k <= n; k ++) {
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= n; j ++) {
				chkmin(distFull[i][j], distFull[i][k] + distFull[k][j]);
			}
		}
	}
	dij(0, 1);
	dij(1, n);
	ll ret = dist[0][n] + dist[1][1];
	for(ll i = 0; i < m; i ++) {
		int u = edges[i].first.first, v = edges[i].first.second, cost = edges[i].second.first;
		if(min(distFull[1][v] + cost + distFull[u][n], distFull[1][n]) + min(distFull[n][v] + cost + distFull[u][1], distFull[n][1]) > ret) {continue;}
		off[2 * i] = true;
		off[2 * i + 1] = false;
		dij(2, 1);
		dij(3, n);
		chkmin(ret, edges[i].second.second + dist[2][n] + dist[3][1]);
		off[2 * i] = false;
		off[2 * i + 1] = true;
	}
	if(ret < mod) {
		cout << ret << endl;
	} else {
		cout << -1 << endl;
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 768 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 87 ms 768 KB Output is correct
4 Correct 97 ms 768 KB Output is correct
5 Correct 35 ms 768 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Incorrect 1 ms 768 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 768 KB Output is correct
2 Correct 11 ms 768 KB Output is correct
3 Execution timed out 1086 ms 4608 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 768 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 87 ms 768 KB Output is correct
4 Correct 97 ms 768 KB Output is correct
5 Correct 35 ms 768 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Incorrect 1 ms 768 KB Output isn't correct
10 Halted 0 ms 0 KB -