oj.uz

답안 #459530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
459530 2021-08-08T15:14:20 Z nickmet2004 Aesthetic (NOI20_aesthetic) C++11
35 / 100
 813 ms 137436 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(d1[v] > w + e.second.first){
                par[v] = u;
                d1[v] = w + e.second.first;
                pq.push({-d1[v] , v});
            }
        }
        //cout << "k";
    }

    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(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);

    memset(f , 0 ,sizeof(f));
    u = n;
    ll ans = 0;
    //cout << "ka";

    while(1){
        //cout << "ha";
        for(ll v : T[u]) q(v);
        //if(!S.size())continue;
        if(u == 1)break;
        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);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23884 KB Output is correct
2 Correct 14 ms 23780 KB Output is correct
3 Correct 14 ms 23852 KB Output is correct
4 Correct 15 ms 23780 KB Output is correct
5 Correct 15 ms 23884 KB Output is correct
6 Correct 16 ms 23772 KB Output is correct
7 Correct 17 ms 23804 KB Output is correct
8 Correct 15 ms 23796 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23884 KB Output is correct
2 Correct 14 ms 23780 KB Output is correct
3 Correct 14 ms 23852 KB Output is correct
4 Correct 15 ms 23780 KB Output is correct
5 Correct 15 ms 23884 KB Output is correct
6 Correct 16 ms 23772 KB Output is correct
7 Correct 17 ms 23804 KB Output is correct
8 Correct 15 ms 23796 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 17 ms 24196 KB Output is correct
11 Correct 16 ms 24168 KB Output is correct
12 Correct 16 ms 24088 KB Output is correct
13 Correct 16 ms 24164 KB Output is correct
14 Correct 17 ms 24140 KB Output is correct
15 Correct 19 ms 24092 KB Output is correct
16 Correct 16 ms 24140 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 790 ms 76824 KB Output is correct
2 Correct 799 ms 76292 KB Output is correct
3 Correct 776 ms 76352 KB Output is correct
4 Correct 805 ms 76516 KB Output is correct
5 Correct 762 ms 76760 KB Output is correct
6 Correct 754 ms 78060 KB Output is correct
7 Correct 813 ms 77456 KB Output is correct
8 Correct 744 ms 78212 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 725 ms 78404 KB Output is correct
2 Correct 729 ms 77124 KB Output is correct
3 Correct 727 ms 75616 KB Output is correct
4 Correct 738 ms 77764 KB Output is correct
5 Correct 728 ms 77424 KB Output is correct
6 Correct 763 ms 78108 KB Output is correct
7 Correct 736 ms 77384 KB Output is correct
8 Correct 742 ms 77552 KB Output is correct

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 764 ms 137436 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 764 ms 137436 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23884 KB Output is correct
2 Correct 14 ms 23780 KB Output is correct
3 Correct 14 ms 23852 KB Output is correct
4 Correct 15 ms 23780 KB Output is correct
5 Correct 15 ms 23884 KB Output is correct
6 Correct 16 ms 23772 KB Output is correct
7 Correct 17 ms 23804 KB Output is correct
8 Correct 15 ms 23796 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 17 ms 24196 KB Output is correct
11 Correct 16 ms 24168 KB Output is correct
12 Correct 16 ms 24088 KB Output is correct
13 Correct 16 ms 24164 KB Output is correct
14 Correct 17 ms 24140 KB Output is correct
15 Correct 19 ms 24092 KB Output is correct
16 Correct 16 ms 24140 KB Output is correct
17 Correct 790 ms 76824 KB Output is correct
18 Correct 799 ms 76292 KB Output is correct
19 Correct 776 ms 76352 KB Output is correct
20 Correct 805 ms 76516 KB Output is correct
21 Correct 762 ms 76760 KB Output is correct
22 Correct 754 ms 78060 KB Output is correct
23 Correct 813 ms 77456 KB Output is correct
24 Correct 744 ms 78212 KB Output is correct
25 Correct 725 ms 78404 KB Output is correct
26 Correct 729 ms 77124 KB Output is correct
27 Correct 727 ms 75616 KB Output is correct
28 Correct 738 ms 77764 KB Output is correct
29 Correct 728 ms 77424 KB Output is correct
30 Correct 763 ms 78108 KB Output is correct
31 Correct 736 ms 77384 KB Output is correct
32 Correct 742 ms 77552 KB Output is correct
33 Runtime error 764 ms 137436 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -