Submission #677247

#	Time	Username	Problem	Language	Result	Execution time	Memory
677247		vovamr	Aesthetic (NOI20_aesthetic)	C++17	22 / 100	687 ms	30172 KiB

Aesthetic

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 3e5 + 10;
const int M = 3e5 + 10;

ve<int> gr[N];

int n;

array<int,3> edges[M];
inline int go(const int &ID, const int &v) { return v ^ edges[ID][0] ^ edges[ID][1]; }

inline ve<ll> dij(const int &s) {
	ve<ll> d(n, inf); d[s] = 0;
	set<pll> st; st.insert({d[s], s});

	while (sz(st)) {
		int v = st.begin()->se;
		st.erase(st.begin());

		for (auto &id : gr[v]) {
			int to = go(id, v);
			int w = edges[id][2];

			if (d[to] > d[v] + w) {
				st.erase({d[to], to});
				d[to] = d[v] + w;
				st.insert({d[to], to});
			}
		}
	}
	return d;
}

inline void solve() {
	int m;
	cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int v, u, w;
		cin >> v >> u >> w;

		edges[i] = {--v, --u, w};

		gr[v].pb(i);
		gr[u].pb(i);
	}

	ve<int> sf(m);
	for (int i = m - 2; ~i; --i) {
		sf[i] = max(sf[i + 1], edges[i + 1][2]);
	}

	auto d0 = dij(0);
	auto d1 = dij(n - 1);

	auto can = [&](const ll &x) -> bool {

		ve<bool> useless(m);
		ve<bool> bridge(m);

		for (int i = 0; i < m; ++i) {
			auto &[v, u, w] = edges[i];
			ll cost = min(d0[v] + d1[u], d1[v] + d0[u]) + w;

			if (cost >= x) useless[i] = 1;
		}

		int timer = 0;
		ve<int> in(n), up(n), used(n);

		bool ok = 0;

		function<void(int,int)> dfs = [&](int v, int pid) {
			used[v] = 1;
			in[v] = up[v] = timer++;

			for (auto &id : gr[v]) {
				if (useless[id]) continue;

				int to = go(id, v);
				if (id == pid) continue;

				if (used[to] == 1) {
					chmin(up[v], in[to]);
				}
				else if (!used[to]) {
					dfs(to, id);
					chmin(up[v], up[to]);

					auto &[v, u, w] = edges[id];
					ll cs = min(d0[v] + d1[u], d1[v] + d0[u]) + w;
					if (up[to] > in[v] && in[n - 1] >= in[to] && cs + sf[id] >= x) {
						ok = 1;
					}
				}
			}
			used[v] = 2;
		};
		dfs(0, -1);

		return ok;
	};

	ll l = d0[n - 1], r = d0[n - 1] + sf[0], mid, ans;
	while (l <= r) {
		mid = l + r >> 1;
		if (can(mid)) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'void solve()':
Aesthetic.cpp:127:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |   mid = l + r >> 1;
      |         ~~^~~

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