제출 #1265132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265132		vlomaczk	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	21 ms	6836 KiB

ho_t4

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Edge {
	ll a, b, c, d;
};

ll M = 210, n, m;
vector<vector<pair<ll, ll>>> g(M), gt(M), gscc(M), gtscc(M);
vector<Edge> edges;
vector<ll> scc(M), post;
ll nxt = 1, inf = 1e18;

void post_dfs(ll v) {
	if(scc[v]) return;
	scc[v] = 1;
	for(auto[u, k] : g[v]) post_dfs(u);
	post.push_back(v);
}

void trans_dfs(ll v) {
	scc[v] = nxt;
	for(auto[u, k] : gt[v]) if(!scc[u]) trans_dfs(u);
}

vector<vector<ll>> bfs(ll s, bool odw) {
	vector<vector<ll>> dist(M, vector<ll>(2, LLONG_MAX));
	dist[s][0] = 0;
	queue<pair<ll, ll>> Q;
	Q.push({s, 0});
	while(Q.size()) {
		auto[v, d] = Q.front(); Q.pop();
		if(v==scc[n] && d==0) {
			if(dist[v][1] > dist[v][0]) {
				dist[v][1] = dist[v][0];
				Q.push({v, 1});
			}
		}
		for(auto[u, k] : (odw ? gtscc[v] : gscc[v])) {
			if(dist[u][d] > dist[v][d] + 1) {
				dist[u][d] = dist[v][d] + 1;
				Q.push({u, d});
			}
		}
	}
	return dist;
}

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

	cin >> n >> m;
	for(ll i=0; i<m; ++i) {
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		g[a].push_back({b, i});
		gt[b].push_back({a, i});
		Edge e = {a, b, c, d};
		edges.emplace_back(e);
	}
	for(int i=1; i<=n; ++i) post_dfs(i);
	scc.assign(M, 0);
	reverse(post.begin(), post.end());
	for(auto v : post) {
		if(!scc[v]) {
			trans_dfs(v);
			nxt++;
		}
	}
	if(scc[1] == scc[n]) {
		cout << "0\n";
		return 0;
	}
	//for(int i=1; i<=n; ++i) cout << scc[i] << " "; cout << "\n";
	ll ans = LLONG_MAX;
	vector<Edge> scc_edges;
	for(ll i=1; i<=n; ++i) {
		for(auto[u, k] : g[i]) {
			if(scc[i]!=scc[u]) {
				gscc[scc[i]].push_back({scc[u], k});
				gtscc[scc[u]].push_back({scc[i], k});
				scc_edges.push_back(edges[k]);
			}
		}
	}
	vector<vector<ll>> distG = bfs(scc[1], 0);
	vector<vector<ll>> distGT = bfs(scc[1], 1);
	for(auto e : scc_edges) {
		auto[a, b, c, d] = e;
		a = scc[a];
		b = scc[b];
		if(distG[b][0]<inf && distGT[a][1]<inf && b!=scc[1]) {
			ans = min(ans, d);
			//cout << a << " " << b << "\n";
		}
		if(distG[b][1]<inf && distGT[a][0]<inf && b!=scc[n]) {
			ans = min(ans, d);
			//cout << a << " " << b << "\n";
		}
	}
	if(ans==LLONG_MAX) cout << "-1\n";
	else cout << ans << "\n";

	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63