oj.uz

Submission #677254

# Submission time Handle Problem Language Result Execution time Memory
677254 2023-01-02T16:30:38 Z vovamr Aesthetic (NOI20_aesthetic) C++17
100 / 100
 598 ms 53224 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 {

		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]) {
				int to = go(id, v);

				auto &[A, B, w] = edges[id];
				ll cs = min(d0[A] + d1[B], d1[A] + d0[B]) + w;

				if (cs > x || id == pid) continue;

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

					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];
	ll r = d0[n - 1] + sf[0] + 10;

	while (l < r) {
		ll mid = l + r >> 1;
		if (can(mid)) l = mid + 1;
		else r = mid;
	}
	cout << l;
}

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:119:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |   ll mid = l + r >> 1;
      |            ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 6 ms 7508 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 6 ms 7508 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 5 ms 7428 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 29412 KB Output is correct
2 Correct 466 ms 29472 KB Output is correct
3 Correct 466 ms 29376 KB Output is correct
4 Correct 463 ms 29360 KB Output is correct
5 Correct 470 ms 29432 KB Output is correct
6 Correct 472 ms 29932 KB Output is correct
7 Correct 452 ms 29688 KB Output is correct
8 Correct 463 ms 29992 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 30028 KB Output is correct
2 Correct 478 ms 29540 KB Output is correct
3 Correct 455 ms 29496 KB Output is correct
4 Correct 461 ms 29788 KB Output is correct
5 Correct 466 ms 29536 KB Output is correct
6 Correct 446 ms 29488 KB Output is correct
7 Correct 462 ms 29512 KB Output is correct
8 Correct 464 ms 29816 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 27824 KB Output is correct
2 Correct 224 ms 28340 KB Output is correct
3 Correct 294 ms 30760 KB Output is correct
4 Correct 307 ms 34492 KB Output is correct
5 Correct 309 ms 34544 KB Output is correct
6 Correct 313 ms 34568 KB Output is correct
7 Correct 329 ms 34780 KB Output is correct
8 Correct 326 ms 34840 KB Output is correct
9 Correct 299 ms 34556 KB Output is correct
10 Correct 305 ms 34788 KB Output is correct
11 Correct 298 ms 34700 KB Output is correct
12 Correct 417 ms 31912 KB Output is correct
13 Correct 305 ms 34620 KB Output is correct
14 Correct 158 ms 53188 KB Output is correct
15 Correct 160 ms 53224 KB Output is correct
16 Correct 430 ms 31996 KB Output is correct
17 Correct 408 ms 29920 KB Output is correct
18 Correct 419 ms 31720 KB Output is correct
19 Correct 223 ms 32624 KB Output is correct
20 Correct 237 ms 32564 KB Output is correct
21 Correct 230 ms 32500 KB Output is correct
22 Correct 223 ms 32560 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 27824 KB Output is correct
2 Correct 224 ms 28340 KB Output is correct
3 Correct 294 ms 30760 KB Output is correct
4 Correct 307 ms 34492 KB Output is correct
5 Correct 309 ms 34544 KB Output is correct
6 Correct 313 ms 34568 KB Output is correct
7 Correct 329 ms 34780 KB Output is correct
8 Correct 326 ms 34840 KB Output is correct
9 Correct 299 ms 34556 KB Output is correct
10 Correct 305 ms 34788 KB Output is correct
11 Correct 298 ms 34700 KB Output is correct
12 Correct 417 ms 31912 KB Output is correct
13 Correct 305 ms 34620 KB Output is correct
14 Correct 158 ms 53188 KB Output is correct
15 Correct 160 ms 53224 KB Output is correct
16 Correct 430 ms 31996 KB Output is correct
17 Correct 408 ms 29920 KB Output is correct
18 Correct 419 ms 31720 KB Output is correct
19 Correct 223 ms 32624 KB Output is correct
20 Correct 237 ms 32564 KB Output is correct
21 Correct 230 ms 32500 KB Output is correct
22 Correct 223 ms 32560 KB Output is correct
23 Correct 510 ms 31308 KB Output is correct
24 Correct 257 ms 32468 KB Output is correct
25 Correct 244 ms 33976 KB Output is correct
26 Correct 246 ms 33664 KB Output is correct
27 Correct 244 ms 33460 KB Output is correct
28 Correct 265 ms 34160 KB Output is correct
29 Correct 240 ms 33752 KB Output is correct
30 Correct 266 ms 33884 KB Output is correct
31 Correct 242 ms 33936 KB Output is correct
32 Correct 244 ms 33724 KB Output is correct
33 Correct 253 ms 34208 KB Output is correct
34 Correct 463 ms 31080 KB Output is correct
35 Correct 237 ms 33864 KB Output is correct
36 Correct 225 ms 50220 KB Output is correct
37 Correct 239 ms 52216 KB Output is correct
38 Correct 461 ms 30944 KB Output is correct
39 Correct 461 ms 31484 KB Output is correct
40 Correct 499 ms 31216 KB Output is correct
41 Correct 253 ms 32496 KB Output is correct
42 Correct 259 ms 32556 KB Output is correct
43 Correct 263 ms 32520 KB Output is correct
44 Correct 255 ms 32468 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 6 ms 7508 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 6 ms 7508 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 5 ms 7428 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 480 ms 29412 KB Output is correct
18 Correct 466 ms 29472 KB Output is correct
19 Correct 466 ms 29376 KB Output is correct
20 Correct 463 ms 29360 KB Output is correct
21 Correct 470 ms 29432 KB Output is correct
22 Correct 472 ms 29932 KB Output is correct
23 Correct 452 ms 29688 KB Output is correct
24 Correct 463 ms 29992 KB Output is correct
25 Correct 487 ms 30028 KB Output is correct
26 Correct 478 ms 29540 KB Output is correct
27 Correct 455 ms 29496 KB Output is correct
28 Correct 461 ms 29788 KB Output is correct
29 Correct 466 ms 29536 KB Output is correct
30 Correct 446 ms 29488 KB Output is correct
31 Correct 462 ms 29512 KB Output is correct
32 Correct 464 ms 29816 KB Output is correct
33 Correct 408 ms 27824 KB Output is correct
34 Correct 224 ms 28340 KB Output is correct
35 Correct 294 ms 30760 KB Output is correct
36 Correct 307 ms 34492 KB Output is correct
37 Correct 309 ms 34544 KB Output is correct
38 Correct 313 ms 34568 KB Output is correct
39 Correct 329 ms 34780 KB Output is correct
40 Correct 326 ms 34840 KB Output is correct
41 Correct 299 ms 34556 KB Output is correct
42 Correct 305 ms 34788 KB Output is correct
43 Correct 298 ms 34700 KB Output is correct
44 Correct 417 ms 31912 KB Output is correct
45 Correct 305 ms 34620 KB Output is correct
46 Correct 158 ms 53188 KB Output is correct
47 Correct 160 ms 53224 KB Output is correct
48 Correct 430 ms 31996 KB Output is correct
49 Correct 408 ms 29920 KB Output is correct
50 Correct 419 ms 31720 KB Output is correct
51 Correct 223 ms 32624 KB Output is correct
52 Correct 237 ms 32564 KB Output is correct
53 Correct 230 ms 32500 KB Output is correct
54 Correct 223 ms 32560 KB Output is correct
55 Correct 510 ms 31308 KB Output is correct
56 Correct 257 ms 32468 KB Output is correct
57 Correct 244 ms 33976 KB Output is correct
58 Correct 246 ms 33664 KB Output is correct
59 Correct 244 ms 33460 KB Output is correct
60 Correct 265 ms 34160 KB Output is correct
61 Correct 240 ms 33752 KB Output is correct
62 Correct 266 ms 33884 KB Output is correct
63 Correct 242 ms 33936 KB Output is correct
64 Correct 244 ms 33724 KB Output is correct
65 Correct 253 ms 34208 KB Output is correct
66 Correct 463 ms 31080 KB Output is correct
67 Correct 237 ms 33864 KB Output is correct
68 Correct 225 ms 50220 KB Output is correct
69 Correct 239 ms 52216 KB Output is correct
70 Correct 461 ms 30944 KB Output is correct
71 Correct 461 ms 31484 KB Output is correct
72 Correct 499 ms 31216 KB Output is correct
73 Correct 253 ms 32496 KB Output is correct
74 Correct 259 ms 32556 KB Output is correct
75 Correct 263 ms 32520 KB Output is correct
76 Correct 255 ms 32468 KB Output is correct
77 Correct 539 ms 33864 KB Output is correct
78 Correct 598 ms 34984 KB Output is correct
79 Correct 331 ms 36916 KB Output is correct
80 Correct 335 ms 37124 KB Output is correct
81 Correct 326 ms 36820 KB Output is correct
82 Correct 330 ms 36844 KB Output is correct
83 Correct 324 ms 37068 KB Output is correct
84 Correct 333 ms 37292 KB Output is correct
85 Correct 325 ms 36888 KB Output is correct
86 Correct 318 ms 36804 KB Output is correct
87 Correct 339 ms 37220 KB Output is correct
88 Correct 536 ms 34252 KB Output is correct
89 Correct 344 ms 37052 KB Output is correct
90 Correct 316 ms 50848 KB Output is correct
91 Correct 346 ms 52748 KB Output is correct
92 Correct 585 ms 34444 KB Output is correct
93 Correct 550 ms 34284 KB Output is correct
94 Correct 546 ms 32904 KB Output is correct
95 Correct 575 ms 34884 KB Output is correct
96 Correct 586 ms 34916 KB Output is correct
97 Correct 594 ms 34852 KB Output is correct
98 Correct 584 ms 34744 KB Output is correct