oj.uz

Submission #705836

# Submission time Handle Problem Language Result Execution time Memory
705836 2023-03-05T13:04:48 Z noedit Aesthetic (NOI20_aesthetic) C++17
38 / 100
 576 ms 49184 KB 
#include <bits/stdc++.h>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;

#define int long long
//#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

const int INF = 1e18;

vector<vector<pair<int, int> > > g;

vector<int> es;
vector<int> tin, go;

vector<ll> suff;
vector<bool> used;
vector<ll> d1, dn;

int timer = 0;

bool flag = 0;

void dfs(int v, int p, ll x)
{
    used[v] = 1;
    tin[v] = go[v] = timer++;
    for (auto&[u, ind] : g[v])
    {
        if (p == u) continue;
        if (min(d1[v] + dn[u], d1[u] + dn[v]) + es[ind] >= x) continue;
        if (used[u])
        {
            go[v] = min(go[v], tin[u]);
        }
        else
        {
            dfs(u, v, x);
            go[v] = min(go[v], go[u]);
            if (go[u] > tin[v] && min(d1[v] + dn[u], d1[u] + dn[v]) + es[ind] + suff[ind + 1] >= x)
            {
                flag = 1;
            }
        }
    }
}

bool f(ll x)
{
    flag = 0;
    timer = 0;
    fill(tin.begin(), tin.end(), 0);
    fill(go.begin(), go.end(), INF);
    fill(used.begin(), used.end(), 0);
    dfs(0, -1, x);
    return flag || tin.back() == 0;
}

void dijkstra(int s, vector<ll>& dist)
{
    fill(dist.begin(), dist.end(), 1e18);
    set<pair<ll, int> > st;
    st.insert({0, s});
    dist[s] = 0;
    while (!st.empty())
    {
        auto [d, v] = *st.begin();
        st.erase(st.begin());
        for (auto&[u, ind] : g[v])
        {
            ll w = es[ind];
            if (dist[u] > dist[v] + w)
            {
                st.erase({dist[u], u});
                dist[u] = dist[v] + w;
                st.insert({dist[u], u});
            }
        }
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    es.resize(m);
    suff.resize(m + 1);
    g.resize(n);
    tin.resize(n);
    d1.resize(n);
    dn.resize(n);
    go.resize(n);
    used.resize(n);
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
        es[i] = z;
    }
    suff[m - 1] = es[m - 1];
    for (int i = m - 2; i >= 0; i--)
    {
        suff[i] = max(suff[i + 1], es[i]);
    }

    dijkstra(0, d1);
    dijkstra(n - 1, dn);

    ll lt = d1[n - 1], rt = d1[n - 1] + suff[0] + 1;
    while (rt - lt  > 1)
    {
        ll mid = (lt + rt) >> 1;
        if (f(mid))
        {
            lt = mid;
        }
        else
        {
            rt = mid;
        }
    }
    cout << lt;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}


/*
4 4
1 2 1 3
1 1
1 2
1 3
1 4
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 37896 KB Output is correct
2 Correct 483 ms 38044 KB Output is correct
3 Correct 471 ms 37628 KB Output is correct
4 Correct 459 ms 37592 KB Output is correct
5 Correct 497 ms 37844 KB Output is correct
6 Correct 521 ms 38624 KB Output is correct
7 Correct 513 ms 38396 KB Output is correct
8 Correct 478 ms 38728 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 38736 KB Output is correct
2 Correct 527 ms 38092 KB Output is correct
3 Correct 536 ms 38004 KB Output is correct
4 Correct 519 ms 38696 KB Output is correct
5 Correct 531 ms 37880 KB Output is correct
6 Correct 507 ms 38052 KB Output is correct
7 Correct 511 ms 38036 KB Output is correct
8 Correct 546 ms 38228 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 35772 KB Output is correct
2 Correct 227 ms 33832 KB Output is correct
3 Correct 235 ms 32920 KB Output is correct
4 Correct 246 ms 32988 KB Output is correct
5 Correct 266 ms 32960 KB Output is correct
6 Correct 254 ms 33044 KB Output is correct
7 Correct 244 ms 33088 KB Output is correct
8 Correct 268 ms 33188 KB Output is correct
9 Correct 240 ms 32944 KB Output is correct
10 Correct 245 ms 33448 KB Output is correct
11 Correct 253 ms 33052 KB Output is correct
12 Correct 469 ms 36036 KB Output is correct
13 Correct 267 ms 33112 KB Output is correct
14 Correct 129 ms 40136 KB Output is correct
15 Correct 125 ms 40116 KB Output is correct
16 Correct 521 ms 35984 KB Output is correct
17 Correct 448 ms 35104 KB Output is correct
18 Correct 428 ms 35504 KB Output is correct
19 Correct 193 ms 33944 KB Output is correct
20 Correct 193 ms 33932 KB Output is correct
21 Correct 190 ms 33964 KB Output is correct
22 Correct 189 ms 33956 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 35772 KB Output is correct
2 Correct 227 ms 33832 KB Output is correct
3 Correct 235 ms 32920 KB Output is correct
4 Correct 246 ms 32988 KB Output is correct
5 Correct 266 ms 32960 KB Output is correct
6 Correct 254 ms 33044 KB Output is correct
7 Correct 244 ms 33088 KB Output is correct
8 Correct 268 ms 33188 KB Output is correct
9 Correct 240 ms 32944 KB Output is correct
10 Correct 245 ms 33448 KB Output is correct
11 Correct 253 ms 33052 KB Output is correct
12 Correct 469 ms 36036 KB Output is correct
13 Correct 267 ms 33112 KB Output is correct
14 Correct 129 ms 40136 KB Output is correct
15 Correct 125 ms 40116 KB Output is correct
16 Correct 521 ms 35984 KB Output is correct
17 Correct 448 ms 35104 KB Output is correct
18 Correct 428 ms 35504 KB Output is correct
19 Correct 193 ms 33944 KB Output is correct
20 Correct 193 ms 33932 KB Output is correct
21 Correct 190 ms 33964 KB Output is correct
22 Correct 189 ms 33956 KB Output is correct
23 Correct 576 ms 36172 KB Output is correct
24 Correct 252 ms 34076 KB Output is correct
25 Correct 259 ms 28072 KB Output is correct
26 Correct 219 ms 27468 KB Output is correct
27 Correct 246 ms 27484 KB Output is correct
28 Correct 225 ms 28348 KB Output is correct
29 Correct 224 ms 27612 KB Output is correct
30 Correct 226 ms 27860 KB Output is correct
31 Correct 262 ms 28040 KB Output is correct
32 Correct 240 ms 27628 KB Output is correct
33 Correct 251 ms 28228 KB Output is correct
34 Correct 497 ms 35880 KB Output is correct
35 Correct 277 ms 28136 KB Output is correct
36 Correct 177 ms 49096 KB Output is correct
37 Correct 190 ms 49184 KB Output is correct
38 Incorrect 534 ms 35804 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -