oj.uz

Submission #1087626

# Submission time Handle Problem Language Result Execution time Memory
1087626 2024-09-13T03:19:14 Z Whisper Aesthetic (NOI20_aesthetic) C++17
35 / 100
 709 ms 51948 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX                 300005
int numNode, numEdge;
vector<int> G[MAX];
struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}

    int other(int x){return (x ^ u ^ v);}
} edge[MAX];
int minDist[2][MAX];

void dijkstra(int s, int minDist[]){
    for (int i = 1; i <= numNode; ++i) minDist[i] = LINF;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.emplace(0, s);
    minDist[s] = 0;
    while(q.size()){
        int du, u; tie(du, u) = q.top(); q.pop();
        if(du > minDist[u]) continue;

        for(int&i : G[u]) {
            int v = edge[i].other(u);
            if(minimize(minDist[v], minDist[u] + edge[i].w)){
                q.emplace(minDist[v], v);
            }
        }
    }
}

int low[MAX], num[MAX], timeDfs = 0;

int suffix[MAX];
bool contain[MAX];
vector<pair<int, int>> newG[MAX];
bool ok = 0;

int value = 0;
void tarjan(int u, int p){
    if(u == numNode) contain[u] = true;
    low[u] = num[u] = ++timeDfs;
    for (pair<int, int>&x : newG[u]){
        int v = x.first, i = x.second;
        if(i ^ p){
            if(num[v]) minimize(low[u], num[v]);
            else{
                tarjan(v, i);
                minimize(low[u], low[v]);
                contain[u] |= contain[v];

                if(num[v] == low[v]){
                    if(!contain[v]) continue;
                    int eu = edge[i].u, ev = edge[i].v;
                    if(minDist[0][eu] + edge[i].w + minDist[1][ev] != minDist[0][numNode]) continue;
                    if(minDist[0][eu] + edge[i].w + minDist[1][ev] + suffix[i] >= minDist[0][numNode] + value)
                        ok = 1;
                }
            }
        }
    }
}

void process(void){
    cin >> numNode >> numEdge;
    int max_weight = 0;
    for (int i = 1; i <= numEdge; ++i){
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
        G[edge[i].u].emplace_back(i);
        G[edge[i].v].emplace_back(i);
        maximize(max_weight, edge[i].w);
    }

    dijkstra(1, minDist[0]);
    dijkstra(numNode, minDist[1]);

    suffix[numEdge] = -LINF;
    for (int i = numEdge - 1; i >= 1; --i){
        maximize(suffix[i], suffix[i + 1]);
        maximize(suffix[i], edge[i + 1].w);
    }

    for (int i = 1; i <= numEdge; ++i){
        if(minDist[0][edge[i].u] > minDist[0][edge[i].v]) swap(edge[i].u, edge[i].v);
    }
    int l = 0, r = max_weight;
    int add = 0;

    auto check = [&](int val) -> bool{
        timeDfs = 0, ok = 0;
        value = val;
        for (int i = 1; i <= numNode; ++i) newG[i].clear(), contain[i] = num[i] = low[i] = 0;

        auto active = [&](int u, int v, int w, int x) -> bool{
            if(minDist[0][u] + minDist[1][v] + w < minDist[0][numNode] + x) return true;
            if(minDist[0][v] + minDist[1][u] + w < minDist[0][numNode] + x) return true;
            return false;
        };

        for (int u = 1; u <= numNode; ++u){
            for (int&i : G[u]){
                int v = edge[i].other(u);
                if(active(u, v, edge[i].w, val)) {
                    newG[u].emplace_back(v, i);
                }
            }
        }
        tarjan(1, 0);
        return (ok);
    };

    while(l <= r){
        int m = (l + r) >> 1;
        if(check(m)) l = m + 1, add = m;
        else r = m - 1;
    }

    cout << minDist[0][numNode] + add;
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Compilation message

Aesthetic.cpp: In lambda function:
Aesthetic.cpp:128:81: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  128 |         for (int i = 1; i <= numNode; ++i) newG[i].clear(), contain[i] = num[i] = low[i] = 0;
      |                                                                          ~~~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 7 ms 14584 KB Output is correct
4 Correct 7 ms 14428 KB Output is correct
5 Correct 6 ms 14384 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 7 ms 14400 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 7 ms 14584 KB Output is correct
4 Correct 7 ms 14428 KB Output is correct
5 Correct 6 ms 14384 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 7 ms 14400 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 8 ms 14684 KB Output is correct
10 Correct 7 ms 14732 KB Output is correct
11 Correct 7 ms 14684 KB Output is correct
12 Correct 8 ms 14684 KB Output is correct
13 Correct 8 ms 14840 KB Output is correct
14 Correct 8 ms 14684 KB Output is correct
15 Correct 8 ms 14684 KB Output is correct
16 Correct 7 ms 14684 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 51028 KB Output is correct
2 Correct 621 ms 51284 KB Output is correct
3 Correct 638 ms 50876 KB Output is correct
4 Correct 609 ms 50876 KB Output is correct
5 Correct 709 ms 51108 KB Output is correct
6 Correct 674 ms 51792 KB Output is correct
7 Correct 637 ms 51536 KB Output is correct
8 Correct 684 ms 51792 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 51948 KB Output is correct
2 Correct 633 ms 51332 KB Output is correct
3 Correct 658 ms 50960 KB Output is correct
4 Correct 669 ms 51764 KB Output is correct
5 Correct 655 ms 51028 KB Output is correct
6 Correct 667 ms 51184 KB Output is correct
7 Correct 641 ms 51052 KB Output is correct
8 Correct 669 ms 51320 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 44968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 44968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 7 ms 14584 KB Output is correct
4 Correct 7 ms 14428 KB Output is correct
5 Correct 6 ms 14384 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 7 ms 14400 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 8 ms 14684 KB Output is correct
10 Correct 7 ms 14732 KB Output is correct
11 Correct 7 ms 14684 KB Output is correct
12 Correct 8 ms 14684 KB Output is correct
13 Correct 8 ms 14840 KB Output is correct
14 Correct 8 ms 14684 KB Output is correct
15 Correct 8 ms 14684 KB Output is correct
16 Correct 7 ms 14684 KB Output is correct
17 Correct 635 ms 51028 KB Output is correct
18 Correct 621 ms 51284 KB Output is correct
19 Correct 638 ms 50876 KB Output is correct
20 Correct 609 ms 50876 KB Output is correct
21 Correct 709 ms 51108 KB Output is correct
22 Correct 674 ms 51792 KB Output is correct
23 Correct 637 ms 51536 KB Output is correct
24 Correct 684 ms 51792 KB Output is correct
25 Correct 695 ms 51948 KB Output is correct
26 Correct 633 ms 51332 KB Output is correct
27 Correct 658 ms 50960 KB Output is correct
28 Correct 669 ms 51764 KB Output is correct
29 Correct 655 ms 51028 KB Output is correct
30 Correct 667 ms 51184 KB Output is correct
31 Correct 641 ms 51052 KB Output is correct
32 Correct 669 ms 51320 KB Output is correct
33 Incorrect 227 ms 44968 KB Output isn't correct
34 Halted 0 ms 0 KB -