oj.uz

Submission #459646

# Submission time Handle Problem Language Result Execution time Memory
459646 2021-08-08T21:34:11 Z nickmet2004 Aesthetic (NOI20_aesthetic) C++11
35 / 100
 767 ms 131780 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n , m ,A, au[300002] , av[300002] , aw[300002];
vector<pair<ll, pair<ll , ll> > >  adj[300002];
ll d1[300002] , dn[300002] , f[300002] , par[300002] , path[300002] , son[300002];
multiset<pair<ll , ll>> S;
vector<ll> B[300002] , T[300002];
void q(ll x){
    f[x] = 1;
    for(auto j : adj[x]){
        //cout << "h";
        ll y = j.first , l = j.second.first;
        auto it = S.find({dn[y] + l + d1[x] , j.second.second});
        if(f[y]==1) S.erase(it);
        if(f[y] == 0) S.insert({dn[x] + l + d1[y] , j.second.second});
    }
}
void dfs(int u , int p){
    if(path[u]) son[u] = u;
    else son[u] = son[p];
    T[son[u]].emplace_back(u);
    for(int v : B[u]) dfs(v , u);
}
main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i  =0; i <m; ++i) cin >> au[i] >> av[i] >> aw[i];
    for(int i = m - 1; ~i; --i){
        ll u = au[i] , v = av[i] , w= aw[i];
        adj[u].push_back({v , {w , A}});
        adj[v].push_back({u , {w , A}});
        A = max(A , w);
        //cout << "j";
    }

    for(int i = 1; i <= n; ++i) d1[i] = dn[i] = 1e18;
    d1[1] = 0;
    dn[n] = 0;
    priority_queue<pair<ll , ll> > pq;
    pq.push({0 , 1});
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        ll u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            ll v = e.first;
            if(!f[v] && d1[v] > w + e.second.first){
                par[v] = u;
                d1[v] = w + e.second.first;
                pq.push({-d1[v] , v});
            }
        }
        //cout << "k";
    }
    for(int i = 1; i <= n; ++i)f[i] = 0;
    //memset(f , 0 ,sizeof(f));
    pq.push({0, n});
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        ll u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            ll v = e.first;
            if(!f[v] && dn[v] > w + e.second.first){
                dn[v]= w + e.second.first;
                pq.push({-dn[v] , v});
            }
        }
        //cout << "l";
    }

    ll X = n;
    while(1){
        path[X] = 1;
        if(X == 1) break;
        X = par[X];
        //cout << "n";
    }

    for(int i = 1; i <= n; ++i)B[par[i]].emplace_back(i);
    dfs(1 , 0);

    for(int i = 1; i <= n; ++i) f[i] =0;
    ll s = n;
    ll ans = d1[n];
    //cout << "ka";
    while(1){
        //cout << "ha";
        for(ll v : T[s]) q(v);
        if(s == 1)break;
        s = par[s];
        ll k = S.begin()->first + S.begin()->second;
        auto i = S.begin();
        ++i;
        if(i != S.end()) k =min(k , i->first);
        ans = max(ans , k);
    }
    cout << ans<<endl;

}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21436 KB Output is correct
2 Correct 13 ms 21496 KB Output is correct
3 Correct 12 ms 21476 KB Output is correct
4 Correct 12 ms 21452 KB Output is correct
5 Correct 12 ms 21500 KB Output is correct
6 Correct 12 ms 21580 KB Output is correct
7 Correct 12 ms 21452 KB Output is correct
8 Correct 12 ms 21452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21436 KB Output is correct
2 Correct 13 ms 21496 KB Output is correct
3 Correct 12 ms 21476 KB Output is correct
4 Correct 12 ms 21452 KB Output is correct
5 Correct 12 ms 21500 KB Output is correct
6 Correct 12 ms 21580 KB Output is correct
7 Correct 12 ms 21452 KB Output is correct
8 Correct 12 ms 21452 KB Output is correct
9 Correct 16 ms 21708 KB Output is correct
10 Correct 14 ms 21836 KB Output is correct
11 Correct 14 ms 21812 KB Output is correct
12 Correct 14 ms 21820 KB Output is correct
13 Correct 14 ms 21708 KB Output is correct
14 Correct 14 ms 21712 KB Output is correct
15 Correct 14 ms 21704 KB Output is correct
16 Correct 14 ms 21796 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 70108 KB Output is correct
2 Correct 762 ms 69496 KB Output is correct
3 Correct 731 ms 69676 KB Output is correct
4 Correct 767 ms 69912 KB Output is correct
5 Correct 690 ms 70216 KB Output is correct
6 Correct 764 ms 71380 KB Output is correct
7 Correct 725 ms 70776 KB Output is correct
8 Correct 735 ms 71436 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 71716 KB Output is correct
2 Correct 724 ms 70572 KB Output is correct
3 Correct 747 ms 68832 KB Output is correct
4 Correct 760 ms 71028 KB Output is correct
5 Correct 710 ms 70664 KB Output is correct
6 Correct 746 ms 71568 KB Output is correct
7 Correct 711 ms 70640 KB Output is correct
8 Correct 703 ms 70832 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 721 ms 131780 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 721 ms 131780 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21436 KB Output is correct
2 Correct 13 ms 21496 KB Output is correct
3 Correct 12 ms 21476 KB Output is correct
4 Correct 12 ms 21452 KB Output is correct
5 Correct 12 ms 21500 KB Output is correct
6 Correct 12 ms 21580 KB Output is correct
7 Correct 12 ms 21452 KB Output is correct
8 Correct 12 ms 21452 KB Output is correct
9 Correct 16 ms 21708 KB Output is correct
10 Correct 14 ms 21836 KB Output is correct
11 Correct 14 ms 21812 KB Output is correct
12 Correct 14 ms 21820 KB Output is correct
13 Correct 14 ms 21708 KB Output is correct
14 Correct 14 ms 21712 KB Output is correct
15 Correct 14 ms 21704 KB Output is correct
16 Correct 14 ms 21796 KB Output is correct
17 Correct 720 ms 70108 KB Output is correct
18 Correct 762 ms 69496 KB Output is correct
19 Correct 731 ms 69676 KB Output is correct
20 Correct 767 ms 69912 KB Output is correct
21 Correct 690 ms 70216 KB Output is correct
22 Correct 764 ms 71380 KB Output is correct
23 Correct 725 ms 70776 KB Output is correct
24 Correct 735 ms 71436 KB Output is correct
25 Correct 724 ms 71716 KB Output is correct
26 Correct 724 ms 70572 KB Output is correct
27 Correct 747 ms 68832 KB Output is correct
28 Correct 760 ms 71028 KB Output is correct
29 Correct 710 ms 70664 KB Output is correct
30 Correct 746 ms 71568 KB Output is correct
31 Correct 711 ms 70640 KB Output is correct
32 Correct 703 ms 70832 KB Output is correct
33 Runtime error 721 ms 131780 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -