oj.uz

Submission #335586

# Submission time Handle Problem Language Result Execution time Memory
335586 2020-12-13T08:45:50 Z jbroeksteeg Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 607 ms 35044 KB 
#include <iostream>
#include <climits>
#include <iomanip>
#include <math.h>
#include <numeric>
#include <cassert>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <vector>
#include <array>
#include <memory>

#define IN(a,b) (a.find(b) != a.end())
#define p(a,b) make_pair(a,b)
#define readVec(a) for (int64_t __i = 0; __i<(int64_t)a.size();__i++){cin>>a[__i];}

// jimjam

template<typename T>
void pMin(T &a, T b) {if (b<a){a=b;}}
template<typename T>
void pMax(T &a, T b) {if (b>a){a=b;}}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& c);
template<typename A, typename B>
std::ostream& operator<<(std::ostream& os, const std::pair<A,B>& c) {std::cout << "(" << c.first << ", " << c.second << ")";return os;}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& c) {
	if (c.size() == 0) {os << "{}"; return os;}
	os << "{" << c[0];
	for (int64_t i = 1; i < (int64_t)c.size(); i++) {os <<", "<<c[i];}
	os << "}";
	return os;
}

const int64_t inf = 2e18;

using namespace std;

int64_t n,m,s,t,u,v;

vector<vector<pair<int64_t,int64_t>>> adj;
vector<vector<int64_t>> backtrack;
vector<vector<int64_t>> dag;

