oj.uz

Submission #284948

# Submission time Handle Problem Language Result Execution time Memory
284948 2020-08-28T08:24:40 Z 3zp Aesthetic (NOI20_aesthetic) C++14
35 / 100
 884 ms 142684 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;
/*
00000111111

*/
void ad(ll x){
    if(g[x] == 1)cout<<1/0;
    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) 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];

        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: In function 'void ad(long long int)':
Aesthetic.cpp:14:25: warning: division by zero [-Wdiv-by-zero]
   14 |     if(g[x] == 1)cout<<1/0;
      |                        ~^~
Aesthetic.cpp: At global scope:
Aesthetic.cpp:24:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      |      ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:90: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]
   90 |     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 16 ms 23936 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 17 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 17 ms 23936 KB Output is correct
8 Correct 16 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 16 ms 23936 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 17 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 17 ms 23936 KB Output is correct
8 Correct 16 ms 23936 KB Output is correct
9 Correct 21 ms 24192 KB Output is correct
10 Correct 18 ms 24192 KB Output is correct
11 Correct 18 ms 24192 KB Output is correct
12 Correct 18 ms 24320 KB Output is correct
13 Correct 19 ms 24192 KB Output is correct
14 Correct 19 ms 24192 KB Output is correct
15 Correct 18 ms 24192 KB Output is correct
16 Correct 18 ms 24144 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 74960 KB Output is correct
2 Correct 790 ms 74972 KB Output is correct
3 Correct 766 ms 73828 KB Output is correct
4 Correct 779 ms 74972 KB Output is correct
5 Correct 760 ms 73680 KB Output is correct
6 Correct 759 ms 76256 KB Output is correct
7 Correct 781 ms 76052 KB Output is correct
8 Correct 782 ms 75344 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 75228 KB Output is correct
2 Correct 779 ms 75476 KB Output is correct
3 Correct 785 ms 74236 KB Output is correct
4 Correct 827 ms 76800 KB Output is correct
5 Correct 799 ms 75868 KB Output is correct
6 Correct 813 ms 76948 KB Output is correct
7 Correct 814 ms 75496 KB Output is correct
8 Correct 787 ms 74832 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 884 ms 142684 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 884 ms 142684 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 17 ms 23936 KB Output is correct
2 Correct 16 ms 23936 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 17 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 17 ms 23936 KB Output is correct
8 Correct 16 ms 23936 KB Output is correct
9 Correct 21 ms 24192 KB Output is correct
10 Correct 18 ms 24192 KB Output is correct
11 Correct 18 ms 24192 KB Output is correct
12 Correct 18 ms 24320 KB Output is correct
13 Correct 19 ms 24192 KB Output is correct
14 Correct 19 ms 24192 KB Output is correct
15 Correct 18 ms 24192 KB Output is correct
16 Correct 18 ms 24144 KB Output is correct
17 Correct 784 ms 74960 KB Output is correct
18 Correct 790 ms 74972 KB Output is correct
19 Correct 766 ms 73828 KB Output is correct
20 Correct 779 ms 74972 KB Output is correct
21 Correct 760 ms 73680 KB Output is correct
22 Correct 759 ms 76256 KB Output is correct
23 Correct 781 ms 76052 KB Output is correct
24 Correct 782 ms 75344 KB Output is correct
25 Correct 781 ms 75228 KB Output is correct
26 Correct 779 ms 75476 KB Output is correct
27 Correct 785 ms 74236 KB Output is correct
28 Correct 827 ms 76800 KB Output is correct
29 Correct 799 ms 75868 KB Output is correct
30 Correct 813 ms 76948 KB Output is correct
31 Correct 814 ms 75496 KB Output is correct
32 Correct 787 ms 74832 KB Output is correct
33 Runtime error 884 ms 142684 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -