Submission #1124053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124053		fern	Aesthetic (NOI20_aesthetic)	C++20	100 / 100	583 ms	101908 KiB

Aesthetic

#include <bits/stdc++.h>
#define f0(i, n) for(int i=0; i<n; i++)
#define f1(i, n) for(int i=1; i<=n; i++)
#define fi first
#define se second
#define pb push_back
#define el cout << "\n";
#define sz(A) (int)A.size()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define all(x) x.begin(), x.end()
#define faster                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                     \
    cout.tie(NULL);
#define AWA signed main()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef unsigned long long ull;
typedef string str;
typedef vector<int> vi;
const int maxn=1000002;
const int mod=1000000007;
const ll inf = 1e18;
#define bit(mask, i) ((mask>>i)&1)
#define lon(x) ((1ll) << (x))
template <class X, class Y>
    bool maximize(X &x, const Y&y)
    {
        if(x<y)
        {
            x=y;
            return true;
        }
        else return false;
    }
template <class X, class Y>
    bool minimize(X &x, const Y&y)
    {
        if(x>y)
        {
            x=y;
            return true;
        }
        else return false;
    }

void file()
{
      #define TASK "INCGRAPH"
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
}

int n, m;
ll eu[maxn], ev[maxn], ew[maxn], Max[maxn];
vector<ii>adj[maxn];
struct Data{
    ll dis[maxn];
    void dijkstra(int s){
        FOR(i, 1, n) dis[i] = inf;
        dis[s] = 0;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.push(make_pair(dis[s], s));
        while(sz(pq)){
            ii top = pq.top(); pq.pop();
            int dd = top.fi, u = top.se;
            for(ii it: adj[u]){
                int v = it.fi, w = it.se;
                if(dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    pq.push(make_pair(dis[v], v));
                }
            }
        }
    }
}d1, dn;
int low[maxn], num[maxn], timer = 0;
bool contain[maxn];
vector<ii> g[maxn];
bool ok = 0;
void dfs(int s, int pre, ll mid){
    if(s == n) contain[s] = 1;
    low[s] = num[s] = ++timer;
    for(ii it: g[s]){
        int v = it.fi, id = it.se;
        if(id == pre) continue;
        if(!num[v]){
            dfs(v, id, mid); 
            contain[s] |= contain[v];
            low[s] = min(low[s], low[v]);
            if(low[v] == num[v] && contain[v]){
                if(d1.dis[eu[id]] + dn.dis[ev[id]] + ew[id] == d1.dis[n] && d1.dis[eu[id]] + dn.dis[ev[id]] + ew[id] + Max[id] >= d1.dis[n] + mid){
                    ok = 1;
                }
            }
        }
        else low[s] = min(low[s], num[v]);
    }
}
bool check(ll mid){

    FOR(i, 1, n){
        g[i].clear();
        low[i] = num[i] = 0; 
        contain[i] = 0;
    }
    timer = 0; 
    ok = 0;
    f0(i, m){
        ll u = eu[i], v = ev[i], w = ew[i];
        if(d1.dis[u] + dn.dis[v] + ew[i] < d1.dis[n] + mid) 
            g[u].pb(make_pair(v, i)), g[v].pb(make_pair(u, i));
        else if(d1.dis[v] + dn.dis[u] + ew[i] < d1.dis[n] + mid) 
            g[u].pb(make_pair(v, i)), g[v].pb(make_pair(u, i));
    }
    dfs(1, -1, mid);
    return(ok);
}
AWA
{
    faster;
    file();
    cin>>n>>m;
    f0(i, m){
        cin >> eu[i] >> ev[i] >> ew[i];
        adj[eu[i]].pb(make_pair(ev[i], ew[i])); 
        adj[ev[i]].pb(make_pair(eu[i], ew[i]));
    }
    for(int i = m - 2; i >= 0; i--){
        Max[i] = max(Max[i + 1], ew[i + 1]);
    }
    d1.dijkstra(1); 
    dn.dijkstra(n);
    f0(i, m){
        if(d1.dis[eu[i]] > d1.dis[ev[i]]) swap(eu[i], ev[i]);
    }
    ll l = 1, r = *max_element(ew + 1, ew + m + 1), ans = 0;
    while(l <= r){
        ll mid = (l + r) >> 1;
        if(check(mid))
        {
            ans = mid; 
            l = mid + 1;
        }
        else r = mid - 1;
    }

    cout << d1.dis[n] + ans;
    return 0;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'void file()':
Aesthetic.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(TASK".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