Submission #1299500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299500		khoal	Aesthetic (NOI20_aesthetic)	C++20	100 / 100	265 ms	45324 KiB

Aesthetic

#include <iostream>
#include <climits>
#include <algorithm>
#include <queue>
#include <fstream>

using namespace std;
const int N=3e5+5;

struct Edge{
    int u, v, w;
    void tie(int &_u, int &_v, int &_w)
    {
        _u=u;
        _v=v;
        _w=w;
    }
};
struct Node{
    int v, w, id;
};
Edge edge[N];
vector<Node>g[N];
int n, m, u, v, w, mx[N], num[N], low[N], cnt, ok[N];
long long d1[N], dn[N], res, l, r, mid;
void JQK(int S, long long d[])
{
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
    for(int i=1;i<=n;i++)
        d[i]=LLONG_MAX;
    d[S]=0;
    q.push({0,S});
    while(!q.empty())
    {
        auto [du,u]=q.top();
        q.pop();
        if(du!=d[u])
            continue;
        for(auto &e:g[u])
            if(d[e.v]>du+e.w)
            {
                d[e.v]=du+e.w;
                q.push({d[e.v],e.v});
            }
    }
}
vector<int>ans;
int dfs(int u, int pr=0)
{
    num[u]=low[u]=++cnt;
    int cc=(u==n);
    for(auto &[v,w,id]:g[u])
        if(v!=pr&&ok[id])
        {
            if(!num[v])
            {
                int tmp=dfs(v,u);
                low[u]=min(low[u],low[v]);
                if(tmp&&num[u]<low[v])
                    ans.push_back(id);
                cc|=tmp;
            }
            else
                low[u]=min(low[u],num[v]);
        }
    return cc;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if(fopen("beautiful.inp", "r")) {
        freopen("beautiful.inp", "r", stdin);
        freopen("beautiful.out", "w", stdout); }
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        edge[i]={u,v,w};
        g[u].push_back({v,w,i});
        g[v].push_back({u,w,i});
    }
    for(int i=m-1;i;i--)
        mx[i]=max(edge[i+1].w,mx[i+1]);
    JQK(1,d1);
    JQK(n,dn);
    res=l=d1[n];
    r=l+mx[1];
    while(l<=r)
    {
        mid=(l+r)/2;
        for(int i=1;i<=m;i++)
        {
            edge[i].tie(u,v,w);
            ok[i]=(min(d1[u]+dn[v],d1[v]+dn[u])+w<mid);
        }
        for(int i=1;i<=n;i++)
            num[i]=low[i]=0;
        cnt=0;
        ans.clear();
        dfs(1);

        cnt=!num[n];
        for(auto i:ans)
        {
            edge[i].tie(u,v,w);
            cnt|=(min(d1[u]+dn[v],d1[v]+dn[u])+w+mx[i]>=mid);
        }

        if(cnt)
        {
            l=mid+1;
            res=mid;
        }
        else
            r=mid-1;
    }
    cout<<res;
    return 0;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen("beautiful.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen("beautiful.out", "w", stdout); }
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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