oj.uz

Submission #834458

# Submission time Handle Problem Language Result Execution time Memory
834458 2023-08-22T14:34:56 Z _martynas Aesthetic (NOI20_aesthetic) C++11
38 / 100
 742 ms 77244 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];
bool onpathton[mxn];
void bridge_det(int u, int par) {
    visited[u] = true;
    if(u == n) onpathton[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] && onpathton[e.to]) {
                isbridge[e.id] = true;
            }
        }
        onpathton[u] = onpathton[u] || onpathton[e.to];
        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});
    vector<vector<ll>> ins(m+1), del(m+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]) {
                int l = cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id]+1, r = cnt[a];
                ll val = from1[from[edgeidx]]+W[used_edge[edgeidx].id]+fromn[a];
                // for(int i = l; i <= r; i++) {
                //     // cerr << "modify " << cnt_to_id[i] << "\n";
                //     ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], val);
                // }
                ins[l].push_back(val);
                del[r].push_back(val);
            }
        }
        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]) {
                    int l = cnt[a]+isbridge[e.id]+1, r = cnt[e.to];
                    ll val = from1[a]+W[e.id]+fromn[e.to];
                    // for(int i = l; i <= r; i++)  {
                    //     // cerr << i << ": " << cnt_to_id[i] << "?\n";
                    //     ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], val);
                    // }
                    ins[l].push_back(val);
                    del[r].push_back(val);
                }
            }
        }
    }
    multiset<ll> available;
    for(int i = 0; i < m; i++) {
        for(ll x : ins[i]) available.insert(x);
        if(cnt_to_id[i] != 0 && !available.empty()) {
            // cerr << cnt_to_id[i] << " <- " << (*available.begin()) << "\n";
            ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], *available.begin());
        }
        for(ll x : del[i]) available.erase(available.find(x));
    }
    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 14420 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 14420 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 637 ms 64804 KB Output is correct
2 Correct 609 ms 64704 KB Output is correct
3 Correct 626 ms 64380 KB Output is correct
4 Correct 615 ms 64496 KB Output is correct
5 Correct 636 ms 64660 KB Output is correct
6 Correct 627 ms 65752 KB Output is correct
7 Correct 614 ms 65248 KB Output is correct
8 Correct 652 ms 65732 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 65652 KB Output is correct
2 Correct 630 ms 64992 KB Output is correct
3 Correct 607 ms 64436 KB Output is correct
4 Correct 618 ms 64636 KB Output is correct
5 Correct 614 ms 64672 KB Output is correct
6 Correct 606 ms 64804 KB Output is correct
7 Correct 667 ms 64832 KB Output is correct
8 Correct 742 ms 65204 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 58384 KB Output is correct
2 Correct 310 ms 59744 KB Output is correct
3 Correct 339 ms 66624 KB Output is correct
4 Correct 395 ms 66692 KB Output is correct
5 Correct 352 ms 66656 KB Output is correct
6 Correct 362 ms 66688 KB Output is correct
7 Correct 355 ms 66692 KB Output is correct
8 Correct 362 ms 66984 KB Output is correct
9 Correct 356 ms 66648 KB Output is correct
10 Correct 376 ms 67164 KB Output is correct
11 Correct 350 ms 66880 KB Output is correct
12 Correct 531 ms 60368 KB Output is correct
13 Correct 359 ms 66936 KB Output is correct
14 Correct 266 ms 77244 KB Output is correct
15 Correct 262 ms 74956 KB Output is correct
16 Correct 483 ms 58600 KB Output is correct
17 Correct 467 ms 59432 KB Output is correct
18 Correct 470 ms 58132 KB Output is correct
19 Correct 347 ms 59988 KB Output is correct
20 Correct 312 ms 59872 KB Output is correct
21 Correct 308 ms 59852 KB Output is correct
22 Correct 309 ms 59840 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 58384 KB Output is correct
2 Correct 310 ms 59744 KB Output is correct
3 Correct 339 ms 66624 KB Output is correct
4 Correct 395 ms 66692 KB Output is correct
5 Correct 352 ms 66656 KB Output is correct
6 Correct 362 ms 66688 KB Output is correct
7 Correct 355 ms 66692 KB Output is correct
8 Correct 362 ms 66984 KB Output is correct
9 Correct 356 ms 66648 KB Output is correct
10 Correct 376 ms 67164 KB Output is correct
11 Correct 350 ms 66880 KB Output is correct
12 Correct 531 ms 60368 KB Output is correct
13 Correct 359 ms 66936 KB Output is correct
14 Correct 266 ms 77244 KB Output is correct
15 Correct 262 ms 74956 KB Output is correct
16 Correct 483 ms 58600 KB Output is correct
17 Correct 467 ms 59432 KB Output is correct
18 Correct 470 ms 58132 KB Output is correct
19 Correct 347 ms 59988 KB Output is correct
20 Correct 312 ms 59872 KB Output is correct
21 Correct 308 ms 59852 KB Output is correct
22 Correct 309 ms 59840 KB Output is correct
23 Correct 569 ms 62264 KB Output is correct
24 Correct 353 ms 62260 KB Output is correct
25 Correct 292 ms 50776 KB Output is correct
26 Incorrect 339 ms 54268 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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