Submission #1299481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299481		KhanhDang	Aesthetic (NOI20_aesthetic)	C++20	16 / 100	429 ms	53888 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});
            }
        }
    }
}

int par[N];

int findSet(int u) {
    return (u == par[u] ? u : par[u] = findSet(par[u]));
}

void UnionSet(int u, int v) {
    u = findSet(u);
    v = findSet(v);

    par[u] = v;
}

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

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

bool Dfs(int u, int p_id, ll len) {
    num[u] = low[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]) {
                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]);
    }

    return false;
}

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

        low[i] = num[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);

                UnionSet(u, v);
            }
        }
    }

    if (findSet(1) != findSet(n)) return false;

    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:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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