Submission #317765

#	Time	Username	Problem	Language	Result	Execution time	Memory
317765		parsabahrami	Aesthetic (NOI20_aesthetic)	C++17	100 / 100	1054 ms	85752 KiB

Aesthetic

//! The Leader Of Retards Bemola
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
 
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 3e5 + 10;
const long long int INF = 1e18;
const ll MOD  = 1e9 + 7;
ll chk[2][MAXN], L[MAXN], mn[MAXN], mark[MAXN], n, m, s, t, timer, f = 0; long long int ans = 0, dist[2][MAXN], W[MAXN], mx[MAXN];
vector<pair<long long int, ll>> adj[2][MAXN]; pll E[MAXN];
 
void Dijkstra(ll St, ll ind) {
    priority_queue<pair<long long int, ll>> pq;
    pq.push({0, St});
    dist[ind][St] = 0;
    while (sz(pq)) {
        ll v = pq.top().S;
        pq.pop();
        if (mark[v]) continue;
        mark[v] = 1;
        for (pll nei: adj[0][v]) {
            ll u = nei.F, w = nei.S;
            if (mark[u]) continue;
            if (dist[ind][u] > dist[ind][v] + w) {
                dist[ind][u] = dist[ind][v] + w;
                pq.push({-dist[ind][u], u});
            }
        }
    }
    return;
}
 
void DFS(ll v, long long int x, ll p = -1) {
    assert(L[v] == 0 && mn[v] == MOD);
    mn[v] = L[v] = timer++;
    mark[v] = 1;
    for (pll nei : adj[1][v]) {
        ll u = nei.F, id = nei.S;
        if (chk[0][id] == 0) continue;
        if (mark[u] == 0) {
            DFS(u, x, v);
            if (mn[u] > L[v] && L[n] >= L[u] && chk[1][id]) f = 1;
            else  mn[v] = min(mn[v], mn[u]);
        } else if (u != p) {
            mn[v] = min(mn[v], L[u]);
        }
    }
}

ll check(long long int x) {
    for (ll i = 1; i <= m; i++) {
        ll u = E[i].F, v = E[i].S;
        chk[0][i] = bool(min(dist[0][u] + W[i] + dist[1][v], dist[0][v] + W[i] + dist[1][u]) <= x);
        chk[1][i] = bool(min(dist[0][u] + W[i] + dist[1][v], dist[0][v] + W[i] + dist[1][u]) + mx[i + 1] > x);
    }
    fill(mn + 1, mn + n + 1, MOD);
    fill(L + 1, L + n + 1, 0);
    memset(mark, 0, sizeof mark);
    timer = 1; f = 0;
    DFS(s, x);
    if (f || L[n] == 0) return 1;
    return 0;
}

int main() {
    fill(dist[0], dist[0] + MAXN, INF);
    fill(dist[1], dist[1] + MAXN, INF);
    scanf("%d%d", &n, &m);
    for (ll i = 1; i <= m; i++) {
        ll u, v; long long int w;
        scanf("%d%d%lld", &u, &v, &w);
        adj[0][u].push_back({v, w});
        adj[0][v].push_back({u, w});
        adj[1][u].push_back({v, i});
        adj[1][v].push_back({u, i});
        W[i] = w;
        E[i] = {u, v};
    }
    for (ll i = m; i >= 1; i--) {
        mx[i] = max(mx[i + 1], W[i]);
    }
    s = 1, t = n;
    Dijkstra(s, 0);
    memset(mark, 0, sizeof mark);
    Dijkstra(t, 1);
    long long int l = dist[0][t], r = dist[0][t] + mx[1] + 1;
    while (r - l > 1) {
        long long int mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    //printf("%d\n", check(9));
    if (check(l)) l++;
    printf("%lld\n", l);
    return 0;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Aesthetic.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |         scanf("%d%d%lld", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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