제출 #274229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274229		doowey	Aesthetic (NOI20_aesthetic)	C++14	100 / 100	1014 ms	71476 KiB

Aesthetic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
int u[N], v[N], w[N];
int p[N];

vector<pii> T[N];
ll dist[2][N];
bool has[N];
int n,m,c;

void dijik(int x){
    priority_queue<pii,vector<pii>,greater<pii>> gg;
    int node;
    for(int i = 1; i <= n; i ++ ){
        dist[c][i]=(ll)1e14;
        has[i]=false;
    }
    dist[c][x]=0ll;
    gg.push(mp(0,x));
    while(!gg.empty()){
        node = gg.top().se;
        gg.pop();
        if(has[node]) continue;
        has[node]=true;
        for(auto x : T[node]){
            if(dist[c][node] + w[x.se] < dist[c][x.fi]){
                dist[c][x.fi] = dist[c][node] + w[x.se];
                gg.push(mp(dist[c][x.fi], x.fi));
            }
        }
    }
    c++;
}

vector<pii> E[N];

int tin[N];
int low[N];

ll attm;
int tt;

bool bridge[N];

void dfs(int u, int par){
    tin[u] = ++tt;
    low[u] = tin[u];
    for(auto x : E[u]){
        if(x.fi == par) continue;
        if(tin[x.fi] != -1){
            low[u] = min(low[u], tin[x.fi]);
        }
        else{
            dfs(x.fi, u);
            low[u] = min(low[u], low[x.fi]);
            if(tin[u] < low[x.fi]){
                bridge[x.se] = true;
            }
        }
    }
}

int ids[N];
int id;

void dfs1(int u, int par){
    ids[u]=id;
    for(auto x : E[u]){
        if(ids[x.fi] != -1) continue;
        if(bridge[x.se]) continue;
        dfs1(x.fi, u);
    }
}

bool bad;

int pid[N];
int ip[N];

bool vis[N];

void dfs2(int u, int par){
    vis[u]=true;
    for(auto x : E[u]){
        if(vis[x.fi]) continue;
        if(bridge[x.se]){
            pid[ids[x.fi]] = ids[u];
            ip[ids[x.fi]] = x.se;
            dfs2(x.fi, u);
        }
        else{
            dfs2(x.fi, u);
        }
    }
}

bool check(ll dis){
    attm = dis;
    tt = 0;
    for(int i = 0 ; i < m ; i ++ ){
        bridge[i]=false;
    }
    for(int i = 1; i <= n; i ++ ){
        E[i].clear();
        vis[i]=false;
        tin[i] = -1, low[i] = -1;
        ids[i] = -1;
        pid[i] = -1;
        ip[i] = -1;
    }
    id = 0;
    for(int i = 0 ; i < m ; i ++ ){
        if(dist[0][u[i]] + w[i] + dist[1][v[i]] <= dis || dist[0][v[i]] + w[i] + dist[1][u[i]] <= dis){
            E[u[i]].push_back(mp(v[i], i));
            E[v[i]].push_back(mp(u[i], i));
        }
    }
    dfs(1, 0);
    if(tin[n] == -1) return false; // we assume it is reachable at this point
    bad = false;
    for(int i = 1; i <= n; i ++ ){
        if(tin[i] != -1 && ids[i] == -1){
            id ++ ;
            dfs1(i,-1);
        }
    }
    dfs2(1, 0);
    int node = ids[n];
    int ed;
    while(node != ids[1]){
        ed = ip[node];
        node = pid[node];
        if(dist[0][u[ed]] + dist[1][v[ed]] + w[ed] + p[ed+1] > dis && dist[1][u[ed]] + dist[0][v[ed]] + w[ed] + p[ed+1] > dis)
            return false;
    }
    return true;
}

int main(){
    fastIO;
    cin >> n >> m;
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u[i] >> v[i] >> w[i];
        T[u[i]].push_back(mp(v[i],i));
        T[v[i]].push_back(mp(u[i],i));
    }
    dijik(1);
    dijik(n);
    for(int i = m-1; i >= 0 ; i -- ){
        p[i]=w[i];
        p[i]=max(p[i],p[i+1]);
    }
    ll li = dist[0][n], ri = li+p[1];
    ll mid;
    while(li < ri){
        mid = (li + ri) / 2;
        if(check(mid))
            ri = mid;
        else
            li = mid + 1;
    }
    cout << li << "\n";
    return 0;
}

• 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