Submission #529106

#	Time	Username	Problem	Language	Result	Execution time	Memory
529106		rk42745417	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	25 ms	1772 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);
	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});
		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);
				}
			}
		}
	}

	if(can[1][n] && can[n][1]) {
		return cout << "0\n", 0;
	}
	int ans = INF;
	int cnt = 0;
	for(const auto &[u, v, c, d] : edges) {
		if((can[u][1] && can[1][u]) && (can[v][n] && can[n][v]))
			cnt++;
		else if((can[u][n] && can[n][u]) && (can[v][1] && can[1][v]))
			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((can[u][1] && can[1][u]) && (can[v][n] && can[n][v]))
				continue;
			else if((can[u][n] && can[n][u]) && (can[v][1] && can[1][v]))
				continue;
			if(can[1][n] && (!can[1][u] || !can[u][1]) && can[1][u] && can[v][n])
				cnt = INF;
			if(can[n][1] && (!can[u][n] || !can[n][u]) && can[n][u] && can[v][1])
				cnt = INF;
		}
	}
	if(cnt > 1) {
		for(const auto &[u, v, c, d] : edges) {
			if((can[u][1] && can[1][u]) && (can[v][n] && can[n][v]))
				ans = min(ans, d);
			else if((can[u][n] && can[n][u]) && (can[v][1] && can[1][v]))
				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