oj.uz

Submission #380285

# Submission time Handle Problem Language Result Execution time Memory
380285 2021-03-20T20:45:49 Z ignaciocanta Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 1492 ms 262144 KB 
#include <bits/stdc++.h>
//#include "crocodile.h"
 
using namespace std;
 
using tint = long long;
using ld = long double;
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
using pi = pair<int,int>;
using pl = pair<tint,tint>;
using vi = vector<int>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vl = vector<tint>;
using vb = vector<bool>;
 
#define pb push_back
#define pf push_front
#define rsz resize
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sz(x) (int)(x).size()
#define ins insert
 
#define f first
#define s second
#define mp make_pair
 
#define DBG(x) cerr << #x << " = " << x << endl;
 
const int MOD = 1e9+7;
const tint mod = 998244353;
const int MX = 1e5+5;
const tint INF = 1e18; 
const int inf = 2e9;
const ld PI = acos(ld(-1)); 
const ld eps = 1e-5;
 
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
 
template<class T> void remDup(vector<T> &v){ 
    sort(all(v)); v.erase(unique(all(v)),end(v));
}
 
template<class T> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; 
} 
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; 
}
 
bool valid(int x, int y, int n, int m){
    return (0<=x && x<n && 0<=y && y<m);
}
 
int cdiv(int a, int b) { return a/b+((a^b)>0&&a%b); } //redondea p arriba
int fdiv(int a, int b) { return a/b-((a^b)<0&&a%b); } //redondea p abajo
 
void NACHO(string name = ""){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

vpi adj[MX];
vi dag[MX], gad[MX];
tint dS[MX], dT[MX], dU[MX], dV[MX], dpU[MX], dpV[MX], dpUU[MX], dpVV[MX];
bool vis[MX];
int n;

void dijkstra(int node, tint a[]){
	F0R(i, n) vis[i] = 0, a[i] = INF;
	a[node] = 0;
	priority_queue<pi, vpi, greater<pi>> q;
	q.push(mp(0, node));
	while(sz(q)){
		auto u = q.top().s; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		trav(v, adj[u]){
			if(a[u]+v.s < a[v.f]){
				a[v.f] = a[u]+v.s;
				q.push(mp(a[v.f], v.f));
			}
		}
	}
}

vi ord;

void dfs(int node){
	trav(u, dag[node]){
		dfs(u);
	}
	ord.pb(node);
}

int main(){
	NACHO();
	int m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	--s, --t, --u, --v;
	F0R(i, m){
		int a, b, c; cin >> a >> b >> c;
		--a, --b;
		adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c));
	}
	dijkstra(s, dS); dijkstra(t, dT); dijkstra(u, dU); dijkstra(v, dV);
	F0R(i, n){
		dpU[i] = INF/2; dpV[i] = INF/2;
		dpUU[i] = INF/2; dpVV[i] = INF/2;
		trav(u, adj[i]){
			if(dS[i]+u.s+dT[u.f] == dT[s]) dag[i].pb(u.f), gad[u.f].pb(i);
		}
	}
	dpU[s] = dU[s]; dpV[s] = dV[s];
	dfs(s);
	reverse(all(ord));
	F0R(i, sz(ord)){
		trav(a, dag[ord[i]]){
			dpU[a] = dU[a];
			ckmin(dpU[a], dpU[ord[i]]);
			dpV[a] = dV[a];
			ckmin(dpV[a], dpV[ord[i]]);
		}
	}
	reverse(all(ord));
	dpUU[t] = dU[t], dpVV[t] = dV[t];
	F0R(i, sz(ord)){
		trav(a, gad[ord[i]]){
			dpUU[a] = dU[a];
			ckmin(dpUU[a], dpUU[ord[i]]);
			dpVV[a] = dV[a];
			ckmin(dpVV[a], dpVV[ord[i]]);
		}
	}
	cout << min(min(dpUU[s]+dpVV[s], dpU[t]+dpV[t]), dU[v]) << "\n";
}

Compilation message

commuter_pass.cpp: In function 'void NACHO(std::string)':
commuter_pass.cpp:70:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:71:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 20248 KB Output is correct
2 Runtime error 1492 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 22732 KB Output is correct
2 Correct 358 ms 23196 KB Output is correct
3 Correct 359 ms 22856 KB Output is correct
4 Correct 361 ms 23144 KB Output is correct
5 Correct 386 ms 24100 KB Output is correct
6 Correct 365 ms 26636 KB Output is correct
7 Correct 398 ms 27728 KB Output is correct
8 Correct 352 ms 23200 KB Output is correct
9 Correct 361 ms 24356 KB Output is correct
10 Correct 367 ms 22696 KB Output is correct
11 Correct 189 ms 24172 KB Output is correct
12 Correct 374 ms 27080 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 439 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 20248 KB Output is correct
2 Runtime error 1492 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -