oj.uz

Submission #677239

# Submission time Handle Problem Language Result Execution time Memory
677239 2023-01-02T16:07:08 Z vovamr Aesthetic (NOI20_aesthetic) C++17
22 / 100
 648 ms 38976 KB 
#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;
			else if (cost + sf[i] >= x) useless[i] = 2;
		}

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

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

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

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

					if (up[to] >= in[to]) bridge[id] = 1;
				}
			}
			used[v] = 2;
		};

		ve<int> p(n), rnk(n);
		for (int i = 0; i < n; ++i) {
			p[i] = i;
			rnk[i] = 1;
		}

		function<int(int)> par = [&p,&par](int v) {
			if (p[v] == v) return v;
			return p[v] = par(p[v]);
		};
		function<bool(int,int)> uni = [&p,&par,&rnk](int a, int b) {
			a = par(a), b = par(b);
			if (a == b) return 0;
			if (rnk[a] > rnk[b]) swap(a, b);
			p[a] = b, rnk[b] += rnk[a]; return 1;
		};

		dfs(0);

		for (int i = 0; i < m; ++i) {
			if (useless[i] == 1 || bridge[i]) continue;
			uni(edges[i][0], edges[i][1]);
		}

		return par(0) != par(n - 1);
	};

	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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 38236 KB Output is correct
2 Correct 576 ms 38432 KB Output is correct
3 Correct 584 ms 38012 KB Output is correct
4 Correct 590 ms 38104 KB Output is correct
5 Correct 564 ms 38116 KB Output is correct
6 Correct 562 ms 38848 KB Output is correct
7 Correct 564 ms 38808 KB Output is correct
8 Correct 592 ms 38964 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 38888 KB Output is correct
2 Correct 577 ms 38436 KB Output is correct
3 Correct 568 ms 38396 KB Output is correct
4 Correct 648 ms 38976 KB Output is correct
5 Correct 579 ms 38264 KB Output is correct
6 Correct 553 ms 38368 KB Output is correct
7 Correct 580 ms 38380 KB Output is correct
8 Correct 589 ms 38540 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 33328 KB Output is correct
2 Correct 198 ms 34216 KB Output is correct
3 Incorrect 225 ms 25120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 33328 KB Output is correct
2 Correct 198 ms 34216 KB Output is correct
3 Incorrect 225 ms 25120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -