oj.uz

Submission #284929

# Submission time Handle Problem Language Result Execution time Memory
284929 2020-08-28T08:06:21 Z 3zp Aesthetic (NOI20_aesthetic) C++14
35 / 100
 806 ms 125020 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 300009;
vector<pair<ll, pair<ll, ll > > > v[N];
vector<ll> T[N];
ll d1[N],dn[N], f[N], g[N],ea[N],eb[N],ec[N], par[N],path[N],wh[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({dn[y] + l + d1[x], u}));
        else S.insert({dn[x] + l + d1[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;
                par[y] = x;
                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];
    ll X = n;
    while(1){
        path[X] = 1;
        if(X == 1) break;
        X = par[X];
    }

    for(ll i = 1; i <= n; i++){
        W.push_back({d1[i], i});
    }
    sort(W.begin(), W.end());
    for(ll i = 0; i < W.size(); i++){
        ll x = W[i].second;
        if(path[x]) wh[x] = x;
        else wh[x] = wh[par[x]];
        T[wh[x]].push_back(x);
    }
    ll x = n;
    while(1){
        for(ll y : T[x])
            ad(y);
        if(x == 1) break;
        x = par[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:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main(){
      |      ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:84:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(ll i = 0; i < W.size(); i++){
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 8 ms 14464 KB Output is correct
4 Correct 12 ms 14464 KB Output is correct
5 Correct 11 ms 14592 KB Output is correct
6 Correct 10 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 10 ms 14464 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 67152 KB Output is correct
2 Correct 748 ms 67168 KB Output is correct
3 Correct 736 ms 66016 KB Output is correct
4 Correct 758 ms 67296 KB Output is correct
5 Correct 753 ms 66104 KB Output is correct
6 Correct 757 ms 68572 KB Output is correct
7 Correct 795 ms 68108 KB Output is correct
8 Correct 806 ms 67536 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 67288 KB Output is correct
2 Correct 779 ms 67684 KB Output is correct
3 Correct 758 ms 66384 KB Output is correct
4 Correct 775 ms 69200 KB Output is correct
5 Correct 780 ms 68044 KB Output is correct
6 Correct 802 ms 69312 KB Output is correct
7 Correct 771 ms 67920 KB Output is correct
8 Correct 758 ms 67220 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 780 ms 125020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 780 ms 125020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 8 ms 14464 KB Output is correct
4 Correct 12 ms 14464 KB Output is correct
5 Correct 11 ms 14592 KB Output is correct
6 Correct 10 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 10 ms 14464 KB Output is correct
9 Correct 14 ms 14848 KB Output is correct
10 Correct 12 ms 14848 KB Output is correct
11 Correct 12 ms 14848 KB Output is correct
12 Correct 12 ms 14848 KB Output is correct
13 Correct 12 ms 14848 KB Output is correct
14 Correct 12 ms 14848 KB Output is correct
15 Correct 12 ms 14976 KB Output is correct
16 Correct 12 ms 14848 KB Output is correct
17 Correct 739 ms 67152 KB Output is correct
18 Correct 748 ms 67168 KB Output is correct
19 Correct 736 ms 66016 KB Output is correct
20 Correct 758 ms 67296 KB Output is correct
21 Correct 753 ms 66104 KB Output is correct
22 Correct 757 ms 68572 KB Output is correct
23 Correct 795 ms 68108 KB Output is correct
24 Correct 806 ms 67536 KB Output is correct
25 Correct 801 ms 67288 KB Output is correct
26 Correct 779 ms 67684 KB Output is correct
27 Correct 758 ms 66384 KB Output is correct
28 Correct 775 ms 69200 KB Output is correct
29 Correct 780 ms 68044 KB Output is correct
30 Correct 802 ms 69312 KB Output is correct
31 Correct 771 ms 67920 KB Output is correct
32 Correct 758 ms 67220 KB Output is correct
33 Runtime error 780 ms 125020 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -