oj.uz

Submission #834370

# Submission time Handle Problem Language Result Execution time Memory
834370 2023-08-22T13:44:06 Z _martynas Aesthetic (NOI20_aesthetic) C++11
22 / 100
 2000 ms 56136 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#warning change mxn
const int mxn = 3e5+5;
const ll inf = 1e16;

struct Edge {
    int to, id;
};

int n, m;
int A[mxn], B[mxn];
vector<Edge> adj[mxn];
ll W[mxn];
vector<Edge> adj2[mxn];
bool isbridge[mxn], visited[mxn];
vector<ll> from1, fromn;

vector<ll> get_min_dist(int start) {
    vector<long long> dist(n+1, inf);
    priority_queue<pair<ll, int>> pq;
    dist[start] = 0;
    pq.push({-dist[start], start});;
    while(!pq.empty()) {
        ll d = -pq.top().first;
        int a = pq.top().second;
        pq.pop();
        if(dist[a] != d) continue;
        for(auto e : adj[a]) if(dist[e.to] > d+W[e.id]) {
            dist[e.to] = d+W[e.id];
            pq.push({-dist[e.to], e.to});
        }
    }
    return dist;
}


int tim = 0;
int disc[mxn], low[mxn];
void bridge_det(int u, int par) {
    visited[u] = true;
    low[u] = disc[u] = tim++;
    for(auto e : adj2[u]) if(e.to != par) {
        if(!visited[e.to]) {
            bridge_det(e.to, u);
            if(low[e.to] > disc[u]) {
                isbridge[e.id] = true;
            }
        }
        low[u] = min(low[u], low[e.to]);
    }
}

int main(int argc, char const *argv[]) {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> A[i] >> B[i] >> W[i];
        adj[A[i]].push_back({B[i], i});
        adj[B[i]].push_back({A[i], i});
    }
    from1 = get_min_dist(1);
    fromn = get_min_dist(n);
    ll mxw = W[m];
    vector<ll> ans(m+1);
    for(int i = m-1; i >= 1; i--) {
        ll nw = W[i]+mxw;
        ll mndist = inf;
        mndist = min(mndist, from1[A[i]]+fromn[B[i]]+nw);
        mndist = min(mndist, from1[B[i]]+fromn[A[i]]+nw);
        ans[i] = mndist;
        mxw = max(mxw, W[i]);
    }
    // build new graph where every path is min
    for(int i = 1; i <= m; i++) {
        if(from1[A[i]]+fromn[B[i]]+W[i] == from1[n] || from1[B[i]]+fromn[A[i]]+W[i] == from1[n]) {
            adj2[A[i]].push_back({B[i], i});
            adj2[B[i]].push_back({A[i], i});
        }
    }
    // printf("new graph\n");
    // for(int i = 1; i <= n; i++) {
    //     printf("%d: ", i);
    //     for(auto e : adj2[i]) {
    //         printf("%d (%d), ", e.to, e.id);
    //     }
    //     printf("\n");
    // }
    fill(low, low+n+1, mxn);
    bridge_det(1, -1);
    // printf("bridge: ");
    // for(int i = m; i >= 1; i--) if(isbridge[i]) printf("%d ", i);
    // printf("\n");
    vector<int> cnt_to_id(m+1);
    fill(visited, visited+n+1, false);
    queue<int> q;
    visited[1] = true; q.push(1);
    int c = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto e : adj2[u]) if(!visited[e.to]) {
            visited[e.to] = true;
            c += isbridge[e.id];
            cnt_to_id[c] = e.id;
        }
    }
    vector<long long> dist(n+1, inf);
    vector<int> cnt(n+1);
    priority_queue<pair<pair<ll, int>, int>> pq;
    vector<Edge> used_edge; vector<int> from;
    dist[1] = 0, cnt[1] = 0;
    pq.push({{-dist[1], 1}, -1});
    while(!pq.empty()) {
        ll d = -pq.top().first.first;
        int a = pq.top().first.second;
        int edgeidx = pq.top().second;
        pq.pop();
        if(edgeidx != -1) {
            // cerr << from[edgeidx] << " -> " << a << "\n";
            // cerr << cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id] << "; " << cnt[a] << "\n";
            if(cnt[used_edge[edgeidx].to] > cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id]) {
                for(int i = cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id]+1; i <= cnt[a]; i++) {
                    // cerr << "modify " << cnt_to_id[i] << "\n";
                    ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], from1[from[edgeidx]]+W[used_edge[edgeidx].id]+fromn[a]);
                }
            }
        }
        if(dist[a] != d) continue;
        // cerr << a << " " << d << "\n";
        for(auto e : adj[a]) {
            if(dist[e.to] > d+W[e.id]) {
                cnt[e.to] = cnt[a]+isbridge[e.id];
                dist[e.to] = d+W[e.id];
                pq.push({{-dist[e.to], e.to}, used_edge.size()});
                used_edge.push_back(e); from.push_back(a);
                // cerr << "add " << from.back() << " " << used_edge.back().to << "\n";
            }
            else {
                // cerr << a << " -> " << e.to << "\n";
                // cerr << cnt[a]+isbridge[e.id] << "; " << cnt[e.to] << "\n";
                if(cnt[e.to] > cnt[a]+isbridge[e.id]) {
                    for(int i = cnt[a]+isbridge[e.id]+1; i <= cnt[e.to]; i++)  {
                        // cerr << i << ": " << cnt_to_id[i] << "?\n";
                        ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], from1[a]+W[e.id]+fromn[e.to]);
                    }
                }
            }
        }
    }
    ll answer = 0;
    for(int i = 1; i < m; i++) {
        // cerr << ans[i] << " ";
        answer = max(answer, isbridge[i] ? ans[i] : from1[n]);
    }
    // cerr << "\n";
    cout << answer << "\n";
    return 0;
}

