oj.uz

Submission #293230

# Submission time Handle Problem Language Result Execution time Memory
293230 2020-09-07T19:19:23 Z crossing0ver Aesthetic (NOI20_aesthetic) C++17
13 / 100
 346 ms 5248 KB 
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define vi vector<int>
#define se second
#define fi first
using namespace std;
const int N = 1e5+5;
vector<pii> adj[N];
int n,m;
int A[N],B[N],W[N],NUM[N][2],MX[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
            int a,b,w;
        cin >> a >> b >> w;
        A[i] = a, B[i] = b;
        W[i] = w;
        NUM[i][0] = adj[a].size();
        NUM[i][1] = adj[b].size();
        adj[a].pb({b,w});
        adj[b].pb({a,w});
        MX[i] = w;
    }
    for (int i = m-2; i >= 0; i--)
        MX[i] = max(MX[i],MX[i+1]);
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        int a = A[i], b = B[i];
        adj[a][NUM[i][0]].se += MX[i+1];
        adj[b][NUM[i][1]].se += MX[i+1];
        // dijkstra

        priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
        pq.push({0,1});
        vector<bool> vis(n+1);
        vector<ll> d(n+1);
        d[0] = 0;
        for (int i = 1; i <= n; i++)
            d[i] = 10000000000000000;
        while(!pq.empty()) {
            auto i1 = pq.top();
            pq.pop();
            int v = i1.se;
            if (vis[v]) continue;
            ll dis = i1.fi;
            if (v == n) {
                ans = max(ans,dis);
                break;
            }
            vis[v] = 1;
            for (auto i : adj[v])
                if (!vis[i.fi] && d[i.fi] > dis + i.se) {
                    d[i.fi] = dis + i.se;
                    pq.push({d[i.fi],i.fi});
                }

        }
        // replace
        adj[a][NUM[i][0]].se -= MX[i+1];
        adj[b][NUM[i][1]].se -= MX[i+1];
    }
    cout << ans;



}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 346 ms 2948 KB Output is correct
10 Correct 335 ms 2948 KB Output is correct
11 Correct 267 ms 2936 KB Output is correct
12 Correct 270 ms 2816 KB Output is correct
13 Correct 164 ms 2936 KB Output is correct
14 Correct 171 ms 2924 KB Output is correct
15 Correct 169 ms 2816 KB Output is correct
16 Correct 167 ms 2936 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 346 ms 2948 KB Output is correct
10 Correct 335 ms 2948 KB Output is correct
11 Correct 267 ms 2936 KB Output is correct
12 Correct 270 ms 2816 KB Output is correct
13 Correct 164 ms 2936 KB Output is correct
14 Correct 171 ms 2924 KB Output is correct
15 Correct 169 ms 2816 KB Output is correct
16 Correct 167 ms 2936 KB Output is correct
17 Runtime error 6 ms 5248 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -