Submission #1299507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299507		KhanhDang	Aesthetic (NOI20_aesthetic)	C++20	100 / 100	425 ms	57924 KiB

Aesthetic

#include<bits/stdc++.h>
using namespace std;
#define     ll long long
#define    pll pair<ll, ll>
#define    pii pair<int, int>
#define     fi first
#define     se second
#define all(v) (v).begin(), (v).end()
#define Unique(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());

const int N = 3e5 + 5;

int n, m;
int w[N], p[N];

vector<pii> adj[N];

ll d1[N], dn[N];

void Dijkstra(int s, ll dist[]) {
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    dist[s] = 0; pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d != dist[u]) continue;

        for (auto [v, id] : adj[u]) {
            if (dist[v] > d + w[id]) {
                dist[v] = d + w[id];
                pq.push({dist[v], v});
            }
        }
    }
}

vector<pii> g[N];
bool mark[N];

int id;
int low[N], num[N];
int tin[N], tout[N];

bool Dfs(int u, int p_id, ll len) {
    num[u] = low[u] = ++id;
    tin[u] = id;

    for (auto [v, i] : g[u]) {
        if (i == p_id) continue;

        if (!num[v]) {
            if (Dfs(v, i, len)) return true;

            low[u] = min(low[u], low[v]);

            if (low[v] == num[v] && tin[v] <= tin[n] && tout[n] <= tout[v]) {
                if (d1[u] + w[i] + p[i] + dn[v] > len &&
                    d1[v] + w[i] + p[i] + dn[u] > len)
                        return true;
            }
        }
        else low[u] = min(low[u], num[v]);
    }

    tout[u] = id;

    return false;
}

bool check(ll len) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();

        low[i] = num[i] = 0;
        tin[i] = tout[i] = 0;
    }

    for (int i = 1; i <= m; i++)
        mark[i] = false;

    for (int u = 1; u <= n; u++) {
        for (auto [v, i] : adj[u]) {

            if (!mark[i] && (d1[u] + w[i] + dn[v] <= len || d1[v] + w[i] + dn[u] <= len)) {
                mark[i] = true;

                g[u].emplace_back(v, i);
                g[v].emplace_back(u, i);
            }
        }
    }

    id = 0; return Dfs(1, -1, len);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "beautiful"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if (fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }

    cin>>n>>m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin>>u>>v>>w[i];

        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }

    for (int i = m; i >= 1; i--)
        p[i] = max(p[i + 1], w[i + 1]);

    memset(d1, 0x3f, sizeof d1); Dijkstra(1, d1);
    memset(dn, 0x3f, sizeof dn); Dijkstra(n, dn);

    ll l = d1[n];
    ll r = l + p[1];

    ll ans = d1[n] - 1;

    while (l <= r) {
        ll mid = (l + r) >> 1;

        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }

    cout<<ans + 1;

    cerr<<setprecision(3)<<fixed<<"Time elapsed: "<< 1.0 * clock() / CLOCKS_PER_SEC <<"s\n";
}

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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