Submission #1130146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130146		am_aadvik	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	318 ms	6904 KiB

ho_t4

#include <iostream>
#include<vector>
#define int long long
using namespace std;

vector<vector<int>> g[205];
bool r1[205] = { 0 }, rn[205] = { 0 }, c1[205] = { 0 }, cn[205] = { 0 };
bool dom[50005] = { 0 };
vector<int> vis(205, 0), path;
vector<vector<int>> e;

void dfs1(int node, int s, int n) {
	vis[node] = 1; //fill c1, cn, r1, rn
	if (s == 1) r1[node] = 1;
	else if (s == n) rn[node] = 1;
	if (node == 1) c1[s] = 1;
	else if (node == n) cn[node] = 1;
	for (auto x : g[node])
		if (!vis[x[0]])
			dfs1(x[0], s, n);
}

bool dfs2(int node, int t) {
	vis[node] = 1;
	if (node == t) return 1;
	for (auto x : g[node])
		if (!vis[x[0]]) {
			path.push_back(x[2]);
			if (dfs2(x[0], t))
				return 1;
			path.pop_back();
		}
	return 0;
}

bool dfs3(int node, int t, int l) {
	vis[node] = 1;
	if (node == t) return 1;
	for (auto x : g[node])
		if (!vis[x[0]] && (x[2] != l)) 
			if (dfs3(x[0], t, l))
				return 1;
	return 0;
}

int32_t main()
{
	int n, m; cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, c, d; cin >> u >> v >> c >> d;
		g[u].push_back({ v, d, i });
		e.push_back({ u, v, d, i });
	}

	for (int i = 1; i <= n; ++i) {
		dfs1(i, i, n); 
		vis.assign(n + 1, 0);
	}
	if (cn[1] && c1[n]) { cout << 0; return 0; }

	int s = 0;
	if (cn[1]) s = 1;
	else if (c1[n]) s = n;
	int o = ((s == 1) ? n : 1);

	if (s) {
		dfs2(s, o), vis.assign(n + 1, 0);
		for (auto x : path) {
			if (!dfs3(s, o, x))
				dom[x] = 1; //this edge dominates s-t 
			vis.assign(n + 1, 0);
		}
	}

	int ans = 1e17;
	for(int i = 0; i < m; ++i)
		if (!dom[i]) {
			int u = e[i][0], v = e[i][1];
			if ((s == 0) || (o == n))
				if ((!rn[v]) || (!c1[u]))
					continue;
			if(o != n)
				if ((!r1[v]) || (!cn[u]))
					continue;
			ans = min(ans, e[i][2]);
		}
	cout << ((ans == 1e17)? -1: ans);
}

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