oj.uz

Submission #293296

# Submission time Handle Problem Language Result Execution time Memory
293296 2020-09-07T20:44:10 Z crossing0ver Aesthetic (NOI20_aesthetic) C++17
51 / 100
 595 ms 54008 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 = 3e5+5;
vector<pii> adj[N];
int n,m;
int A[N],B[N],W[N],NUM[N][2],MX[N],par[N],good[N],sub[N],id[N];
ll D[N],FROM_N[N],H[N];
set<pii> path;

ll t[4*N];
void upd(int v,int tl,int tr,int l,int r,ll val) {
    if(l > tr || r < tl) return;
    if (l <= tl && r >= tr)  {
            t[v] = val;
            return;
    }
    t[v*2] = min(t[v*2],t[v]);
    t[v*2+1] = min(t[v*2+1],t[v]);
    int tm = (tl + tr)/2;
    upd(v*2,tl,tm,l,r,val);
    upd(v*2+1,tm+1,tr,l,r,val);
    //t[v] = min(t[v*2],t[v*2+1]);
}
void down(int v,int tl,int tr) {
    if (tl == tr) H[tl] = t[v];
    else {
            int tm = (tl + tr)/2;
            t[v*2] = min(t[v*2],t[v]);
        t[v*2+1] = min(t[v*2+1],t[v]);
        down(v*2,tl,tm);
        down(v*2+1,tm+1,tr);
    }
}
void dijkstra(int s) {
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
        pq.push({0,s});
        vector<bool> vis(n+1);
        vector<ll> d(n+1);
        for (int i = 1; i <= n; i++)
            d[i] = 10000000000000000;
        d[s] = 0;
        par[s] = 0;
        id[s] = 0;
        while(!pq.empty()) {
            auto i1 = pq.top();
            pq.pop();
            int v = i1.se;
            if (vis[v]) continue;
            ll dis = i1.fi;
            vis[v] = 1;
            for (auto i : adj[v])
                if (!vis[i.fi] && d[i.fi] > dis + i.se) {
                    d[i.fi] = dis + i.se;
                    id[i.fi] = id[v] + 1;
                    par[i.fi] = v;
                    pq.push({d[i.fi],i.fi});
                }
        }/*1 2 3
2 3 5
1 3 4*/
        if (s == n)
        for (int i = 1; i <= n; i++)
            FROM_N[i] = d[i];
        else {
                for (int i = 1; i <= n; i++)
                    D[i] = d[i];
               int j = n;
                good[1] = 1;
            while(j != 1) {
                good[j] = 1;
                j = par[j];
            }
            for (int i = 2; i <= n; i++) {
                        if (good[i])
                    path.insert({i,par[i]}),
                    path.insert({par[i],i});
                }
            vector<pair<ll,int> > g;
            for (int i =1 ; i <= n; i++) {
                g.pb({d[i],i});
            }
        sort(all(g));
        for (auto i1 : g) {
            int v = i1.se;
            if (!good[v])
                sub[v] = sub [ par[v] ];
            else sub[v] = v;
        }
        }
}
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;
    }
    dijkstra(n);
    dijkstra(1);
    for (int i = 1; i < 4*N; i++)
        t[i] = 10000000000000000;
   // cout << FROM_N[1];exit(0);
    for (int i = m-2; i >= 0; i--)
        MX[i] = max(MX[i],MX[i+1]);
    ll ans = D[n];
   // cout << D[n];exit(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);
        for (int i = 1; i <= n; i++)
            d[i] = 10000000000000000;
        d[1] = 0;
        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];
    }*/
    vector<pair<ll,pii> > q;
    for (int i = 0; i < m; i++) {
        int a = A[i], b = B[i];
        if (path.count({a,b}) || sub[a] == sub[b]) continue;
        if (id[sub[a]] > id[sub[b]]) swap(a,b);
        ll dis = D[a] + FROM_N[b] + W[i];
        a = sub[a];
        b = sub[b];
        if (id[a] > id[b]) swap(a,b);
      //  if (id[sub])
      q.pb({dis,{id[a],id[b]-1}});
     //   upd(1,0,id[n],id[a],id[b]-1,dis);
    }
    sort(q.rbegin(),q.rend());
    for (auto i1 : q) {
        int a = i1.se.fi;
        int b = i1.se.se;
        ll val = i1.fi;
        upd(1,0,id[n],a,b,val);
    }
    down(1,0,id[n]);
    for (int i = 0; i < m; i++) {
        int a = A[i], b = B[i];
        if (path.count({a,b}) == 0) continue;
        if (id[a] > id[b]) swap(a,b);
        if (H[id[a]] !=  10000000000000000)
        ans = max(ans, min(H[id[a]],D[n] + MX[i+1]));
        else ans = max(ans,D[n] + MX[i+1]);
      /*  ll C = D[n];
        C += MX[i+1];
        //adj[a][NUM[i][0]].se += MX[i+1];
        //adj[b][NUM[i][1]].se += MX[i+1];
        // dijkstra
        for (int i = 0; i < m; i++) {
            int x = A[i], y = B[i];
            if (id[sub[x]] > id[sub[y]]) swap(x,y);

            if (x == a && y == b ) continue;
            if (id[sub[x]] > id[a] || id[sub[y]] < id[b]) continue;
            C = min(C,D[x] + FROM_N[y] + W[i]);
        }
        ans = max(ans,C);

*/
        }
        // 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 11 ms 16896 KB Output is correct
