oj.uz

Submission #293317

# Submission time Handle Problem Language Result Execution time Memory
293317 2020-09-07T21:28:12 Z crossing0ver Aesthetic (NOI20_aesthetic) C++17
100 / 100
 907 ms 297508 KB 
#include<bits/stdc++.h>
#define int long long
#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 = 4e6+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;
    }
  //  if ()
    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 dfs(int v) {
    for (auto i : adj[v])
    {
        if (!good[i.fi]) {
            sub[i.fi] = sub[v];
            dfs(i.fi);
        }
    }
}
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 = 1; i <= n; i++)
                    if (!good[i]) id[i] = 0;
            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;
            //j = n;
           // int cur = n -1;
           // while (j)
           //     sub[v]
           for (int i = 1; i <= n; i++)
                adj[i].clear();
            for (int i = 2; i <= n; i++)
                adj[par[i]].pb({i,0});
            for (int i = 1; i <= n; i++)
            if (good[i]) {
                sub[i] = i;
                dfs(i);
            }
           /* 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;
        }
        }*/

        }
}
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 = 0; i < 4*N; i++)
        t[i] = 10000000000000000;
   // cout << FROM_N[1];exit(0);
    for (int i = m+1; 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})) {
            if (id[a] > id[b]) swap(a,b);
            q.pb({D[n] + MX[i+1],{id[a],id[a]}});
        }
    }
    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, H[id[a]]);
       // 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;
}

Compilation message