vector<bool> topoSeen;
set<int> good;
vector<int> topoOrder;
void toposort(int c) {
	topoSeen[c]=true;
	for( int i: dag[c] ) {
		if (!topoSeen[i]&&good.count(i)) toposort(i);
	}
	topoOrder.push_back(c);
}
void dijkstra(int64_t start, vector<int64_t>& seen) {
	priority_queue<pair<int64_t,int64_t>,vector<pair<int64_t,int64_t>>,greater<pair<int64_t,int64_t>>> pq;
	pq.push({0,start});
	seen[start]=0;
	while (pq.size()) {
		auto curr = pq.top(); pq.pop();
		for (pair<int64_t,int64_t> pi: adj[curr.second]) {
			if (pi.second+curr.first<seen[pi.first]) {
				seen[pi.first]=pi.second+curr.first;
				pq.push({seen[pi.first],pi.first});
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	// s t get nuked
	// route from u to v
	cin >> n >> m >> s >> t >> u >> v;
	adj.resize(n+1);
	topoSeen.resize(n+1);
	backtrack.resize(n+1);
	dag.resize(n+1);
	for (int64_t i = 0; i < m; i++) {
		int64_t a, b, w; cin >> a >> b >> w;
		adj[a].push_back({b,w});
		adj[b].push_back({a,w});
	}
	priority_queue<pair<int64_t,int64_t>,vector<pair<int64_t,int64_t>>,greater<pair<int64_t,int64_t>>> pq;
	vector<int64_t> dijkstraSeen(n+1,inf);
	dijkstraSeen[s]=0;
	pq.push({0, s});
	while (pq.size()) {
		auto curr = pq.top();
		pq.pop();
		for (auto pi: adj[curr.second]) {
			if (pi.second+curr.first<dijkstraSeen[pi.first]) {
				backtrack[pi.first].clear();
				dijkstraSeen[pi.first]=pi.second+curr.first;
				pq.push({dijkstraSeen[pi.first],pi.first});
			}
			if (pi.second+curr.first<=dijkstraSeen[pi.first]) {
				backtrack[pi.first].push_back(curr.second);
			}
		}
	}
	vector<int64_t> distFromU(n+1,inf), distFromV(n+1,inf);
	dijkstra(u,distFromU);
	dijkstra(v,distFromV);
	for (int i = 1; i <= n; i++) adj[i].clear();
	for (int64_t i = 1; i <= n; i++) {
		for (int64_t j: backtrack[i]) {
			dag[j].push_back(i);
		}
	}
	priority_queue<pair<int64_t,int64_t>> pq2; // goes through DAG backwards
	vector<int64_t> minUBehind(n+1,inf), minVBehind(n+1,inf);
	for (int64_t i = 1; i <= n; i++) {
		minUBehind[i]=distFromU[i];
		minVBehind[i]=distFromV[i];
	}

	queue<int> bfs; // bfs to find good edges
	vector<int> bfsSeen(n+1);
	bfs.push(t);
	while (bfs.size()) {
		good.insert(bfs.front());
		for (int i: backtrack[bfs.front()]) {
			if (!bfsSeen[i]) {
				bfs.push(i);
				bfsSeen[i]=true;
			}
		}
		bfs.pop();
	}
	int64_t ans=inf;
	for (int i: good) {
		if (!topoSeen[i]) toposort(i);
	}
	reverse(topoOrder.begin(),topoOrder.end());
	for( int currInd: topoOrder) {
		pMin(ans, minUBehind[currInd] + distFromV[currInd]);
		pMin(ans, minVBehind[currInd] + distFromU[currInd]);
		
		for (int64_t i: dag[currInd]) {
			pMin(minUBehind[i],minUBehind[currInd]);
			pMin(minVBehind[i],minVBehind[currInd]);
		}
	}
	cout << min(ans,distFromV[u]) << endl;
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 27792 KB Output is correct
2 Correct 488 ms 29968 KB Output is correct
3 Correct 533 ms 33748 KB Output is correct
4 Correct 397 ms 28396 KB Output is correct
5 Correct 524 ms 31832 KB Output is correct
6 Correct 422 ms 27680 KB Output is correct
7 Correct 519 ms 32292 KB Output is correct
8 Correct 523 ms 31820 KB Output is correct
9 Correct 428 ms 27504 KB Output is correct
10 Correct 346 ms 27092 KB Output is correct
11 Correct 228 ms 27116 KB Output is correct
12 Correct 430 ms 28112 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 30036 KB Output is correct
2 Correct 491 ms 30372 KB Output is correct
3 Correct 482 ms 30404 KB Output is correct
4 Correct 503 ms 30160 KB Output is correct
5 Correct 503 ms 30372 KB Output is correct
6 Correct 505 ms 33140 KB Output is correct
7 Correct 541 ms 34892 KB Output is correct
8 Correct 494 ms 30124 KB Output is correct
9 Correct 505 ms 30876 KB Output is correct
10 Correct 479 ms 30560 KB Output is correct
11 Correct 259 ms 28396 KB Output is correct
12 Correct 508 ms 33928 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1900 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 17 ms 3436 KB Output is correct
5 Correct 8 ms 1772 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 8 ms 1772 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 27792 KB Output is correct
2 Correct 488 ms 29968 KB Output is correct
3 Correct 533 ms 33748 KB Output is correct
4 Correct 397 ms 28396 KB Output is correct
5 Correct 524 ms 31832 KB Output is correct
6 Correct 422 ms 27680 KB Output is correct
7 Correct 519 ms 32292 KB Output is correct
8 Correct 523 ms 31820 KB Output is correct
9 Correct 428 ms 27504 KB Output is correct
10 Correct 346 ms 27092 KB Output is correct
11 Correct 228 ms 27116 KB Output is correct
12 Correct 430 ms 28112 KB Output is correct
13 Correct 483 ms 30036 KB Output is correct
14 Correct 491 ms 30372 KB Output is correct
15 Correct 482 ms 30404 KB Output is correct
16 Correct 503 ms 30160 KB Output is correct
17 Correct 503 ms 30372 KB Output is correct
18 Correct 505 ms 33140 KB Output is correct
19 Correct 541 ms 34892 KB Output is correct
20 Correct 494 ms 30124 KB Output is correct
21 Correct 505 ms 30876 KB Output is correct
22 Correct 479 ms 30560 KB Output is correct
23 Correct 259 ms 28396 KB Output is correct
24 Correct 508 ms 33928 KB Output is correct
25 Correct 9 ms 1900 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 17 ms 3436 KB Output is correct
29 Correct 8 ms 1772 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 2 ms 620 KB Output is correct
33 Correct 1 ms 492 KB Output is correct
34 Correct 8 ms 1772 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 1 ms 492 KB Output is correct
39 Correct 1 ms 492 KB Output is correct
40 Correct 384 ms 26940 KB Output is correct
41 Correct 393 ms 27280 KB Output is correct
42 Correct 403 ms 27336 KB Output is correct
43 Correct 332 ms 30312 KB Output is correct
44 Correct 328 ms 30576 KB Output is correct
45 Correct 596 ms 34884 KB Output is correct
46 Correct 555 ms 35044 KB Output is correct
47 Correct 416 ms 29136 KB Output is correct
48 Correct 343 ms 29160 KB Output is correct
49 Correct 358 ms 28876 KB Output is correct
50 Correct 543 ms 33880 KB Output is correct
51 Correct 607 ms 35024 KB Output is correct