oj.uz

Submission #285010

# Submission time Handle Problem Language Result Execution time Memory
285010 2020-08-28T08:53:05 Z 3zp Aesthetic (NOI20_aesthetic) C++14
51 / 100
 870 ms 77148 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) 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) continue;
        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: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 16 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 16 ms 23936 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 16 ms 23848 KB Output is correct
7 Correct 18 ms 24064 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 16 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 16 ms 23936 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 16 ms 23848 KB Output is correct
7 Correct 18 ms 24064 KB Output is correct
8 Correct 17 ms 23936 KB Output is correct
9 Correct 17 ms 24168 KB Output is correct
10 Correct 18 ms 24192 KB Output is correct
11 Correct 19 ms 24320 KB Output is correct
12 Correct 19 ms 24192 KB Output is correct
13 Correct 18 ms 24192 KB Output is correct
14 Correct 18 ms 24192 KB Output is correct
15 Correct 17 ms 24192 KB Output is correct
16 Correct 17 ms 24192 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 75068 KB Output is correct
2 Correct 787 ms 75056 KB Output is correct
3 Correct 797 ms 73732 KB Output is correct
4 Correct 752 ms 75100 KB Output is correct
5 Correct 749 ms 73808 KB Output is correct
6 Correct 800 ms 76280 KB Output is correct
7 Correct 780 ms 75984 KB Output is correct
8 Correct 765 ms 75344 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 75164 KB Output is correct
2 Correct 771 ms 75620 KB Output is correct
3 Correct 795 ms 74320 KB Output is correct
4 Correct 803 ms 77008 KB Output is correct
5 Correct 783 ms 75736 KB Output is correct
6 Correct 772 ms 77008 KB Output is correct
7 Correct 766 ms 75600 KB Output is correct
8 Correct 749 ms 74960 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 70500 KB Output is correct
2 Correct 297 ms 71004 KB Output is correct
3 Correct 383 ms 63368 KB Output is correct
4 Correct 368 ms 62180 KB Output is correct
5 Correct 370 ms 61668 KB Output is correct
6 Correct 372 ms 63172 KB Output is correct
7 Correct 369 ms 61288 KB Output is correct
8 Correct 393 ms 61796 KB Output is correct
9 Correct 385 ms 61136 KB Output is correct
10 Correct 385 ms 63972 KB Output is correct
11 Correct 408 ms 61672 KB Output is correct
12 Correct 870 ms 70628 KB Output is correct
13 Correct 375 ms 61800 KB Output is correct
14 Correct 279 ms 77148 KB Output is correct
15 Correct 199 ms 70120 KB Output is correct
16 Correct 832 ms 71720 KB Output is correct
17 Correct 844 ms 69224 KB Output is correct
18 Correct 814 ms 70752 KB Output is correct
19 Correct 303 ms 70896 KB Output is correct
20 Correct 290 ms 71004 KB Output is correct
21 Correct 289 ms 70832 KB Output is correct
22 Correct 290 ms 70876 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 70500 KB Output is correct
2 Correct 297 ms 71004 KB Output is correct
3 Correct 383 ms 63368 KB Output is correct
4 Correct 368 ms 62180 KB Output is correct
5 Correct 370 ms 61668 KB Output is correct
6 Correct 372 ms 63172 KB Output is correct
7 Correct 369 ms 61288 KB Output is correct
8 Correct 393 ms 61796 KB Output is correct
9 Correct 385 ms 61136 KB Output is correct
10 Correct 385 ms 63972 KB Output is correct
11 Correct 408 ms 61672 KB Output is correct
12 Correct 870 ms 70628 KB Output is correct
13 Correct 375 ms 61800 KB Output is correct
14 Correct 279 ms 77148 KB Output is correct
15 Correct 199 ms 70120 KB Output is correct
16 Correct 832 ms 71720 KB Output is correct
17 Correct 844 ms 69224 KB Output is correct
18 Correct 814 ms 70752 KB Output is correct
19 Correct 303 ms 70896 KB Output is correct
20 Correct 290 ms 71004 KB Output is correct
21 Correct 289 ms 70832 KB Output is correct
22 Correct 290 ms 70876 KB Output is correct
23 Incorrect 616 ms 69024 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 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 16 ms 23936 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 16 ms 23848 KB Output is correct
7 Correct 18 ms 24064 KB Output is correct
8 Correct 17 ms 23936 KB Output is correct
9 Correct 17 ms 24168 KB Output is correct
10 Correct 18 ms 24192 KB Output is correct
11 Correct 19 ms 24320 KB Output is correct
12 Correct 19 ms 24192 KB Output is correct
13 Correct 18 ms 24192 KB Output is correct
14 Correct 18 ms 24192 KB Output is correct
15 Correct 17 ms 24192 KB Output is correct
16 Correct 17 ms 24192 KB Output is correct
17 Correct 771 ms 75068 KB Output is correct
18 Correct 787 ms 75056 KB Output is correct
19 Correct 797 ms 73732 KB Output is correct
20 Correct 752 ms 75100 KB Output is correct
21 Correct 749 ms 73808 KB Output is correct
22 Correct 800 ms 76280 KB Output is correct
23 Correct 780 ms 75984 KB Output is correct
24 Correct 765 ms 75344 KB Output is correct
25 Correct 782 ms 75164 KB Output is correct
26 Correct 771 ms 75620 KB Output is correct
27 Correct 795 ms 74320 KB Output is correct
28 Correct 803 ms 77008 KB Output is correct
29 Correct 783 ms 75736 KB Output is correct
30 Correct 772 ms 77008 KB Output is correct
31 Correct 766 ms 75600 KB Output is correct
32 Correct 749 ms 74960 KB Output is correct
33 Correct 796 ms 70500 KB Output is correct
34 Correct 297 ms 71004 KB Output is correct
35 Correct 383 ms 63368 KB Output is correct
36 Correct 368 ms 62180 KB Output is correct
37 Correct 370 ms 61668 KB Output is correct
38 Correct 372 ms 63172 KB Output is correct
39 Correct 369 ms 61288 KB Output is correct
40 Correct 393 ms 61796 KB Output is correct
41 Correct 385 ms 61136 KB Output is correct
42 Correct 385 ms 63972 KB Output is correct
43 Correct 408 ms 61672 KB Output is correct
44 Correct 870 ms 70628 KB Output is correct
45 Correct 375 ms 61800 KB Output is correct
46 Correct 279 ms 77148 KB Output is correct
47 Correct 199 ms 70120 KB Output is correct
48 Correct 832 ms 71720 KB Output is correct
49 Correct 844 ms 69224 KB Output is correct
50 Correct 814 ms 70752 KB Output is correct
51 Correct 303 ms 70896 KB Output is correct
52 Correct 290 ms 71004 KB Output is correct
53 Correct 289 ms 70832 KB Output is correct
54 Correct 290 ms 70876 KB Output is correct
55 Incorrect 616 ms 69024 KB Output isn't correct
56 Halted 0 ms 0 KB -