Submission #1126538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126538		whoknow	Aesthetic (NOI20_aesthetic)	C++20	100 / 100	557 ms	73220 KiB

Aesthetic

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 300005
#define ii pair<ll,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF = 1e18;
int n, m;
struct edge
{
    int u, v, w;
} a[MAXN];
vector<ii>g[MAXN];
namespace sub1
{
int timedfs;
int num[MAXN], low[MAXN];
ll cost[MAXN], d[2][MAXN];
vector<ii>adj[MAXN];
struct cmp
{
    bool operator()(ii x, ii y)
    {
        return x.F > y.F;
    }
};
bool minimize(ll &x, ll y)
{
    if(x > y)
        return x = y, 1;
    return 0;
}
void bfs(int k, int st)
{
    for(int i = 1; i <= n; i++)
        d[k][i] = INF;
    priority_queue<ii, vector<ii>, cmp>q;
    q.push({0, st});
    d[k][st] = 0;
    while(sz(q))
    {
        ii top = q.top();
        q.pop();
        ll kc = top.F;
        int u = top.S;
        if(u != st && (u == n || u == 1))
            continue;
        for(ii i : g[u])
        {
            int v = i.F, id = i.S;
            if(minimize(d[k][v], kc + a[id].w))
                q.push({d[k][v], v});
        }
    }
}
bool dfs(int u, int p, ll L)
{
    num[u] = low[u] = ++timedfs;
    for(ii i : adj[u])
    {
        int v = i.F, id = i.S;
        if(v == p)
            continue;
        if(num[v])
            low[u] = min(low[u], num[v]);
        else
        {
            if(dfs(v, u, L))
                return 1;
            low[u] = min(low[u], low[v]);
            if(low[v] > num[u])
                if(low[n] && low[v] <= num[n] && (d[0][u] + d[1][v] + a[id].w == d[0][n] || d[1][u] + d[0][v] + a[id].w == d[0][n]) && min(d[0][u] + d[1][v], d[0][v] + d[1][u]) + a[id].w + cost[id + 1] >= L)
                    return 1;
        }
    }
    return 0;
}
bool check(ll L)
{
    timedfs = 0;
    for(int i = 1; i <= n; i++)
    {
        num[i] = low[i] = 0;
        vector<ii>().swap(adj[i]);
    }
    for(int i = 1; i <= m; i++)
        if(d[0][a[i].u] + d[1][a[i].v] + a[i].w < L || d[0][a[i].v] + d[1][a[i].u] + a[i].w < L)
            adj[a[i].u].push_back({a[i].v, i}), adj[a[i].v].push_back({a[i].u, i});
    return dfs(1, 0, L);
}
ll bina()
{
    ll l = d[0][n], r = d[0][n] + cost[1];
    while(l < r)
    {
        ll mid = (l + r + 1) / 2;
        if(check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}
void solve()
{
    bfs(0, 1);
    bfs(1, n);
    for(int i = m; i >= 1; i--)
        cost[i] = max(cost[i + 1], (ll)a[i].w);
    cout << bina();
}
}
main()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
        a[i] = {x, y, z};
    }
    sub1::solve();
}
/**
5 6
1 2 1
1 5 1
2 3 0
2 4 0
2 5 0
3 4 1
phải check ở có thuộc đường đi ngắn nhất không ở trong tarjan là vì:
đường đi bé nhất luôn <= L => chỉ có thay đổi đường đi ngắn nhất >= thì những cái còn lại sẽ bị thay đổi theo vì đấy là cạnh cầu
và tất nhiên đường đi bé nhất phải có n đi qua nó để tới 1
**/

Compilation message (stderr)

Aesthetic.cpp:117:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 | main()
      | ^~~~
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("TEST.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