2 Correct 11 ms 16896 KB Output is correct
3 Correct 11 ms 16896 KB Output is correct
4 Correct 11 ms 16896 KB Output is correct
5 Correct 11 ms 16896 KB Output is correct
6 Correct 11 ms 16896 KB Output is correct
7 Correct 11 ms 16896 KB Output is correct
8 Correct 11 ms 16896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16896 KB Output is correct
2 Correct 11 ms 16896 KB Output is correct
3 Correct 11 ms 16896 KB Output is correct
4 Correct 11 ms 16896 KB Output is correct
5 Correct 11 ms 16896 KB Output is correct
6 Correct 11 ms 16896 KB Output is correct
7 Correct 11 ms 16896 KB Output is correct
8 Correct 11 ms 16896 KB Output is correct
9 Correct 12 ms 17152 KB Output is correct
10 Correct 12 ms 17152 KB Output is correct
11 Correct 12 ms 17024 KB Output is correct
12 Correct 12 ms 17024 KB Output is correct
13 Correct 15 ms 17024 KB Output is correct
14 Correct 12 ms 17024 KB Output is correct
15 Correct 12 ms 17024 KB Output is correct
16 Correct 12 ms 17024 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 50552 KB Output is correct
2 Correct 571 ms 50652 KB Output is correct
3 Correct 574 ms 50400 KB Output is correct
4 Correct 565 ms 50632 KB Output is correct
5 Correct 569 ms 50712 KB Output is correct
6 Correct 584 ms 51184 KB Output is correct
7 Correct 576 ms 50988 KB Output is correct
8 Correct 581 ms 51284 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 51380 KB Output is correct
2 Correct 575 ms 50804 KB Output is correct
3 Correct 563 ms 50040 KB Output is correct
4 Correct 558 ms 50304 KB Output is correct
5 Correct 577 ms 50576 KB Output is correct
6 Correct 559 ms 50688 KB Output is correct
7 Correct 570 ms 50688 KB Output is correct
8 Correct 586 ms 51076 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 44388 KB Output is correct
2 Correct 250 ms 45232 KB Output is correct
3 Correct 268 ms 37576 KB Output is correct
4 Correct 266 ms 37616 KB Output is correct
5 Correct 275 ms 39352 KB Output is correct
6 Correct 274 ms 37960 KB Output is correct
7 Correct 274 ms 37628 KB Output is correct
8 Correct 270 ms 37688 KB Output is correct
9 Correct 265 ms 37576 KB Output is correct
10 Correct 272 ms 37696 KB Output is correct
11 Correct 274 ms 37704 KB Output is correct
12 Correct 452 ms 44604 KB Output is correct
13 Correct 263 ms 37688 KB Output is correct
14 Correct 275 ms 54008 KB Output is correct
15 Correct 291 ms 53944 KB Output is correct
16 Correct 456 ms 44204 KB Output is correct
17 Correct 428 ms 43472 KB Output is correct
18 Correct 432 ms 43988 KB Output is correct
19 Correct 251 ms 45316 KB Output is correct
20 Correct 249 ms 45180 KB Output is correct
21 Correct 257 ms 45184 KB Output is correct
22 Correct 254 ms 45208 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 44388 KB Output is correct
2 Correct 250 ms 45232 KB Output is correct
3 Correct 268 ms 37576 KB Output is correct
4 Correct 266 ms 37616 KB Output is correct
5 Correct 275 ms 39352 KB Output is correct
6 Correct 274 ms 37960 KB Output is correct
7 Correct 274 ms 37628 KB Output is correct
8 Correct 270 ms 37688 KB Output is correct
9 Correct 265 ms 37576 KB Output is correct
10 Correct 272 ms 37696 KB Output is correct
11 Correct 274 ms 37704 KB Output is correct
12 Correct 452 ms 44604 KB Output is correct
13 Correct 263 ms 37688 KB Output is correct
14 Correct 275 ms 54008 KB Output is correct
15 Correct 291 ms 53944 KB Output is correct
16 Correct 456 ms 44204 KB Output is correct
17 Correct 428 ms 43472 KB Output is correct
18 Correct 432 ms 43988 KB Output is correct
19 Correct 251 ms 45316 KB Output is correct
20 Correct 249 ms 45180 KB Output is correct
21 Correct 257 ms 45184 KB Output is correct
22 Correct 254 ms 45208 KB Output is correct
23 Incorrect 502 ms 46616 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16896 KB Output is correct
2 Correct 11 ms 16896 KB Output is correct
3 Correct 11 ms 16896 KB Output is correct
4 Correct 11 ms 16896 KB Output is correct
5 Correct 11 ms 16896 KB Output is correct
6 Correct 11 ms 16896 KB Output is correct
7 Correct 11 ms 16896 KB Output is correct
8 Correct 11 ms 16896 KB Output is correct
9 Correct 12 ms 17152 KB Output is correct
10 Correct 12 ms 17152 KB Output is correct
11 Correct 12 ms 17024 KB Output is correct
12 Correct 12 ms 17024 KB Output is correct
13 Correct 15 ms 17024 KB Output is correct
14 Correct 12 ms 17024 KB Output is correct
15 Correct 12 ms 17024 KB Output is correct
16 Correct 12 ms 17024 KB Output is correct
17 Correct 595 ms 50552 KB Output is correct
18 Correct 571 ms 50652 KB Output is correct
19 Correct 574 ms 50400 KB Output is correct
20 Correct 565 ms 50632 KB Output is correct
21 Correct 569 ms 50712 KB Output is correct
22 Correct 584 ms 51184 KB Output is correct
23 Correct 576 ms 50988 KB Output is correct
24 Correct 581 ms 51284 KB Output is correct
25 Correct 594 ms 51380 KB Output is correct
26 Correct 575 ms 50804 KB Output is correct
27 Correct 563 ms 50040 KB Output is correct
28 Correct 558 ms 50304 KB Output is correct
29 Correct 577 ms 50576 KB Output is correct
30 Correct 559 ms 50688 KB Output is correct
31 Correct 570 ms 50688 KB Output is correct
32 Correct 586 ms 51076 KB Output is correct
33 Correct 460 ms 44388 KB Output is correct
34 Correct 250 ms 45232 KB Output is correct
35 Correct 268 ms 37576 KB Output is correct
36 Correct 266 ms 37616 KB Output is correct
37 Correct 275 ms 39352 KB Output is correct
38 Correct 274 ms 37960 KB Output is correct
39 Correct 274 ms 37628 KB Output is correct
40 Correct 270 ms 37688 KB Output is correct
41 Correct 265 ms 37576 KB Output is correct
42 Correct 272 ms 37696 KB Output is correct
43 Correct 274 ms 37704 KB Output is correct
44 Correct 452 ms 44604 KB Output is correct
45 Correct 263 ms 37688 KB Output is correct
46 Correct 275 ms 54008 KB Output is correct
47 Correct 291 ms 53944 KB Output is correct
48 Correct 456 ms 44204 KB Output is correct
49 Correct 428 ms 43472 KB Output is correct
50 Correct 432 ms 43988 KB Output is correct
51 Correct 251 ms 45316 KB Output is correct
52 Correct 249 ms 45180 KB Output is correct
53 Correct 257 ms 45184 KB Output is correct
54 Correct 254 ms 45208 KB Output is correct
55 Incorrect 502 ms 46616 KB Output isn't correct
56 Halted 0 ms 0 KB -