oj.uz

Submission #284907

# Submission time Handle Problem Language Result Execution time Memory
284907 2020-08-28T07:54:04 Z 3zp Aesthetic (NOI20_aesthetic) C++14
38 / 100
 832 ms 56832 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 300009;
vector<pair<ll, pair<ll, ll > > > v[N];
ll d1[N],dn[N], f[N], g[N],ea[N],eb[N],ec[N];
multiset<pair<ll,ll> > S;
void ad(ll x){
    g[x] = 1;
    for(auto E : v[x]){
        ll y = E.first, l = E.second.first,  u= E.second.second;
        if(g[y] == 1) S.erase(S.find({d1[y] + l + dn[x], u}));
        else S.insert({d1[x] + l + dn[y], u});
    }
}
ll A = 0;
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n, m;
    cin >> n >> m;
    for(ll i = 0; i < m; i++){
        cin>>ea[i]>>eb[i]>>ec[i];
    }
    for(ll i = m-1; i >= 0; i--){
        ll a = ea[i], b = eb[i], c = ec[i];

        v[a].push_back({b, {c,A}});
        v[b].push_back({a, {c,A}});
        A = max(A, c);
    }
    for(ll i = 1; i <= n; i++){
        d1[i] = 1e18;
        dn[i] = 1e18;
    }
    d1[1] = 0;
    dn[n] = 0;
    priority_queue<pair<ll, ll> > q;
    q.push({0, 1});
    while(q.size()){
        ll x = q.top().second;
        q.pop();
        if(f[x]) continue;
        f[x] = 1;
        for(auto E: v[x]){
            ll y = E.first, l = E.second.first;
            if(!f[y] && d1[y] > d1[x] + l){
                d1[y] = d1[x] + l;
                q.push({-d1[y], y});
            }
        }
    }
    q.push({0, n});
    for(ll i = 1; i <= n; i++)
        f[i] = 0;
    while(q.size()){
        ll x = q.top().second;
        q.pop();
        if(f[x]) continue;
        f[x] = 1;
        for(auto E: v[x]){
            ll y = E.first, l = E.second.first;
            if(!f[y] && dn[y] > dn[x] + l){
                dn[y] = dn[x] + l;
                q.push({-dn[y], y});
            }
        }
    }
    vector<pair<ll,ll> > W;
    ll ans = d1[n];
    for(ll i = 1; i <= n; i++){
        W.push_back({d1[i], i});
    }
    sort(W.begin(), W.end());
    for(ll i = 0; i < n; i++){

        ll x = W[i].second;
        if(x == n) break;
        ad(x);
        ll U = S.begin()->first + S.begin()->second;
        auto it = S.begin();
        it++;
        if(it != S.end()) U = min(U, it->first);
        ans = max(ans, U);
    }
    cout<<ans<<endl;
}

Compilation message

Aesthetic.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main(){
      |      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7456 KB Output is correct
2 Incorrect 5 ms 7424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7456 KB Output is correct
2 Incorrect 5 ms 7424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 55908 KB Output is correct
2 Correct 593 ms 56060 KB Output is correct
3 Correct 674 ms 55672 KB Output is correct
4 Correct 642 ms 55824 KB Output is correct
5 Correct 724 ms 55652 KB Output is correct
6 Correct 646 ms 56688 KB Output is correct
7 Correct 613 ms 56540 KB Output is correct
8 Correct 653 ms 56804 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 56560 KB Output is correct
2 Correct 634 ms 56056 KB Output is correct
3 Correct 624 ms 56036 KB Output is correct
4 Correct 557 ms 56832 KB Output is correct
5 Correct 652 ms 55920 KB Output is correct
6 Correct 606 ms 56012 KB Output is correct
7 Correct 695 ms 56008 KB Output is correct
8 Correct 739 ms 56232 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 53232 KB Output is correct
2 Correct 283 ms 49884 KB Output is correct
3 Correct 301 ms 44808 KB Output is correct
4 Correct 317 ms 44808 KB Output is correct
5 Correct 307 ms 44772 KB Output is correct
6 Correct 299 ms 44904 KB Output is correct
7 Correct 307 ms 44772 KB Output is correct
8 Correct 308 ms 44876 KB Output is correct
9 Correct 312 ms 44936 KB Output is correct
10 Correct 322 ms 45224 KB Output is correct
11 Correct 300 ms 44900 KB Output is correct
12 Correct 549 ms 53464 KB Output is correct
13 Correct 303 ms 44772 KB Output is correct
14 Correct 173 ms 50272 KB Output is correct
15 Correct 164 ms 50324 KB Output is correct
16 Correct 687 ms 54372 KB Output is correct
17 Correct 688 ms 53200 KB Output is correct
18 Correct 678 ms 53768 KB Output is correct
19 Correct 267 ms 50012 KB Output is correct
20 Correct 274 ms 50020 KB Output is correct
21 Correct 272 ms 50068 KB Output is correct
22 Correct 268 ms 49996 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 53232 KB Output is correct
2 Correct 283 ms 49884 KB Output is correct
3 Correct 301 ms 44808 KB Output is correct
4 Correct 317 ms 44808 KB Output is correct
5 Correct 307 ms 44772 KB Output is correct
6 Correct 299 ms 44904 KB Output is correct
7 Correct 307 ms 44772 KB Output is correct
8 Correct 308 ms 44876 KB Output is correct
9 Correct 312 ms 44936 KB Output is correct
10 Correct 322 ms 45224 KB Output is correct
11 Correct 300 ms 44900 KB Output is correct
12 Correct 549 ms 53464 KB Output is correct
13 Correct 303 ms 44772 KB Output is correct
14 Correct 173 ms 50272 KB Output is correct
15 Correct 164 ms 50324 KB Output is correct
16 Correct 687 ms 54372 KB Output is correct
17 Correct 688 ms 53200 KB Output is correct
18 Correct 678 ms 53768 KB Output is correct
19 Correct 267 ms 50012 KB Output is correct
20 Correct 274 ms 50020 KB Output is correct
21 Correct 272 ms 50068 KB Output is correct
22 Correct 268 ms 49996 KB Output is correct
23 Incorrect 832 ms 54492 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7456 KB Output is correct
2 Incorrect 5 ms 7424 KB Output isn't correct
3 Halted 0 ms 0 KB -