Submission #293317

#	Time	Username	Problem	Language	Result	Execution time	Memory
293317		crossing0ver	Aesthetic (NOI20_aesthetic)	C++17	100 / 100	907 ms	297508 KiB

Aesthetic

#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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27