oj.uz

Submission #284302

# Submission time Handle Problem Language Result Execution time Memory
284302 2020-08-27T07:59:48 Z 임성재(#5754) Aesthetic (NOI20_aesthetic) C++17
22 / 100
 795 ms 45244 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> plll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
int u[300010];
int v[300010];
ll w[300010];
ll a[300010];
vector<pii> g[300010];
priority_queue<plll, vector<plll>, greater<plll>> pQ;
vector<pll> D[300010];

int main() {
	fast;

	cin >> n >> m;

	for(int i=1; i<=m; i++) {
		cin >> u[i] >> v[i] >> w[i];

		g[u[i]].eb(v[i], i);
		g[v[i]].eb(u[i], i);
	}

	for(int i=m; i > 1; i--) {
		a[i-1] = max(a[i], w[i]);
	}

	pQ.em(0, mp(1, 0));

	while(pQ.size()) {
		ll d = pQ.top().fi;
		ll x = pQ.top().se.fi;
		ll e = pQ.top().se.se;
		pQ.pop();

		if(D[x].size() > 1 || D[x].size() == 1 && D[x][0].se == e) continue;

		D[x].eb(mp(d, e));

		for(auto i : g[x]) {
			if(i.se == e) continue;

			pQ.em(d + w[i.se], i);
		}
	}

	ll ans = D[n][0].fi;
	for(int i = n; i != 1; i = u[D[i][0].se] + v[D[i][0].se] - i) {
		if(D[i].size() == 1) D[i].eb(INF, 0);

		ans = max(ans, D[n][0].fi + min(D[i][1].fi - D[i][0].fi, a[D[i][0].se]));

		//cout << D[n][0].fi + D[i][1].fi - D[i][0].fi << " " << D[n][0].fi + a[D[i][0].se] << endl;
	}

	cout << ans;
}

Compilation message

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:52:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |   if(D[x].size() > 1 || D[x].size() == 1 && D[x][0].se == e) continue;
      |                         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14464 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 456 ms 41148 KB Output is correct
2 Correct 458 ms 41336 KB Output is correct
3 Correct 460 ms 40952 KB Output is correct
4 Correct 456 ms 40824 KB Output is correct
5 Correct 446 ms 41004 KB Output is correct
6 Correct 463 ms 41496 KB Output is correct
7 Correct 469 ms 41464 KB Output is correct
8 Correct 490 ms 41720 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 41592 KB Output is correct
2 Correct 516 ms 41208 KB Output is correct
3 Correct 480 ms 41144 KB Output is correct
4 Correct 505 ms 41544 KB Output is correct
5 Correct 505 ms 41056 KB Output is correct
6 Correct 488 ms 41256 KB Output is correct
7 Correct 477 ms 41156 KB Output is correct
8 Correct 504 ms 41344 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 45244 KB Output is correct
2 Correct 263 ms 42616 KB Output is correct
3 Incorrect 433 ms 34472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 45244 KB Output is correct
2 Correct 263 ms 42616 KB Output is correct
3 Incorrect 433 ms 34472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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