Submission #959933

#	Time	Username	Problem	Language	Result	Execution time	Memory
959933		Cookie	Aesthetic (NOI20_aesthetic)	C++14	100 / 100	515 ms	74440 KiB

Aesthetic

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 69, pr = 31;
const int mxn = 3e5 + 5, mxq = 1e5 + 5, sq = 300, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e18 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
// <3;

int n, m;
ll eu[mxn + 1], ev[mxn + 1], ew[mxn + 1], mx[mxn + 1];
vt<pll>adj[mxn + 1];
struct D{
    ll dis[mxn + 1];
    void go(int s){
        for(int i = 1; i <= n; i++){
            dis[i] = inf;
        }
        dis[s] = 0;
        priority_queue<pll, vt<pll>, greater<pll>>pq;
        pq.push(mpp(dis[s], s));
        while(!pq.empty()){
            auto [dd, u] = pq.top(); pq.pop();
            for(auto [v, w]: adj[u]){
                if(dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    pq.push(mpp(dis[v], v));
                }
            }
        }
    }
};
D d1, dn;
int low[mxn + 1], num[mxn + 1], tt = 0;
bool contain[mxn + 1];
vt<pii>g[mxn + 1];
bool ok = 0;
void dfs(int s, int pre, ll mid){
    if(s == n)contain[s] = 1;
    low[s] = num[s] = ++tt;
    for(auto [v, id]: g[s]){
        if(id == pre){
            continue;
        }
        if(!num[v]){
            dfs(v, id, mid); contain[s] |= contain[v];
            //cout << low[v] << " " << num[v] << " ";
            low[s] = min(low[s], low[v]);
            if(low[v] == num[v] && contain[v]){
                if(d1.dis[eu[id]] + dn.dis[ev[id]] + ew[id] == d1.dis[n] && d1.dis[eu[id]] + dn.dis[ev[id]] + ew[id] + mx[id] >= d1.dis[n] + mid){
                    ok = 1;
                    //cout << eu[id] << " " << ev[id] << " " << ew[id] << " " << mx[id] << "\n";
                }
            }
        }else{
            low[s] = min(low[s], num[v]);
        }
    }
}
bool ck(ll mid){
   
    for(int i = 1; i <= n; i++){
        g[i].clear(); low[i] = num[i] = 0; contain[i] = 0;
    }
    tt = 0; ok = 0;
    for(int i = 0; i < m; i++){
        ll u = eu[i], v = ev[i], w = ew[i];
        if(d1.dis[u] + dn.dis[v] + ew[i] < d1.dis[n] + mid){
            
            g[u].pb(mpp(v, i)); g[v].pb(mpp(u, i));
        }else if(d1.dis[v] + dn.dis[u] + ew[i] < d1.dis[n] + mid){
            g[u].pb(mpp(v, i)); g[v].pb(mpp(u, i));
        }
    }
    dfs(1, -1, mid);
    //cout << ok << " ";
    return(ok);
}
void solve(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> eu[i] >> ev[i] >> ew[i];
       
        adj[eu[i]].pb(mpp(ev[i], ew[i])); adj[ev[i]].pb(mpp(eu[i], ew[i]));
    }
    for(int i = m - 2; i >= 0; i--){
        mx[i] = max(mx[i + 1], ew[i + 1]);
    }
    d1.go(1); dn.go(n);
    for(int i = 0; i < m; i++){
        if(d1.dis[eu[i]] > d1.dis[ev[i]])swap(eu[i], ev[i]);
    }
    
    

    ll l = 1, r = *max_element(ew + 1, ew + m + 1), ans = 0;
    while(l <= r){
        ll mid = (l + r) >> 1;
        if(ck(mid)){
            ans = mid; l = mid + 1;
        }else{
            r = mid - 1;
        }
    }

    cout << d1.dis[n] + ans;
    

}


signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("netw.inp", "r", stdin);
    //freopen("netw.out", "w", stdout);
    int ttt; ttt = 1;
    while(ttt--){
        solve();

    }
    return(0);
}
/*
1
5 7 2
1 1 1
3 1 2
2 2 3
4 2 4
2 4 2
1 5 5
3 5 2
5 3
2 7
3 3 1
1 1 1
1 2 2
1 3 3
3 1
*/

Compilation message (stderr)

Aesthetic.cpp: In member function 'void D::go(int)':
Aesthetic.cpp:44:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |             auto [dd, u] = pq.top(); pq.pop();
      |                  ^
Aesthetic.cpp:45:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |             for(auto [v, w]: adj[u]){
      |                      ^
Aesthetic.cpp: In function 'void dfs(int, int, long long int)':
Aesthetic.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [v, id]: g[s]){
      |              ^
Aesthetic.cpp: In function 'bool ck(long long int)':
Aesthetic.cpp:88:34: warning: unused variable 'w' [-Wunused-variable]
   88 |         ll u = eu[i], v = ev[i], w = ew[i];
      |                                  ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27