oj.uz

Submission #285005

# Submission time Handle Problem Language Result Execution time Memory
285005 2020-08-28T08:51:11 Z 3zp Aesthetic (NOI20_aesthetic) C++14
35 / 100
 825 ms 81232 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500009;
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;
        auto it= S.find({dn[y] + l + d1[x], u});
        if(g[y] == 1 && it != S.end()) S.erase(it);
        if(g[y] == 0) 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];
        if(a == b)cout<<1/0;

        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];
        if(S.size() == 0) continue;
        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:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main(){
      |      ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:29:26: warning: division by zero [-Wdiv-by-zero]
   29 |         if(a == b)cout<<1/0;
      |                         ~^~
Aesthetic.cpp:86: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]
   86 |     for(ll i = 0; i < W.size(); i++){
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 16 ms 23936 KB Output is correct
7 Correct 16 ms 23936 KB Output is correct
8 Correct 17 ms 23936 KB Output is correct
9 Correct 19 ms 24320 KB Output is correct
10 Correct 18 ms 24184 KB Output is correct
11 Correct 18 ms 24192 KB Output is correct
12 Correct 19 ms 24320 KB Output is correct
13 Correct 19 ms 24320 KB Output is correct
14 Correct 18 ms 24192 KB Output is correct
15 Correct 18 ms 24192 KB Output is correct
16 Correct 18 ms 24184 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 74932 KB Output is correct
2 Correct 800 ms 79196 KB Output is correct
3 Correct 721 ms 77796 KB Output is correct
4 Correct 744 ms 79324 KB Output is correct
5 Correct 733 ms 78036 KB Output is correct
6 Correct 772 ms 80608 KB Output is correct
7 Correct 743 ms 80208 KB Output is correct
8 Correct 758 ms 79440 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 75228 KB Output is correct
2 Correct 733 ms 79716 KB Output is correct
3 Correct 736 ms 78416 KB Output is correct
4 Correct 776 ms 81088 KB Output is correct
5 Correct 764 ms 80092 KB Output is correct
6 Correct 787 ms 81232 KB Output is correct
7 Correct 825 ms 79824 KB Output is correct
8 Correct 728 ms 79312 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 63948 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 63948 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 16 ms 23936 KB Output is correct
7 Correct 16 ms 23936 KB Output is correct
8 Correct 17 ms 23936 KB Output is correct
9 Correct 19 ms 24320 KB Output is correct
10 Correct 18 ms 24184 KB Output is correct
11 Correct 18 ms 24192 KB Output is correct
12 Correct 19 ms 24320 KB Output is correct
13 Correct 19 ms 24320 KB Output is correct
14 Correct 18 ms 24192 KB Output is correct
15 Correct 18 ms 24192 KB Output is correct
16 Correct 18 ms 24184 KB Output is correct
17 Correct 747 ms 74932 KB Output is correct
18 Correct 800 ms 79196 KB Output is correct
19 Correct 721 ms 77796 KB Output is correct
20 Correct 744 ms 79324 KB Output is correct
21 Correct 733 ms 78036 KB Output is correct
22 Correct 772 ms 80608 KB Output is correct
23 Correct 743 ms 80208 KB Output is correct
24 Correct 758 ms 79440 KB Output is correct
25 Correct 763 ms 75228 KB Output is correct
26 Correct 733 ms 79716 KB Output is correct
27 Correct 736 ms 78416 KB Output is correct
28 Correct 776 ms 81088 KB Output is correct
29 Correct 764 ms 80092 KB Output is correct
30 Correct 787 ms 81232 KB Output is correct
31 Correct 825 ms 79824 KB Output is correct
32 Correct 728 ms 79312 KB Output is correct
33 Runtime error 134 ms 63948 KB Execution killed with signal 4
34 Halted 0 ms 0 KB -