oj.uz

Submission #255304

# Submission time Handle Problem Language Result Execution time Memory
255304 2020-07-31T17:14:59 Z model_code Aesthetic (NOI20_aesthetic) C++17
100 / 100
 1754 ms 32364 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

vector<tuple<int, int, int> > adj[300001];
int pre[300001], preve[300001], par[300001], depth[300001];
ll dis[2][300001];
void dijkstra(int s, int t) {
	priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
	dis[t][s] = 0;
	pq.push({0, s});
	ll c; int u;
	while (!pq.empty()) {
		tie(c, u) = pq.top();
		pq.pop();
		if (dis[t][u] != c) continue;
		for (int i=0; i<adj[u].size(); i++) {
			int v, w, b;
			tie(v, w, b) = adj[u][i];
			if (dis[t][v] != -1 && dis[t][v] <= c + w) continue;
			if (t == 0) {
				pre[v] = u;
				preve[v] = b;
				depth[v] = depth[u] + 1;
			}
			dis[t][v] = c + w;
			pq.push({dis[t][v], v});
		}
	}
}
int findp(int u) {
	return u == par[u] ? u : par[u] = findp(par[u]);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	bool isline[300001];
	int n, m, u, v, w, b, warr[300001], inc[300001];
	cin >> n >> m;
	for (int i=1; i<=m; i++) {
		cin >> u >> v >> w;
		adj[u].emplace_back(v, w, i);
		adj[v].emplace_back(u, w, i);
		warr[i] = w;
	}
	inc[m] = 0;
	for (int i=m-1; i; i--) inc[i] = max(inc[i+1], warr[i+1]);
	for (int i=0; i<2; i++) fill(dis[i]+1, dis[i]+n+1, -1);
	dijkstra(1, 0);
	dijkstra(n, 1);
	
	ll lo = dis[0][n] + 1, hi = dis[0][n] + 1e9, ans = dis[0][n], cut;
	bool valid;
	fill(isline+1, isline+m+1, false);
	for (int i=n; i; i=pre[i]) {
		par[i] = i;
		isline[preve[i]] = true;
	}
	while (lo <= hi) {
		cut = (lo + hi) / 2;
		for (int i=1; i<=n; i++) par[i] = pre[i];
		for (int i=n; i; i=pre[i]) par[i] = i;
		for (int i=1; i<=n; i++) {
			for (auto tup : adj[i]) {
				tie(v, w, b) = tup;
				u = i;
				if (min(dis[0][u]+dis[1][v], dis[0][v]+dis[1][u]) + w >= cut) continue;
				if (isline[b]) continue;
				u = findp(u), v = findp(v);
				if (depth[u] > depth[v]) swap(u, v);
				while (v != u) {
					par[v] = pre[v];
					v = findp(v);
				}
			}
		}
		v = findp(n);
		valid = false;
		while (v > 1) {
			u = pre[v], b = preve[v], w = warr[preve[v]];
			if (min(dis[0][u]+dis[1][v], dis[0][v]+dis[1][u]) + w + inc[b] >= cut) valid = true;
			v = findp(pre[v]);
		}
		if (valid) {
			ans = cut;
			lo = cut + 1;
		}
		else hi = cut - 1;
	}
	cout << ans;
}

Compilation message

