oj.uz

Submission #459616

# Submission time Handle Problem Language Result Execution time Memory
459616 2021-08-08T20:41:27 Z nickmet2004 Aesthetic (NOI20_aesthetic) C++11
73 / 100
 801 ms 134584 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 5;
ll n , m , au[N] , av[N] , aw[N];
ll u , v , w , A = 0;
vector<pair<ll, pair<ll , ll> > >  adj[N];
ll d1[N] , dn[N] , f[N] , par[N] , path[N] , son[N];
priority_queue<pair<ll , ll> > pq;
multiset<pair<ll , ll>> S;
vector<ll> B[N] , T[N];
void q(int x){
    f[x] = 1;
    for(auto y : adj[x]){
        //cout << "h";
        auto it = S.find({dn[y.first] + y.second.first + d1[x] , y.second.second});
        if(f[y.first]) S.erase(it);
        else S.insert({dn[x] + y.second.first + d1[y.first] , y.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){
        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;
    pq.push({0 , 1});
    while(pq.size()){
        auto T = pq.top(); pq.pop();
        u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            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();
        u = T.second , w = -T.first;
        if(f[u])continue;
        f[u] = 1;
        for(auto e : adj[u]){
            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;
    u = n;
    ll ans = d1[n];
    //cout << "ka";
    ll k;
    while(1){
        //cout << "ha";
        if(u == 1)break;
        for(ll v : T[u]) q(v);
        //if(!S.size())continue;
        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);
        u = par[u];
    }
    cout << ans;

}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21548 KB Output is correct
2 Correct 12 ms 21512 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21532 KB Output is correct
5 Correct 12 ms 21452 KB Output is correct
6 Correct 12 ms 21532 KB Output is correct
7 Correct 12 ms 21540 KB Output is correct
8 Correct 12 ms 21452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21548 KB Output is correct
2 Correct 12 ms 21512 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21532 KB Output is correct
5 Correct 12 ms 21452 KB Output is correct
6 Correct 12 ms 21532 KB Output is correct
7 Correct 12 ms 21540 KB Output is correct
8 Correct 12 ms 21452 KB Output is correct
9 Correct 14 ms 21728 KB Output is correct
10 Correct 14 ms 21768 KB Output is correct
11 Correct 14 ms 21708 KB Output is correct
12 Correct 15 ms 21820 KB Output is correct
13 Correct 13 ms 21708 KB Output is correct
14 Correct 13 ms 21708 KB Output is correct
15 Correct 13 ms 21724 KB Output is correct
16 Correct 14 ms 21792 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 70168 KB Output is correct
2 Correct 706 ms 69512 KB Output is correct
3 Correct 717 ms 69760 KB Output is correct
4 Correct 702 ms 69824 KB Output is correct
5 Correct 725 ms 70284 KB Output is correct
6 Correct 740 ms 71384 KB Output is correct
7 Correct 708 ms 70776 KB Output is correct
8 Correct 751 ms 71444 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 71724 KB Output is correct
2 Correct 719 ms 70620 KB Output is correct
3 Correct 730 ms 68824 KB Output is correct
4 Correct 706 ms 71024 KB Output is correct
5 Correct 697 ms 70588 KB Output is correct
6 Correct 704 ms 71476 KB Output is correct
7 Correct 696 ms 70660 KB Output is correct
8 Correct 731 ms 70864 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 64928 KB Output is correct
2 Correct 298 ms 68768 KB Output is correct
3 Correct 286 ms 59860 KB Output is correct
4 Correct 261 ms 58680 KB Output is correct
5 Correct 262 ms 58492 KB Output is correct
6 Correct 272 ms 59700 KB Output is correct
7 Correct 256 ms 57984 KB Output is correct
8 Correct 260 ms 58524 KB Output is correct
9 Correct 261 ms 57540 KB Output is correct
10 Correct 276 ms 60620 KB Output is correct
11 Correct 259 ms 58172 KB Output is correct
12 Correct 611 ms 65648 KB Output is correct
13 Correct 253 ms 58520 KB Output is correct
14 Correct 247 ms 80932 KB Output is correct
15 Correct 179 ms 70724 KB Output is correct
16 Correct 487 ms 64756 KB Output is correct
17 Correct 559 ms 64816 KB Output is correct
18 Correct 470 ms 63008 KB Output is correct
19 Correct 303 ms 69192 KB Output is correct
20 Correct 301 ms 69100 KB Output is correct
21 Correct 299 ms 69064 KB Output is correct
22 Correct 302 ms 69100 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 64928 KB Output is correct
2 Correct 298 ms 68768 KB Output is correct
3 Correct 286 ms 59860 KB Output is correct
4 Correct 261 ms 58680 KB Output is correct
5 Correct 262 ms 58492 KB Output is correct
6 Correct 272 ms 59700 KB Output is correct
7 Correct 256 ms 57984 KB Output is correct
8 Correct 260 ms 58524 KB Output is correct
9 Correct 261 ms 57540 KB Output is correct
10 Correct 276 ms 60620 KB Output is correct
11 Correct 259 ms 58172 KB Output is correct
12 Correct 611 ms 65648 KB Output is correct
13 Correct 253 ms 58520 KB Output is correct
14 Correct 247 ms 80932 KB Output is correct
15 Correct 179 ms 70724 KB Output is correct
16 Correct 487 ms 64756 KB Output is correct
17 Correct 559 ms 64816 KB Output is correct
18 Correct 470 ms 63008 KB Output is correct
19 Correct 303 ms 69192 KB Output is correct
20 Correct 301 ms 69100 KB Output is correct
21 Correct 299 ms 69064 KB Output is correct
22 Correct 302 ms 69100 KB Output is correct
23 Correct 693 ms 66052 KB Output is correct
24 Correct 361 ms 69280 KB Output is correct
25 Correct 371 ms 58944 KB Output is correct
26 Correct 357 ms 58560 KB Output is correct
27 Correct 342 ms 58296 KB Output is correct
28 Correct 429 ms 60000 KB Output is correct
29 Correct 393 ms 58656 KB Output is correct
30 Correct 376 ms 59244 KB Output is correct
31 Correct 392 ms 59756 KB Output is correct
32 Correct 392 ms 57792 KB Output is correct
33 Correct 431 ms 59320 KB Output is correct
34 Correct 745 ms 66068 KB Output is correct
35 Correct 414 ms 58600 KB Output is correct
36 Correct 287 ms 83688 KB Output is correct
37 Correct 304 ms 83648 KB Output is correct
38 Correct 662 ms 65448 KB Output is correct
39 Correct 683 ms 65272 KB Output is correct
40 Correct 756 ms 66372 KB Output is correct
41 Correct 358 ms 69124 KB Output is correct
42 Correct 361 ms 69176 KB Output is correct
43 Correct 357 ms 69060 KB Output is correct
44 Correct 359 ms 69140 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21548 KB Output is correct
2 Correct 12 ms 21512 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21532 KB Output is correct
5 Correct 12 ms 21452 KB Output is correct
6 Correct 12 ms 21532 KB Output is correct
7 Correct 12 ms 21540 KB Output is correct
8 Correct 12 ms 21452 KB Output is correct
9 Correct 14 ms 21728 KB Output is correct
10 Correct 14 ms 21768 KB Output is correct
11 Correct 14 ms 21708 KB Output is correct
12 Correct 15 ms 21820 KB Output is correct
13 Correct 13 ms 21708 KB Output is correct
14 Correct 13 ms 21708 KB Output is correct
15 Correct 13 ms 21724 KB Output is correct
16 Correct 14 ms 21792 KB Output is correct
17 Correct 706 ms 70168 KB Output is correct
18 Correct 706 ms 69512 KB Output is correct
19 Correct 717 ms 69760 KB Output is correct
20 Correct 702 ms 69824 KB Output is correct
21 Correct 725 ms 70284 KB Output is correct
22 Correct 740 ms 71384 KB Output is correct
23 Correct 708 ms 70776 KB Output is correct
24 Correct 751 ms 71444 KB Output is correct
25 Correct 705 ms 71724 KB Output is correct
26 Correct 719 ms 70620 KB Output is correct
27 Correct 730 ms 68824 KB Output is correct
28 Correct 706 ms 71024 KB Output is correct
29 Correct 697 ms 70588 KB Output is correct
30 Correct 704 ms 71476 KB Output is correct
31 Correct 696 ms 70660 KB Output is correct
32 Correct 731 ms 70864 KB Output is correct
33 Correct 564 ms 64928 KB Output is correct
34 Correct 298 ms 68768 KB Output is correct
35 Correct 286 ms 59860 KB Output is correct
36 Correct 261 ms 58680 KB Output is correct
37 Correct 262 ms 58492 KB Output is correct
38 Correct 272 ms 59700 KB Output is correct
39 Correct 256 ms 57984 KB Output is correct
40 Correct 260 ms 58524 KB Output is correct
41 Correct 261 ms 57540 KB Output is correct
42 Correct 276 ms 60620 KB Output is correct
43 Correct 259 ms 58172 KB Output is correct
44 Correct 611 ms 65648 KB Output is correct
45 Correct 253 ms 58520 KB Output is correct
46 Correct 247 ms 80932 KB Output is correct
47 Correct 179 ms 70724 KB Output is correct
48 Correct 487 ms 64756 KB Output is correct
49 Correct 559 ms 64816 KB Output is correct
50 Correct 470 ms 63008 KB Output is correct
51 Correct 303 ms 69192 KB Output is correct
52 Correct 301 ms 69100 KB Output is correct
53 Correct 299 ms 69064 KB Output is correct
54 Correct 302 ms 69100 KB Output is correct
55 Correct 693 ms 66052 KB Output is correct
56 Correct 361 ms 69280 KB Output is correct
57 Correct 371 ms 58944 KB Output is correct
58 Correct 357 ms 58560 KB Output is correct
59 Correct 342 ms 58296 KB Output is correct
60 Correct 429 ms 60000 KB Output is correct
61 Correct 393 ms 58656 KB Output is correct
62 Correct 376 ms 59244 KB Output is correct
63 Correct 392 ms 59756 KB Output is correct
64 Correct 392 ms 57792 KB Output is correct
65 Correct 431 ms 59320 KB Output is correct
66 Correct 745 ms 66068 KB Output is correct
67 Correct 414 ms 58600 KB Output is correct
68 Correct 287 ms 83688 KB Output is correct
69 Correct 304 ms 83648 KB Output is correct
70 Correct 662 ms 65448 KB Output is correct
71 Correct 683 ms 65272 KB Output is correct
72 Correct 756 ms 66372 KB Output is correct
73 Correct 358 ms 69124 KB Output is correct
74 Correct 361 ms 69176 KB Output is correct
75 Correct 357 ms 69060 KB Output is correct
76 Correct 359 ms 69140 KB Output is correct
77 Correct 801 ms 66756 KB Output is correct
78 Correct 368 ms 69184 KB Output is correct
79 Correct 475 ms 59144 KB Output is correct
80 Correct 440 ms 57924 KB Output is correct
81 Correct 423 ms 59196 KB Output is correct
82 Correct 461 ms 58964 KB Output is correct
83 Correct 441 ms 58384 KB Output is correct
84 Correct 452 ms 58448 KB Output is correct
85 Correct 401 ms 59448 KB Output is correct
86 Correct 439 ms 59128 KB Output is correct
87 Correct 421 ms 58300 KB Output is correct
88 Correct 613 ms 65672 KB Output is correct
89 Correct 427 ms 58940 KB Output is correct
90 Correct 311 ms 83752 KB Output is correct
91 Correct 357 ms 83712 KB Output is correct
92 Runtime error 769 ms 134584 KB Execution killed with signal 6
93 Halted 0 ms 0 KB -