oj.uz

Submission #459536

# Submission time Handle Problem Language Result Execution time Memory
459536 2021-08-08T15:19:37 Z nickmet2004 Aesthetic (NOI20_aesthetic) C++11
35 / 100
 780 ms 133172 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 1;
ll n , m , au[N] , av[N] , aw[N];
ll u , v , w , A = 0;
vector<pair<ll, pair<ll , ll> > >  adj[N];
ll d1[N] , dn[N] , f[N] , par[N] , path[N] , son[N];
priority_queue<pair<ll , ll> > pq;
multiset<pair<ll , ll>> S;
vector<ll> B[N] , T[N];
void q(int x){
    f[x] = 1;
    for(auto y : adj[x]){
        //cout << "h";
        auto it = S.find({dn[y.first] + y.second.first + d1[x] , y.second.second});
        if(f[y.first]) S.erase(it);
        else S.insert({dn[x] + y.second.first + d1[y.first] , y.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){
        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;
    pq.push({0 , 1});
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            v = e.first;
            if(d1[v] > w + e.second.first){
                par[v] = u;
                d1[v] = w + e.second.first;
                pq.push({-d1[v] , v});
            }
        }
        //cout << "k";
    }

    memset(f , 0 ,sizeof(f));
    pq.push({0, n});
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            v = e.first;
            if(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);

    memset(f , 0 ,sizeof(f));
    u = n;
    ll ans = d1[n];
    //cout << "ka";

    while(1){
        //cout << "ha";
        for(ll v : T[u]) q(v);
        //if(!S.size())continue;
        if(u == 1)break;
        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);
        u = par[u];
    }
    cout << ans;

}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23796 KB Output is correct
3 Correct 13 ms 23772 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 14 ms 23876 KB Output is correct
6 Correct 13 ms 23816 KB Output is correct
7 Correct 14 ms 23780 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23796 KB Output is correct
3 Correct 13 ms 23772 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 14 ms 23876 KB Output is correct
6 Correct 13 ms 23816 KB Output is correct
7 Correct 14 ms 23780 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 16 ms 24148 KB Output is correct
11 Correct 15 ms 24100 KB Output is correct
12 Correct 16 ms 24120 KB Output is correct
13 Correct 17 ms 24140 KB Output is correct
14 Correct 16 ms 24140 KB Output is correct
15 Correct 15 ms 24140 KB Output is correct
16 Correct 15 ms 24140 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 70204 KB Output is correct
2 Correct 756 ms 69528 KB Output is correct
3 Correct 709 ms 69816 KB Output is correct
4 Correct 764 ms 69972 KB Output is correct
5 Correct 768 ms 70380 KB Output is correct
6 Correct 780 ms 71420 KB Output is correct
7 Correct 746 ms 70800 KB Output is correct
8 Correct 750 ms 71524 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 71744 KB Output is correct
2 Correct 700 ms 70604 KB Output is correct
3 Correct 710 ms 68844 KB Output is correct
4 Correct 742 ms 70900 KB Output is correct
5 Correct 739 ms 70664 KB Output is correct
6 Correct 707 ms 71472 KB Output is correct
7 Correct 734 ms 70688 KB Output is correct
8 Correct 702 ms 70864 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 730 ms 133172 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 730 ms 133172 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 13 ms 23756 KB Output is correct
2 Correct 13 ms 23796 KB Output is correct
3 Correct 13 ms 23772 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 14 ms 23876 KB Output is correct
6 Correct 13 ms 23816 KB Output is correct
7 Correct 14 ms 23780 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 16 ms 24148 KB Output is correct
11 Correct 15 ms 24100 KB Output is correct
12 Correct 16 ms 24120 KB Output is correct
13 Correct 17 ms 24140 KB Output is correct
14 Correct 16 ms 24140 KB Output is correct
15 Correct 15 ms 24140 KB Output is correct
16 Correct 15 ms 24140 KB Output is correct
17 Correct 735 ms 70204 KB Output is correct
18 Correct 756 ms 69528 KB Output is correct
19 Correct 709 ms 69816 KB Output is correct
20 Correct 764 ms 69972 KB Output is correct
21 Correct 768 ms 70380 KB Output is correct
22 Correct 780 ms 71420 KB Output is correct
23 Correct 746 ms 70800 KB Output is correct
24 Correct 750 ms 71524 KB Output is correct
25 Correct 710 ms 71744 KB Output is correct
26 Correct 700 ms 70604 KB Output is correct
27 Correct 710 ms 68844 KB Output is correct
28 Correct 742 ms 70900 KB Output is correct
29 Correct 739 ms 70664 KB Output is correct
30 Correct 707 ms 71472 KB Output is correct
31 Correct 734 ms 70688 KB Output is correct
32 Correct 702 ms 70864 KB Output is correct
33 Runtime error 730 ms 133172 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -