Submission #870621

#	Time	Username	Problem	Language	Result	Execution time	Memory
870621		fanwen	Aesthetic (NOI20_aesthetic)	C++17	100 / 100	359 ms	56076 KiB

Aesthetic

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

const int MAX = 3e5 + 5;
const long long INF = numeric_limits <long long>::max() / 2;

int N, M, low[MAX], num[MAX];
long long dp1[MAX], dpN[MAX];
vector <tuple <int, int, int>> adj[MAX];

long long dijkstra(int source, int target, long long dp[]) {
    fill(dp + 1, dp + N + 1, INF);
    priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> q;
    q.emplace(dp[source] = 0, source);
    while(!q.empty()) {
        auto [du, u] = q.top(); q.pop();
        if(dp[u] != du) continue;
        for (auto [v, w, _] : adj[u]) if(minimize(dp[v], du + w)) {
            q.emplace(dp[v], v);
        }
    }
    return dp[target];
}

bool check(long long val) {
    auto is_correct = [&] (int u, int v, int w, int r) -> bool {
        return dp1[u] + w + r + dpN[v] >= val and dpN[u] + w + r + dp1[v] >= val;
    };

    auto is_edge = [&] (int u, int v, int w) -> bool {
        return dp1[u] + w + dpN[v] < val or dpN[u] + w + dp1[v] < val;
    };

    fill(num + 1, num + N + 1, 0);
    fill(low + 1, low + N + 1, 0);
    int Time = 0;
    bool ans = false;
    function <void(int, int)> dfs = [&] (int u, int p) {
        num[u] = low[u] = ++Time;
        for (auto [v, w, r] : adj[u]) if(v != p && is_edge(u, v, w)) {
            if(!num[v]) {
                dfs(v, u);
                minimize(low[u], low[v]);
                if(low[v] > num[u] and is_correct(u, v, w, r) and low[N] && low[v] <= num[N]) {
                    ans |= true;
                }
            } else minimize(low[u], low[v]);
        }
    };
    dfs(1, 0);

    return ans;
}

void you_make_it(void) {
    cin >> N >> M;
    vector <tuple <int, int, int>> edges(M);
    for (auto &[u, v, w] : edges) cin >> u >> v >> w;
    reverse(ALL(edges));
    int Max = 0;
    for (auto [u, v, w] : edges) {
        adj[u].emplace_back(v, w, Max);
        adj[v].emplace_back(u, w, Max);
        maximize(Max, w);
    }

    long long Min_dist = dijkstra(1, N, dp1); dijkstra(N, 1, dpN);

    long long L = Min_dist, R = Min_dist + Max + 2;
    while(R - L > 1) {
        long long Mid = L + R >> 1;
        if(check(Mid)) L = Mid;
        else R = Mid;
    }
    cout << L;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("Aesthetic");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

Aesthetic.cpp: In function 'void you_make_it()':
Aesthetic.cpp:85:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         long long Mid = L + R >> 1;
      |                         ~~^~~
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:13:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:98:5: note: in expansion of macro 'file'
   98 |     file("Aesthetic");
      |     ^~~~
Aesthetic.cpp:13:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:98:5: note: in expansion of macro 'file'
   98 |     file("Aesthetic");
      |     ^~~~

• 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