Compilation message

Aesthetic.cpp:7:2: warning: #warning change mxn [-Wcpp]
    7 | #warning change mxn
      |  ^~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 50632 KB Output is correct
2 Correct 597 ms 50636 KB Output is correct
3 Correct 553 ms 50492 KB Output is correct
4 Correct 599 ms 50480 KB Output is correct
5 Correct 555 ms 50688 KB Output is correct
6 Correct 592 ms 51240 KB Output is correct
7 Correct 622 ms 50972 KB Output is correct
8 Correct 630 ms 51324 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 51388 KB Output is correct
2 Correct 575 ms 54932 KB Output is correct
3 Correct 595 ms 54404 KB Output is correct
4 Correct 641 ms 54428 KB Output is correct
5 Correct 575 ms 54756 KB Output is correct
6 Correct 577 ms 54708 KB Output is correct
7 Correct 649 ms 54812 KB Output is correct
8 Correct 567 ms 55056 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 44508 KB Output is correct
2 Correct 284 ms 49480 KB Output is correct
3 Correct 342 ms 55324 KB Output is correct
4 Correct 425 ms 55324 KB Output is correct
5 Correct 361 ms 55312 KB Output is correct
6 Correct 346 ms 55332 KB Output is correct
7 Correct 357 ms 55452 KB Output is correct
8 Correct 302 ms 55492 KB Output is correct
9 Correct 350 ms 55488 KB Output is correct
10 Correct 347 ms 55744 KB Output is correct
11 Correct 333 ms 55656 KB Output is correct
12 Correct 514 ms 48800 KB Output is correct
13 Correct 355 ms 55488 KB Output is correct
14 Execution timed out 2073 ms 56136 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 44508 KB Output is correct
2 Correct 284 ms 49480 KB Output is correct
3 Correct 342 ms 55324 KB Output is correct
4 Correct 425 ms 55324 KB Output is correct
5 Correct 361 ms 55312 KB Output is correct
6 Correct 346 ms 55332 KB Output is correct
7 Correct 357 ms 55452 KB Output is correct
8 Correct 302 ms 55492 KB Output is correct
9 Correct 350 ms 55488 KB Output is correct
10 Correct 347 ms 55744 KB Output is correct
11 Correct 333 ms 55656 KB Output is correct
12 Correct 514 ms 48800 KB Output is correct
13 Correct 355 ms 55488 KB Output is correct
14 Execution timed out 2073 ms 56136 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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