Submission #1226253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226253		chaeryeong	Aesthetic (NOI20_aesthetic)	C++20	100 / 100	987 ms	80296 KiB

Aesthetic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int MAXN = 3e5 + 25;
vector <array <ll, 3>> adj[MAXN];
array <ll, 4> edges[MAXN];
int n, m;
ll dist[2][MAXN];
void dijkstra (int c, int node) {
	for (int i = 1; i <= n; i++) {
		dist[c][i] = inf;
	}
	dist[c][node] = 0;
	priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq;
	pq.push({0, node});
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		if (k.first > dist[c][k.second]) {
			continue;
		}
		for (auto [j, w, e] : adj[k.second]) {
			if (w + k.first < dist[c][j]) {
				dist[c][j] = w + k.first;
				pq.push({dist[c][j], j});
			}
		}
	}
/*	cout << node << ": ";
	for (int i = 1; i <= n; i++) {
		cout << dist[c][i] << " ";
	}
	cout << '\n';*/
}
vector <pair <int, int>> c[MAXN];
int in[MAXN], out[MAXN], tt, dp[MAXN], vis[MAXN];
int flag;
ll T;
void dfs (int pos, int par) {
	in[pos] = ++tt;
	dp[pos] = tt;
	vis[pos] = 1;
	for (auto [j, i] : c[pos]) {
		if (j == par) {
			continue;
		}
		if (!vis[j]) {
			dfs(j, pos);
			dp[pos] = min(dp[pos], dp[j]);
			if (dp[j] > in[pos] && vis[n] && in[j] <= in[n] && out[n] <= out[j]) {
				int u = 1;
				u &= dist[0][pos] + dist[1][j] + edges[i][2] + edges[i][3] > T;
				u &= dist[0][j] + dist[1][pos] + edges[i][2] + edges[i][3] > T;
				flag |= u;
			}
		} else {
			dp[pos] = min(dp[pos], in[j]);
		}
	}
	out[pos] = tt;
}
bool check (ll t) {
	T = t;
	for (int i = 1; i <= n; i++) {
		c[i].clear(); vis[i] = 0;
		in[i] = out[i] = 0;
	}
	tt = 0; flag = 0;
	for (int i = 1; i <= m; i++) {
		auto x = edges[i];
		if (dist[0][x[0]] + dist[1][x[1]] + x[2] <= t || dist[0][x[1]] + dist[1][x[0]] + x[2] <= t) {
			c[x[0]].push_back({x[1], i});
			c[x[1]].push_back({x[0], i});
		}
	}
	dfs(1, -1);
	return flag;
}
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (a == b) {
			m--; i--; continue;
		}
		edges[i] = {a, b, c, 0};
	}
	ll mx = 0;
	for (int i = m; i >= 1; i--) {
		edges[i][3] = mx;
		mx = max(mx, edges[i][2]);
	}
	for (int i = 1; i <= m; i++) {
		adj[edges[i][0]].push_back({edges[i][1], edges[i][2], edges[i][3]});
		adj[edges[i][1]].push_back({edges[i][0], edges[i][2], edges[i][3]});
	}
	dijkstra(0, 1);
	dijkstra(1, n);
	ll l = dist[0][n], r = dist[0][n] + 1e9, ans = dist[0][n] - 1;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (check(mid)) {
			l = mid + 1; ans = mid;
		} else {
			r = mid - 1;
		}
	}
	cout << ans + 1 << '\n';
}	
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27