oj.uz

Submission #459645

# Submission time Handle Problem Language Result Execution time Memory
459645 2021-08-08T21:32:51 Z nickmet2004 Aesthetic (NOI20_aesthetic) C++11
73 / 100
 855 ms 134560 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n , m ,A, au[300005] , av[300005] , aw[300005];
vector<pair<ll, pair<ll , ll> > >  adj[300005];
ll d1[300005] , dn[300005] , f[300005] , par[300005] , path[300005] , son[300005];
multiset<pair<ll , ll>> S;
vector<ll> B[300005] , T[300005];
void q(ll x){
    f[x] = 1;
    for(auto j : adj[x]){
        //cout << "h";
        ll y = j.first , l = j.second.first;
        auto it = S.find({dn[y] + l + d1[x] , j.second.second});
        if(f[y]==1) S.erase(it);
        if(f[y] == 0) S.insert({dn[x] + l + d1[y] , j.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){
        ll 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;
    priority_queue<pair<ll , ll> > pq;
    pq.push({0 , 1});
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        ll u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            ll v = e.first;
            if(!f[v] && d1[v] > w + e.second.first){
                par[v] = u;
                d1[v] = w + e.second.first;
                pq.push({-d1[v] , v});
            }
        }
        //cout << "k";
    }
    for(int i = 1; i <= n; ++i)f[i] = 0;
    //memset(f , 0 ,sizeof(f));
    pq.push({0, n});
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        ll u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            ll v = e.first;
            if(!f[v] && 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);

    for(int i = 1; i <= n; ++i) f[i] =0;
    ll s = n;
    ll ans = d1[n];
    //cout << "ka";
    while(1){
        //cout << "ha";
        if(s == 1)break;
        for(ll v : T[s]) q(v);
        s = par[s];
        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);
    }
    cout << ans<<endl;

}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21452 KB Output is correct
5 Correct 12 ms 21444 KB Output is correct
6 Correct 12 ms 21528 KB Output is correct
7 Correct 12 ms 21580 KB Output is correct
8 Correct 12 ms 21432 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21452 KB Output is correct
5 Correct 12 ms 21444 KB Output is correct
6 Correct 12 ms 21528 KB Output is correct
7 Correct 12 ms 21580 KB Output is correct
8 Correct 12 ms 21432 KB Output is correct
9 Correct 14 ms 21772 KB Output is correct
10 Correct 14 ms 21824 KB Output is correct
11 Correct 14 ms 21740 KB Output is correct
12 Correct 16 ms 21836 KB Output is correct
13 Correct 16 ms 21760 KB Output is correct
14 Correct 14 ms 21780 KB Output is correct
15 Correct 15 ms 21708 KB Output is correct
16 Correct 13 ms 21708 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 70128 KB Output is correct
2 Correct 763 ms 69696 KB Output is correct
3 Correct 723 ms 69868 KB Output is correct
4 Correct 702 ms 69912 KB Output is correct
5 Correct 704 ms 70196 KB Output is correct
6 Correct 723 ms 71448 KB Output is correct
7 Correct 713 ms 70772 KB Output is correct
8 Correct 753 ms 71572 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 71800 KB Output is correct
2 Correct 756 ms 70556 KB Output is correct
3 Correct 723 ms 68876 KB Output is correct
4 Correct 723 ms 70940 KB Output is correct
5 Correct 729 ms 70728 KB Output is correct
6 Correct 719 ms 71476 KB Output is correct
7 Correct 717 ms 70668 KB Output is correct
8 Correct 706 ms 70860 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 64936 KB Output is correct
2 Correct 309 ms 68852 KB Output is correct
3 Correct 281 ms 59884 KB Output is correct
4 Correct 268 ms 58824 KB Output is correct
5 Correct 260 ms 58496 KB Output is correct
6 Correct 270 ms 59712 KB Output is correct
7 Correct 273 ms 58012 KB Output is correct
8 Correct 272 ms 58604 KB Output is correct
9 Correct 251 ms 57500 KB Output is correct
10 Correct 309 ms 60696 KB Output is correct
11 Correct 257 ms 58076 KB Output is correct
12 Correct 645 ms 65600 KB Output is correct
13 Correct 251 ms 58488 KB Output is correct
14 Correct 266 ms 80872 KB Output is correct
15 Correct 181 ms 70712 KB Output is correct
16 Correct 511 ms 64648 KB Output is correct
17 Correct 560 ms 64772 KB Output is correct
18 Correct 452 ms 63032 KB Output is correct
19 Correct 302 ms 69176 KB Output is correct
20 Correct 301 ms 69044 KB Output is correct
21 Correct 311 ms 69060 KB Output is correct
22 Correct 302 ms 69028 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 64936 KB Output is correct
2 Correct 309 ms 68852 KB Output is correct
3 Correct 281 ms 59884 KB Output is correct
4 Correct 268 ms 58824 KB Output is correct
5 Correct 260 ms 58496 KB Output is correct
6 Correct 270 ms 59712 KB Output is correct
7 Correct 273 ms 58012 KB Output is correct
8 Correct 272 ms 58604 KB Output is correct
9 Correct 251 ms 57500 KB Output is correct
10 Correct 309 ms 60696 KB Output is correct
11 Correct 257 ms 58076 KB Output is correct
12 Correct 645 ms 65600 KB Output is correct
13 Correct 251 ms 58488 KB Output is correct
14 Correct 266 ms 80872 KB Output is correct
15 Correct 181 ms 70712 KB Output is correct
16 Correct 511 ms 64648 KB Output is correct
17 Correct 560 ms 64772 KB Output is correct
18 Correct 452 ms 63032 KB Output is correct
19 Correct 302 ms 69176 KB Output is correct
20 Correct 301 ms 69044 KB Output is correct
21 Correct 311 ms 69060 KB Output is correct
22 Correct 302 ms 69028 KB Output is correct
23 Correct 762 ms 66008 KB Output is correct
24 Correct 361 ms 69136 KB Output is correct
25 Correct 382 ms 58992 KB Output is correct
26 Correct 371 ms 58484 KB Output is correct
27 Correct 364 ms 58476 KB Output is correct
28 Correct 428 ms 60068 KB Output is correct
29 Correct 424 ms 58804 KB Output is correct
30 Correct 377 ms 59328 KB Output is correct
31 Correct 419 ms 59808 KB Output is correct
32 Correct 404 ms 57760 KB Output is correct
33 Correct 441 ms 59456 KB Output is correct
34 Correct 696 ms 65984 KB Output is correct
35 Correct 418 ms 58388 KB Output is correct
36 Correct 291 ms 83808 KB Output is correct
37 Correct 308 ms 83720 KB Output is correct
38 Correct 700 ms 65532 KB Output is correct
39 Correct 721 ms 65344 KB Output is correct
40 Correct 839 ms 66268 KB Output is correct
41 Correct 378 ms 69088 KB Output is correct
42 Correct 357 ms 69092 KB Output is correct
43 Correct 360 ms 69184 KB Output is correct
44 Correct 381 ms 69168 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21452 KB Output is correct
5 Correct 12 ms 21444 KB Output is correct
6 Correct 12 ms 21528 KB Output is correct
7 Correct 12 ms 21580 KB Output is correct
8 Correct 12 ms 21432 KB Output is correct
9 Correct 14 ms 21772 KB Output is correct
10 Correct 14 ms 21824 KB Output is correct
11 Correct 14 ms 21740 KB Output is correct
12 Correct 16 ms 21836 KB Output is correct
13 Correct 16 ms 21760 KB Output is correct
14 Correct 14 ms 21780 KB Output is correct
15 Correct 15 ms 21708 KB Output is correct
16 Correct 13 ms 21708 KB Output is correct
17 Correct 737 ms 70128 KB Output is correct
18 Correct 763 ms 69696 KB Output is correct
19 Correct 723 ms 69868 KB Output is correct
20 Correct 702 ms 69912 KB Output is correct
21 Correct 704 ms 70196 KB Output is correct
22 Correct 723 ms 71448 KB Output is correct
23 Correct 713 ms 70772 KB Output is correct
24 Correct 753 ms 71572 KB Output is correct
25 Correct 733 ms 71800 KB Output is correct
26 Correct 756 ms 70556 KB Output is correct
27 Correct 723 ms 68876 KB Output is correct
28 Correct 723 ms 70940 KB Output is correct
29 Correct 729 ms 70728 KB Output is correct
30 Correct 719 ms 71476 KB Output is correct
31 Correct 717 ms 70668 KB Output is correct
32 Correct 706 ms 70860 KB Output is correct
33 Correct 541 ms 64936 KB Output is correct
34 Correct 309 ms 68852 KB Output is correct
35 Correct 281 ms 59884 KB Output is correct
36 Correct 268 ms 58824 KB Output is correct
37 Correct 260 ms 58496 KB Output is correct
38 Correct 270 ms 59712 KB Output is correct
39 Correct 273 ms 58012 KB Output is correct
40 Correct 272 ms 58604 KB Output is correct
41 Correct 251 ms 57500 KB Output is correct
42 Correct 309 ms 60696 KB Output is correct
43 Correct 257 ms 58076 KB Output is correct
44 Correct 645 ms 65600 KB Output is correct
45 Correct 251 ms 58488 KB Output is correct
46 Correct 266 ms 80872 KB Output is correct
47 Correct 181 ms 70712 KB Output is correct
48 Correct 511 ms 64648 KB Output is correct
49 Correct 560 ms 64772 KB Output is correct
50 Correct 452 ms 63032 KB Output is correct
51 Correct 302 ms 69176 KB Output is correct
52 Correct 301 ms 69044 KB Output is correct
53 Correct 311 ms 69060 KB Output is correct
54 Correct 302 ms 69028 KB Output is correct
55 Correct 762 ms 66008 KB Output is correct
56 Correct 361 ms 69136 KB Output is correct
57 Correct 382 ms 58992 KB Output is correct
58 Correct 371 ms 58484 KB Output is correct
59 Correct 364 ms 58476 KB Output is correct
60 Correct 428 ms 60068 KB Output is correct
61 Correct 424 ms 58804 KB Output is correct
62 Correct 377 ms 59328 KB Output is correct
63 Correct 419 ms 59808 KB Output is correct
64 Correct 404 ms 57760 KB Output is correct
65 Correct 441 ms 59456 KB Output is correct
66 Correct 696 ms 65984 KB Output is correct
67 Correct 418 ms 58388 KB Output is correct
68 Correct 291 ms 83808 KB Output is correct
69 Correct 308 ms 83720 KB Output is correct
70 Correct 700 ms 65532 KB Output is correct
71 Correct 721 ms 65344 KB Output is correct
72 Correct 839 ms 66268 KB Output is correct
73 Correct 378 ms 69088 KB Output is correct
74 Correct 357 ms 69092 KB Output is correct
75 Correct 360 ms 69184 KB Output is correct
76 Correct 381 ms 69168 KB Output is correct
77 Correct 855 ms 66688 KB Output is correct
78 Correct 372 ms 69096 KB Output is correct
79 Correct 460 ms 59144 KB Output is correct
80 Correct 457 ms 57940 KB Output is correct
81 Correct 429 ms 59164 KB Output is correct
82 Correct 518 ms 58932 KB Output is correct
83 Correct 447 ms 58252 KB Output is correct
84 Correct 517 ms 58436 KB Output is correct
85 Correct 450 ms 59620 KB Output is correct
86 Correct 438 ms 59140 KB Output is correct
87 Correct 428 ms 58304 KB Output is correct
88 Correct 632 ms 65832 KB Output is correct
89 Correct 419 ms 58944 KB Output is correct
90 Correct 327 ms 83744 KB Output is correct
91 Correct 361 ms 83644 KB Output is correct
92 Runtime error 786 ms 134560 KB Execution killed with signal 6
93 Halted 0 ms 0 KB -