oj.uz

Submission #285011

# Submission time Handle Problem Language Result Execution time Memory
285011 2020-08-28T08:54:06 Z 3zp Aesthetic (NOI20_aesthetic) C++14
35 / 100
 841 ms 77072 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];
        if(ea[i] == eb[i])cout<<1/0;
    }
    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:26:34: warning: division by zero [-Wdiv-by-zero]
   26 |         if(ea[i] == eb[i])cout<<1/0;
      |                                 ~^~
Aesthetic.cpp:86: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]
   86 |     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 17 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 19 ms 23936 KB Output is correct
7 Correct 16 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 16 ms 23936 KB Output is correct
2 Correct 17 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 19 ms 23936 KB Output is correct
7 Correct 16 ms 23936 KB Output is correct
8 Correct 16 ms 23936 KB Output is correct
9 Correct 18 ms 24192 KB Output is correct
10 Correct 21 ms 24192 KB Output is correct
11 Correct 18 ms 24192 KB Output is correct
12 Correct 18 ms 24192 KB Output is correct
13 Correct 19 ms 24192 KB Output is correct
14 Correct 18 ms 24192 KB Output is correct
15 Correct 18 ms 24192 KB Output is correct
16 Correct 19 ms 24192 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 75088 KB Output is correct
2 Correct 761 ms 75020 KB Output is correct
3 Correct 819 ms 73832 KB Output is correct
4 Correct 742 ms 75100 KB Output is correct
5 Correct 751 ms 73696 KB Output is correct
6 Correct 826 ms 76364 KB Output is correct
7 Correct 789 ms 75984 KB Output is correct
8 Correct 782 ms 75216 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 75152 KB Output is correct
2 Correct 754 ms 75492 KB Output is correct
3 Correct 750 ms 74168 KB Output is correct
4 Correct 799 ms 76828 KB Output is correct
5 Correct 784 ms 75744 KB Output is correct
6 Correct 770 ms 77072 KB Output is correct
7 Correct 841 ms 75728 KB Output is correct
8 Correct 759 ms 74960 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 61176 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 61176 KB Execution killed with signal 4
2 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 17 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 19 ms 23936 KB Output is correct
7 Correct 16 ms 23936 KB Output is correct
8 Correct 16 ms 23936 KB Output is correct
9 Correct 18 ms 24192 KB Output is correct
10 Correct 21 ms 24192 KB Output is correct
11 Correct 18 ms 24192 KB Output is correct
12 Correct 18 ms 24192 KB Output is correct
13 Correct 19 ms 24192 KB Output is correct
14 Correct 18 ms 24192 KB Output is correct
15 Correct 18 ms 24192 KB Output is correct
16 Correct 19 ms 24192 KB Output is correct
17 Correct 778 ms 75088 KB Output is correct
18 Correct 761 ms 75020 KB Output is correct
19 Correct 819 ms 73832 KB Output is correct
20 Correct 742 ms 75100 KB Output is correct
21 Correct 751 ms 73696 KB Output is correct
22 Correct 826 ms 76364 KB Output is correct
23 Correct 789 ms 75984 KB Output is correct
24 Correct 782 ms 75216 KB Output is correct
25 Correct 762 ms 75152 KB Output is correct
26 Correct 754 ms 75492 KB Output is correct
27 Correct 750 ms 74168 KB Output is correct
28 Correct 799 ms 76828 KB Output is correct
29 Correct 784 ms 75744 KB Output is correct
30 Correct 770 ms 77072 KB Output is correct
31 Correct 841 ms 75728 KB Output is correct
32 Correct 759 ms 74960 KB Output is correct
33 Runtime error 147 ms 61176 KB Execution killed with signal 4
34 Halted 0 ms 0 KB -