Submission #1300215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300215		KhoaDuy	Aesthetic (NOI20_aesthetic)	C++20	35 / 100	2096 ms	37284 KiB

Aesthetic

#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXN=3*1e5;
struct we{
    int u,v,w,wbuff;
};
vector<vector<we>> graph;
vector<long long> dijik(int s){
    int n=graph.size()-1;
    priority_queue<pair<long long,int>> pq;
    vector<long long> dist;
    dist.assign(n+1,-1);
    dist[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        int u=pq.top().second;
        long long d=pq.top().first;
        pq.pop();
        if(d>dist[u]){
            continue;
        }
        for(we &x:graph[u]){
            int v=x.v,w=x.w;
            if(dist[v]==-1||dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    return dist;
}
bool brid[MAXN];
int low[MAXN+1],in[MAXN+1],sum[MAXN+1];
int tim=1;
vector<long long> d1,dn;
int n;
vector<we> edges;
void DFS(int u,int p){
    in[u]=tim;
    low[u]=tim;
    tim++;
    sum[u]=(u==1||u==n);
    for(we &x:graph[u]){
        int v=x.v;
        if(v==p){
            continue;
        }
        if(!in[v]){
            DFS(v,u);
            sum[u]+=sum[v];
            low[u]=min(low[u],low[v]);
            if(low[v]>in[u]&&sum[v]==1){
                brid[x.w]=true;
            }
        }
        else{
            low[u]=min(low[u],in[v]);
        }
    }
}
bool check(long long mid){
    int m=edges.size();
    graph.clear(),graph.resize(n+1);
    for(int i=0;i<m;i++){
        int u=edges[i].u,v=edges[i].v,w=edges[i].w;
        if(d1[u]+dn[v]+w<=mid||d1[v]+dn[u]+w<=mid){
            graph[u].push_back({u,v,i,0});
            graph[v].push_back({v,u,i,0});
        }
    }
    memset(brid,false,sizeof(brid));
    for(int i=1;i<=n;i++){
        in[i]=0;
        low[i]=0;
        sum[i]=0;
    }
    tim=1;
    DFS(1,-1);
    bool flag=false;
    for(int i=0;i+1<m;i++){
        if(brid[i]){
            int u=edges[i].u,v=edges[i].v,w=edges[i].w+edges[i].wbuff;
            if(d1[u]+dn[v]+w>mid&&d1[v]+dn[u]+w>mid){
                flag=true;
                break;
            }
        }
    }
    return flag;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int m;
    cin >> n >> m;
    edges.resize(m);
    graph.resize(n+1);
    int bst=0;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        bst=max(bst,w);
        graph[u].push_back({u,v,w,0});
        graph[v].push_back({v,u,w,0});
        edges[i]={u,v,w,0};
    }
    d1=dijik(1),dn=dijik(n);
    edges[m-1].wbuff=0;
    for(int i=m-2;i>=0;i--){
        edges[i].wbuff=max(edges[i+1].wbuff,edges[i+1].w);
    }
    long long Low=d1[n],high=d1[n]+bst;
    Low--,high++;
    while(high-Low>1){
        long long mid=((high-Low)>>1)+Low;
        if(check(mid)){
            Low=mid;
        }
        else{
            high=mid;
        }
    }
    cout << high;
}

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