oj.uz

Submission #285017

# Submission time Handle Problem Language Result Execution time Memory
285017 2020-08-28T08:58:44 Z 3zp Aesthetic (NOI20_aesthetic) C++14
51 / 100
 840 ms 71432 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<ll, pair<ll, ll > > > v[300009];
vector<ll> T[300009];
ll d1[300009],dn[300009], f[300009], g[300009],ea[300009],eb[300009],ec[300009], par[300009],path[300009],wh[300009];
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) 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){
            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:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main(){
      |      ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:85: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]
   85 |     for(ll i = 0; i < W.size(); i++){
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14592 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 11 ms 14464 KB Output is correct
9 Correct 12 ms 14848 KB Output is correct
10 Correct 12 ms 14848 KB Output is correct
11 Correct 14 ms 14848 KB Output is correct
12 Correct 14 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 14848 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 823 ms 70820 KB Output is correct
2 Correct 748 ms 69084 KB Output is correct
3 Correct 747 ms 67812 KB Output is correct
4 Correct 760 ms 69212 KB Output is correct
5 Correct 740 ms 68072 KB Output is correct
6 Correct 768 ms 70492 KB Output is correct
7 Correct 781 ms 70100 KB Output is correct
8 Correct 800 ms 69692 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 70972 KB Output is correct
2 Correct 791 ms 69640 KB Output is correct
3 Correct 808 ms 68356 KB Output is correct
4 Correct 791 ms 71108 KB Output is correct
5 Correct 789 ms 69988 KB Output is correct
6 Correct 775 ms 71432 KB Output is correct
7 Correct 775 ms 69820 KB Output is correct
8 Correct 752 ms 69200 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 65328 KB Output is correct
2 Correct 292 ms 62940 KB Output is correct
3 Correct 380 ms 55304 KB Output is correct
4 Correct 384 ms 54372 KB Output is correct
5 Correct 407 ms 53936 KB Output is correct
6 Correct 397 ms 55268 KB Output is correct
7 Correct 372 ms 53604 KB Output is correct
8 Correct 374 ms 54120 KB Output is correct
9 Correct 370 ms 53256 KB Output is correct
10 Correct 396 ms 56164 KB Output is correct
11 Correct 376 ms 53788 KB Output is correct
12 Correct 794 ms 62956 KB Output is correct
13 Correct 370 ms 54116 KB Output is correct
14 Correct 277 ms 69468 KB Output is correct
15 Correct 192 ms 62364 KB Output is correct
16 Correct 772 ms 63688 KB Output is correct
17 Correct 747 ms 61536 KB Output is correct
18 Correct 840 ms 63004 KB Output is correct
19 Correct 335 ms 62940 KB Output is correct
20 Correct 300 ms 63068 KB Output is correct
21 Correct 309 ms 63044 KB Output is correct
22 Correct 304 ms 62940 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 65328 KB Output is correct
2 Correct 292 ms 62940 KB Output is correct
3 Correct 380 ms 55304 KB Output is correct
4 Correct 384 ms 54372 KB Output is correct
5 Correct 407 ms 53936 KB Output is correct
6 Correct 397 ms 55268 KB Output is correct
7 Correct 372 ms 53604 KB Output is correct
8 Correct 374 ms 54120 KB Output is correct
9 Correct 370 ms 53256 KB Output is correct
10 Correct 396 ms 56164 KB Output is correct
11 Correct 376 ms 53788 KB Output is correct
12 Correct 794 ms 62956 KB Output is correct
13 Correct 370 ms 54116 KB Output is correct
14 Correct 277 ms 69468 KB Output is correct
15 Correct 192 ms 62364 KB Output is correct
16 Correct 772 ms 63688 KB Output is correct
17 Correct 747 ms 61536 KB Output is correct
18 Correct 840 ms 63004 KB Output is correct
19 Correct 335 ms 62940 KB Output is correct
20 Correct 300 ms 63068 KB Output is correct
21 Correct 309 ms 63044 KB Output is correct
22 Correct 304 ms 62940 KB Output is correct
23 Incorrect 676 ms 61304 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14592 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 11 ms 14464 KB Output is correct
9 Correct 12 ms 14848 KB Output is correct
10 Correct 12 ms 14848 KB Output is correct
11 Correct 14 ms 14848 KB Output is correct
12 Correct 14 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 14848 KB Output is correct
16 Correct 12 ms 14848 KB Output is correct
17 Correct 823 ms 70820 KB Output is correct
18 Correct 748 ms 69084 KB Output is correct
19 Correct 747 ms 67812 KB Output is correct
20 Correct 760 ms 69212 KB Output is correct
21 Correct 740 ms 68072 KB Output is correct
22 Correct 768 ms 70492 KB Output is correct
23 Correct 781 ms 70100 KB Output is correct
24 Correct 800 ms 69692 KB Output is correct
25 Correct 786 ms 70972 KB Output is correct
26 Correct 791 ms 69640 KB Output is correct
27 Correct 808 ms 68356 KB Output is correct
28 Correct 791 ms 71108 KB Output is correct
29 Correct 789 ms 69988 KB Output is correct
30 Correct 775 ms 71432 KB Output is correct
31 Correct 775 ms 69820 KB Output is correct
32 Correct 752 ms 69200 KB Output is correct
33 Correct 832 ms 65328 KB Output is correct
34 Correct 292 ms 62940 KB Output is correct
35 Correct 380 ms 55304 KB Output is correct
36 Correct 384 ms 54372 KB Output is correct
37 Correct 407 ms 53936 KB Output is correct
38 Correct 397 ms 55268 KB Output is correct
39 Correct 372 ms 53604 KB Output is correct
40 Correct 374 ms 54120 KB Output is correct
41 Correct 370 ms 53256 KB Output is correct
42 Correct 396 ms 56164 KB Output is correct
43 Correct 376 ms 53788 KB Output is correct
44 Correct 794 ms 62956 KB Output is correct
45 Correct 370 ms 54116 KB Output is correct
46 Correct 277 ms 69468 KB Output is correct
47 Correct 192 ms 62364 KB Output is correct
48 Correct 772 ms 63688 KB Output is correct
49 Correct 747 ms 61536 KB Output is correct
50 Correct 840 ms 63004 KB Output is correct
51 Correct 335 ms 62940 KB Output is correct
52 Correct 300 ms 63068 KB Output is correct
53 Correct 309 ms 63044 KB Output is correct
54 Correct 304 ms 62940 KB Output is correct
55 Incorrect 676 ms 61304 KB Output isn't correct
56 Halted 0 ms 0 KB -