Aesthetic.cpp:128:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main() {
      |      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 219640 KB Output is correct
2 Correct 140 ms 219644 KB Output is correct
3 Correct 141 ms 219584 KB Output is correct
4 Correct 135 ms 219640 KB Output is correct
5 Correct 148 ms 219640 KB Output is correct
6 Correct 142 ms 219620 KB Output is correct
7 Correct 135 ms 219640 KB Output is correct
8 Correct 136 ms 219640 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 219640 KB Output is correct
2 Correct 140 ms 219644 KB Output is correct
3 Correct 141 ms 219584 KB Output is correct
4 Correct 135 ms 219640 KB Output is correct
5 Correct 148 ms 219640 KB Output is correct
6 Correct 142 ms 219620 KB Output is correct
7 Correct 135 ms 219640 KB Output is correct
8 Correct 136 ms 219640 KB Output is correct
9 Correct 137 ms 219896 KB Output is correct
10 Correct 139 ms 219896 KB Output is correct
11 Correct 140 ms 219896 KB Output is correct
12 Correct 137 ms 219896 KB Output is correct
13 Correct 135 ms 219896 KB Output is correct
14 Correct 150 ms 219900 KB Output is correct
15 Correct 135 ms 219896 KB Output is correct
16 Correct 133 ms 219896 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 267100 KB Output is correct
2 Correct 811 ms 266988 KB Output is correct
3 Correct 843 ms 267020 KB Output is correct
4 Correct 875 ms 267016 KB Output is correct
5 Correct 857 ms 267396 KB Output is correct
6 Correct 854 ms 268236 KB Output is correct
7 Correct 848 ms 267612 KB Output is correct
8 Correct 862 ms 268160 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 268340 KB Output is correct
2 Correct 907 ms 267748 KB Output is correct
3 Correct 804 ms 266364 KB Output is correct
4 Correct 785 ms 266600 KB Output is correct
5 Correct 845 ms 267256 KB Output is correct
6 Correct 796 ms 266992 KB Output is correct
7 Correct 835 ms 267244 KB Output is correct
8 Correct 875 ms 267748 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 260600 KB Output is correct
2 Correct 392 ms 264704 KB Output is correct
3 Correct 443 ms 256604 KB Output is correct
4 Correct 450 ms 257756 KB Output is correct
5 Correct 464 ms 258712 KB Output is correct
6 Correct 450 ms 257728 KB Output is correct
7 Correct 440 ms 256476 KB Output is correct
8 Correct 451 ms 257628 KB Output is correct
9 Correct 439 ms 256908 KB Output is correct
10 Correct 442 ms 256992 KB Output is correct
11 Correct 452 ms 257796 KB Output is correct
12 Correct 669 ms 264224 KB Output is correct
13 Correct 456 ms 256736 KB Output is correct
14 Correct 497 ms 285624 KB Output is correct
15 Correct 476 ms 285644 KB Output is correct
16 Correct 650 ms 261148 KB Output is correct
17 Correct 642 ms 261616 KB Output is correct
18 Correct 650 ms 259988 KB Output is correct
19 Correct 404 ms 264692 KB Output is correct
20 Correct 389 ms 265072 KB Output is correct
21 Correct 392 ms 264780 KB Output is correct
22 Correct 383 ms 264824 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 260600 KB Output is correct
2 Correct 392 ms 264704 KB Output is correct
3 Correct 443 ms 256604 KB Output is correct
4 Correct 450 ms 257756 KB Output is correct
5 Correct 464 ms 258712 KB Output is correct
6 Correct 450 ms 257728 KB Output is correct
7 Correct 440 ms 256476 KB Output is correct
8 Correct 451 ms 257628 KB Output is correct
9 Correct 439 ms 256908 KB Output is correct
10 Correct 442 ms 256992 KB Output is correct
11 Correct 452 ms 257796 KB Output is correct
12 Correct 669 ms 264224 KB Output is correct
13 Correct 456 ms 256736 KB Output is correct
14 Correct 497 ms 285624 KB Output is correct
15 Correct 476 ms 285644 KB Output is correct
16 Correct 650 ms 261148 KB Output is correct
17 Correct 642 ms 261616 KB Output is correct
18 Correct 650 ms 259988 KB Output is correct
19 Correct 404 ms 264692 KB Output is correct
20 Correct 389 ms 265072 KB Output is correct
21 Correct 392 ms 264780 KB Output is correct
22 Correct 383 ms 264824 KB Output is correct
23 Correct 723 ms 264768 KB Output is correct
24 Correct 430 ms 267524 KB Output is correct
25 Correct 488 ms 260584 KB Output is correct
26 Correct 479 ms 260576 KB Output is correct
27 Correct 465 ms 260576 KB Output is correct
28 Correct 471 ms 260736 KB Output is correct
29 Correct 479 ms 263892 KB Output is correct
30 Correct 461 ms 260552 KB Output is correct
31 Correct 469 ms 261084 KB Output is correct
32 Correct 469 ms 260616 KB Output is correct
33 Correct 489 ms 261076 KB Output is correct
34 Correct 683 ms 266572 KB Output is correct
35 Correct 489 ms 264152 KB Output is correct
36 Correct 548 ms 296228 KB Output is correct
37 Correct 655 ms 296996 KB Output is correct
38 Correct 686 ms 264872 KB Output is correct
39 Correct 685 ms 266316 KB Output is correct
40 Correct 702 ms 267024 KB Output is correct
41 Correct 418 ms 267632 KB Output is correct
42 Correct 415 ms 267384 KB Output is correct
43 Correct 418 ms 267408 KB Output is correct
44 Correct 418 ms 267492 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 219640 KB Output is correct
2 Correct 140 ms 219644 KB Output is correct
3 Correct 141 ms 219584 KB Output is correct
4 Correct 135 ms 219640 KB Output is correct
5 Correct 148 ms 219640 KB Output is correct
6 Correct 142 ms 219620 KB Output is correct
7 Correct 135 ms 219640 KB Output is correct
8 Correct 136 ms 219640 KB Output is correct
9 Correct 137 ms 219896 KB Output is correct
10 Correct 139 ms 219896 KB Output is correct
11 Correct 140 ms 219896 KB Output is correct
12 Correct 137 ms 219896 KB Output is correct
13 Correct 135 ms 219896 KB Output is correct
14 Correct 150 ms 219900 KB Output is correct
15 Correct 135 ms 219896 KB Output is correct
16 Correct 133 ms 219896 KB Output is correct
17 Correct 807 ms 267100 KB Output is correct
18 Correct 811 ms 266988 KB Output is correct
19 Correct 843 ms 267020 KB Output is correct
20 Correct 875 ms 267016 KB Output is correct
21 Correct 857 ms 267396 KB Output is correct
22 Correct 854 ms 268236 KB Output is correct
23 Correct 848 ms 267612 KB Output is correct
24 Correct 862 ms 268160 KB Output is correct
25 Correct 905 ms 268340 KB Output is correct
26 Correct 907 ms 267748 KB Output is correct
27 Correct 804 ms 266364 KB Output is correct
28 Correct 785 ms 266600 KB Output is correct
29 Correct 845 ms 267256 KB Output is correct
30 Correct 796 ms 266992 KB Output is correct
31 Correct 835 ms 267244 KB Output is correct
32 Correct 875 ms 267748 KB Output is correct
33 Correct 675 ms 260600 KB Output is correct
34 Correct 392 ms 264704 KB Output is correct
35 Correct 443 ms 256604 KB Output is correct
36 Correct 450 ms 257756 KB Output is correct
37 Correct 464 ms 258712 KB Output is correct
38 Correct 450 ms 257728 KB Output is correct
39 Correct 440 ms 256476 KB Output is correct
40 Correct 451 ms 257628 KB Output is correct
41 Correct 439 ms 256908 KB Output is correct
42 Correct 442 ms 256992 KB Output is correct
43 Correct 452 ms 257796 KB Output is correct
44 Correct 669 ms 264224 KB Output is correct
45 Correct 456 ms 256736 KB Output is correct
46 Correct 497 ms 285624 KB Output is correct
47 Correct 476 ms 285644 KB Output is correct
48 Correct 650 ms 261148 KB Output is correct
49 Correct 642 ms 261616 KB Output is correct
50 Correct 650 ms 259988 KB Output is correct
51 Correct 404 ms 264692 KB Output is correct
52 Correct 389 ms 265072 KB Output is correct
53 Correct 392 ms 264780 KB Output is correct
54 Correct 383 ms 264824 KB Output is correct
55 Correct 723 ms 264768 KB Output is correct
56 Correct 430 ms 267524 KB Output is correct
57 Correct 488 ms 260584 KB Output is correct
58 Correct 479 ms 260576 KB Output is correct
59 Correct 465 ms 260576 KB Output is correct
60 Correct 471 ms 260736 KB Output is correct
61 Correct 479 ms 263892 KB Output is correct
62 Correct 461 ms 260552 KB Output is correct
63 Correct 469 ms 261084 KB Output is correct
64 Correct 469 ms 260616 KB Output is correct
65 Correct 489 ms 261076 KB Output is correct
66 Correct 683 ms 266572 KB Output is correct
67 Correct 489 ms 264152 KB Output is correct
68 Correct 548 ms 296228 KB Output is correct
69 Correct 655 ms 296996 KB Output is correct
70 Correct 686 ms 264872 KB Output is correct
71 Correct 685 ms 266316 KB Output is correct
72 Correct 702 ms 267024 KB Output is correct
73 Correct 418 ms 267632 KB Output is correct
74 Correct 415 ms 267384 KB Output is correct
75 Correct 418 ms 267408 KB Output is correct
76 Correct 418 ms 267492 KB Output is correct
77 Correct 725 ms 267900 KB Output is correct
78 Correct 428 ms 269824 KB Output is correct
79 Correct 488 ms 263136 KB Output is correct
80 Correct 482 ms 266196 KB Output is correct
81 Correct 472 ms 263000 KB Output is correct
82 Correct 477 ms 262748 KB Output is correct
83 Correct 488 ms 266328 KB Output is correct
84 Correct 486 ms 263400 KB Output is correct
85 Correct 480 ms 262920 KB Output is correct
86 Correct 489 ms 263264 KB Output is correct
87 Correct 473 ms 263260 KB Output is correct
88 Correct 712 ms 267344 KB Output is correct
89 Correct 486 ms 263520 KB Output is correct
90 Correct 572 ms 296740 KB Output is correct
91 Correct 615 ms 297508 KB Output is correct
92 Correct 736 ms 269716 KB Output is correct
93 Correct 705 ms 266580 KB Output is correct
94 Correct 676 ms 265916 KB Output is correct
95 Correct 426 ms 269732 KB Output is correct
96 Correct 424 ms 269856 KB Output is correct
97 Correct 427 ms 269940 KB Output is correct
98 Correct 430 ms 269688 KB Output is correct