Submission #293230

#	Time	Username	Problem	Language	Result	Execution time	Memory
293230		crossing0ver	Aesthetic (NOI20_aesthetic)	C++17	13 / 100	346 ms	5248 KiB

Aesthetic

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27