Aesthetic.cpp: In function 'void dijkstra(int, int)':
Aesthetic.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<adj[u].size(); i++) {
                 ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 31608 KB Output is correct
2 Correct 1192 ms 31992 KB Output is correct
3 Correct 1171 ms 31508 KB Output is correct
4 Correct 1209 ms 31496 KB Output is correct
5 Correct 1145 ms 31480 KB Output is correct
6 Correct 1272 ms 32020 KB Output is correct
7 Correct 1196 ms 32120 KB Output is correct
8 Correct 1203 ms 32120 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1297 ms 32120 KB Output is correct
2 Correct 1219 ms 31708 KB Output is correct
3 Correct 1254 ms 31648 KB Output is correct
4 Correct 1240 ms 32364 KB Output is correct
5 Correct 1288 ms 31732 KB Output is correct
6 Correct 1217 ms 31736 KB Output is correct
7 Correct 1153 ms 31744 KB Output is correct
8 Correct 1194 ms 31928 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1579 ms 29468 KB Output is correct
2 Correct 608 ms 27548 KB Output is correct
3 Correct 812 ms 25356 KB Output is correct
4 Correct 827 ms 25468 KB Output is correct
5 Correct 785 ms 25336 KB Output is correct
6 Correct 813 ms 25464 KB Output is correct
7 Correct 790 ms 25328 KB Output is correct
8 Correct 802 ms 25336 KB Output is correct
9 Correct 818 ms 25308 KB Output is correct
10 Correct 858 ms 25548 KB Output is correct
11 Correct 858 ms 25408 KB Output is correct
12 Correct 1754 ms 29600 KB Output is correct
13 Correct 788 ms 25464 KB Output is correct
14 Correct 309 ms 28776 KB Output is correct
15 Correct 285 ms 28920 KB Output is correct
16 Correct 1529 ms 29520 KB Output is correct
17 Correct 1432 ms 28904 KB Output is correct
18 Correct 1414 ms 29472 KB Output is correct
19 Correct 773 ms 27664 KB Output is correct
20 Correct 607 ms 27768 KB Output is correct
21 Correct 707 ms 27680 KB Output is correct
22 Correct 730 ms 27512 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1579 ms 29468 KB Output is correct
2 Correct 608 ms 27548 KB Output is correct
3 Correct 812 ms 25356 KB Output is correct
4 Correct 827 ms 25468 KB Output is correct
5 Correct 785 ms 25336 KB Output is correct
6 Correct 813 ms 25464 KB Output is correct
7 Correct 790 ms 25328 KB Output is correct
8 Correct 802 ms 25336 KB Output is correct
9 Correct 818 ms 25308 KB Output is correct
10 Correct 858 ms 25548 KB Output is correct
11 Correct 858 ms 25408 KB Output is correct
12 Correct 1754 ms 29600 KB Output is correct
13 Correct 788 ms 25464 KB Output is correct
14 Correct 309 ms 28776 KB Output is correct
15 Correct 285 ms 28920 KB Output is correct
16 Correct 1529 ms 29520 KB Output is correct
17 Correct 1432 ms 28904 KB Output is correct
18 Correct 1414 ms 29472 KB Output is correct
19 Correct 773 ms 27664 KB Output is correct
20 Correct 607 ms 27768 KB Output is correct
21 Correct 707 ms 27680 KB Output is correct
22 Correct 730 ms 27512 KB Output is correct
23 Correct 1603 ms 30788 KB Output is correct
24 Correct 712 ms 27768 KB Output is correct
25 Correct 747 ms 25336 KB Output is correct
26 Correct 863 ms 25320 KB Output is correct
27 Correct 764 ms 25252 KB Output is correct
28 Correct 769 ms 25336 KB Output is correct
29 Correct 1014 ms 25336 KB Output is correct
30 Correct 800 ms 25336 KB Output is correct
31 Correct 805 ms 25592 KB Output is correct
32 Correct 906 ms 25464 KB Output is correct
33 Correct 892 ms 25592 KB Output is correct
34 Correct 1480 ms 30900 KB Output is correct
35 Correct 748 ms 25592 KB Output is correct
36 Correct 270 ms 31016 KB Output is correct
37 Correct 333 ms 31140 KB Output is correct
38 Correct 1706 ms 29616 KB Output is correct
39 Correct 1468 ms 30280 KB Output is correct
40 Correct 1750 ms 30796 KB Output is correct
41 Correct 661 ms 27768 KB Output is correct
42 Correct 632 ms 27772 KB Output is correct
43 Correct 635 ms 27640 KB Output is correct
44 Correct 632 ms 27768 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 5 ms 7424 KB Output is correct
8 Correct 5 ms 7424 KB Output is correct
9 Correct 9 ms 7552 KB Output is correct
10 Correct 8 ms 7552 KB Output is correct
11 Correct 8 ms 7552 KB Output is correct
12 Correct 7 ms 7552 KB Output is correct
13 Correct 9 ms 7520 KB Output is correct
14 Correct 6 ms 7552 KB Output is correct
15 Correct 6 ms 7552 KB Output is correct
16 Correct 7 ms 7552 KB Output is correct
17 Correct 1183 ms 31608 KB Output is correct
18 Correct 1192 ms 31992 KB Output is correct
19 Correct 1171 ms 31508 KB Output is correct
20 Correct 1209 ms 31496 KB Output is correct
21 Correct 1145 ms 31480 KB Output is correct
22 Correct 1272 ms 32020 KB Output is correct
23 Correct 1196 ms 32120 KB Output is correct
24 Correct 1203 ms 32120 KB Output is correct
25 Correct 1297 ms 32120 KB Output is correct
26 Correct 1219 ms 31708 KB Output is correct
27 Correct 1254 ms 31648 KB Output is correct
28 Correct 1240 ms 32364 KB Output is correct
29 Correct 1288 ms 31732 KB Output is correct
30 Correct 1217 ms 31736 KB Output is correct
31 Correct 1153 ms 31744 KB Output is correct
32 Correct 1194 ms 31928 KB Output is correct
33 Correct 1579 ms 29468 KB Output is correct
34 Correct 608 ms 27548 KB Output is correct
35 Correct 812 ms 25356 KB Output is correct
36 Correct 827 ms 25468 KB Output is correct
37 Correct 785 ms 25336 KB Output is correct
38 Correct 813 ms 25464 KB Output is correct
39 Correct 790 ms 25328 KB Output is correct
40 Correct 802 ms 25336 KB Output is correct
41 Correct 818 ms 25308 KB Output is correct
42 Correct 858 ms 25548 KB Output is correct
43 Correct 858 ms 25408 KB Output is correct
44 Correct 1754 ms 29600 KB Output is correct
45 Correct 788 ms 25464 KB Output is correct
46 Correct 309 ms 28776 KB Output is correct
47 Correct 285 ms 28920 KB Output is correct
48 Correct 1529 ms 29520 KB Output is correct
49 Correct 1432 ms 28904 KB Output is correct
50 Correct 1414 ms 29472 KB Output is correct
51 Correct 773 ms 27664 KB Output is correct
52 Correct 607 ms 27768 KB Output is correct
53 Correct 707 ms 27680 KB Output is correct
54 Correct 730 ms 27512 KB Output is correct
55 Correct 1603 ms 30788 KB Output is correct
56 Correct 712 ms 27768 KB Output is correct
57 Correct 747 ms 25336 KB Output is correct
58 Correct 863 ms 25320 KB Output is correct
59 Correct 764 ms 25252 KB Output is correct
60 Correct 769 ms 25336 KB Output is correct
61 Correct 1014 ms 25336 KB Output is correct
62 Correct 800 ms 25336 KB Output is correct
63 Correct 805 ms 25592 KB Output is correct
64 Correct 906 ms 25464 KB Output is correct
65 Correct 892 ms 25592 KB Output is correct
66 Correct 1480 ms 30900 KB Output is correct
67 Correct 748 ms 25592 KB Output is correct
68 Correct 270 ms 31016 KB Output is correct
69 Correct 333 ms 31140 KB Output is correct
70 Correct 1706 ms 29616 KB Output is correct
71 Correct 1468 ms 30280 KB Output is correct
72 Correct 1750 ms 30796 KB Output is correct
73 Correct 661 ms 27768 KB Output is correct
74 Correct 632 ms 27772 KB Output is correct
75 Correct 635 ms 27640 KB Output is correct
76 Correct 632 ms 27768 KB Output is correct
77 Correct 1115 ms 30924 KB Output is correct
78 Correct 529 ms 27640 KB Output is correct
79 Correct 597 ms 25336 KB Output is correct
80 Correct 610 ms 25592 KB Output is correct
81 Correct 607 ms 25592 KB Output is correct
82 Correct 621 ms 25464 KB Output is correct
83 Correct 601 ms 25720 KB Output is correct
84 Correct 602 ms 25464 KB Output is correct
85 Correct 604 ms 25464 KB Output is correct
86 Correct 601 ms 25720 KB Output is correct
87 Correct 587 ms 25592 KB Output is correct
88 Correct 969 ms 29836 KB Output is correct
89 Correct 569 ms 25464 KB Output is correct
90 Correct 283 ms 31012 KB Output is correct
91 Correct 348 ms 31268 KB Output is correct
92 Correct 975 ms 30788 KB Output is correct
93 Correct 978 ms 30796 KB Output is correct
94 Correct 1143 ms 30272 KB Output is correct
95 Correct 492 ms 27776 KB Output is correct
96 Correct 503 ms 27768 KB Output is correct
97 Correct 617 ms 27644 KB Output is correct
98 Correct 497 ms 27512 KB Output is correct