Submission #529103

#	Time	Username	Problem	Language	Result	Execution time	Memory
529103		rk42745417	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	31 ms	3416 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(4e18) + ll(2e15);
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

signed main() {
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> edge(n + 1), redge(n + 1);
	vector<vector<bool>> can(n + 1, vector<bool>(n + 1));
	vector<tuple<int, int, int, int>> edges(m);
	for(int i = 0, u, v, c, d; i < m; i++) {
		cin >> u >> v >> c >> d;
		edge[u].push_back({v, c});
		redge[v].push_back({u, c});
		edges[i] = {u, v, c, d};
	}

	for(int i = 1; i <= n; i++) {
		can[i][i] = true;
		queue<int> bfs;
		bfs.push(i);
		while(!bfs.empty()) {
			int u = bfs.front();
			bfs.pop();
			for(const auto &[v, c] : edge[u]) {
				if(!can[i][v]) {
					can[i][v] = true;
					bfs.push(v);
				}
			}
		}
	}

	vector<int> pa(n + 1);
	vector<bool> vis(n + 1);
	stack<int, vector<int>> st;

	function<void(int)> dfs = [&](int u) {
		vis[u] = true;
		for(const auto &[v, c] : edge[u])
			if(!vis[v])
				dfs(v);
		st.push(u);
	};
	function<void(int, int)> dfs2 = [&](int u, int p) {
		pa[u] = p;
		for(const auto &[v, c] : redge[u])
			if(!pa[v])
				dfs2(v, p);
	};
	for(int i = 1; i <= n; i++)
		if(!vis[i])
			dfs(i);
	int t = 1;
	while(!st.empty()) {
		int u = st.top();
		st.pop();
		if(!pa[u])
			dfs2(u, t++);
	}
	if(pa[1] == pa[n]) {
		return cout << "0\n", 0;
	}
	int ans = INF;
	int cnt = 0;
	for(const auto &[u, v, c, d] : edges) {
		if(pa[u] == pa[1] && pa[v] == pa[n])
			cnt++;
		else if(pa[u] == pa[n] && pa[v] == pa[1])
			cnt++;
		else {
			if(can[1][n] && can[n][v] && can[u][1])
				ans = min(ans, d);
			if(can[n][1] && can[1][v] && can[u][n])
				ans = min(ans, d);
		}
	}
	if(cnt == 1) {
		for(const auto &[u, v, c, d] : edges) {
			if(pa[u] == pa[1] && pa[v] == pa[n])
				continue;
			if(pa[u] == pa[n] && pa[v] == pa[1])
				continue;
			if(can[1][n] && pa[u] != pa[1] && can[1][u] && can[v][n])
				cnt = INF;
			if(can[n][1] && pa[u] != pa[n] && can[n][u] && can[v][1])
				cnt = INF;
		}
	}
	if(cnt > 1) {
		for(const auto &[u, v, c, d] : edges) {
			if(pa[u] == pa[1] && pa[v] == pa[n])
				ans = min(ans, d);
			if(pa[u] == pa[n] && pa[v] == pa[1])
				ans = min(ans, d);
		}
	}

	if(ans == INF || (!can[1][n] && !can[n][1]))
		cout << "-1\n";
	else
		cout << ans << '\n';
}

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