oj.uz

Submission #705833

# Submission time Handle Problem Language Result Execution time Memory
705833 2023-03-05T12:52:02 Z noedit Aesthetic (NOI20_aesthetic) C++17
38 / 100
 493 ms 43556 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 = 1e9;

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

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

vector<int> 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;
}

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 426 ms 34252 KB Output is correct
2 Correct 401 ms 34492 KB Output is correct
3 Correct 414 ms 34012 KB Output is correct
4 Correct 418 ms 34080 KB Output is correct
5 Correct 441 ms 34204 KB Output is correct
6 Correct 443 ms 34948 KB Output is correct
7 Correct 421 ms 34724 KB Output is correct
8 Correct 422 ms 35064 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 35028 KB Output is correct
2 Correct 449 ms 34384 KB Output is correct
3 Correct 415 ms 34440 KB Output is correct
4 Correct 425 ms 35008 KB Output is correct
5 Correct 416 ms 34296 KB Output is correct
6 Correct 401 ms 34364 KB Output is correct
7 Correct 435 ms 34436 KB Output is correct
8 Correct 426 ms 34648 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 30228 KB Output is correct
2 Correct 178 ms 28236 KB Output is correct
3 Correct 223 ms 26440 KB Output is correct
4 Correct 193 ms 26528 KB Output is correct
5 Correct 198 ms 26432 KB Output is correct
6 Correct 204 ms 26576 KB Output is correct
7 Correct 205 ms 26672 KB Output is correct
8 Correct 201 ms 26700 KB Output is correct
9 Correct 195 ms 26468 KB Output is correct
10 Correct 213 ms 26804 KB Output is correct
11 Correct 200 ms 26620 KB Output is correct
12 Correct 394 ms 30284 KB Output is correct
13 Correct 197 ms 26616 KB Output is correct
14 Correct 115 ms 33596 KB Output is correct
15 Correct 121 ms 33640 KB Output is correct
16 Correct 376 ms 30360 KB Output is correct
17 Correct 364 ms 29420 KB Output is correct
18 Correct 402 ms 29960 KB Output is correct
19 Correct 190 ms 28348 KB Output is correct
20 Correct 181 ms 28424 KB Output is correct
21 Correct 184 ms 28396 KB Output is correct
22 Correct 179 ms 28376 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 30228 KB Output is correct
2 Correct 178 ms 28236 KB Output is correct
3 Correct 223 ms 26440 KB Output is correct
4 Correct 193 ms 26528 KB Output is correct
5 Correct 198 ms 26432 KB Output is correct
6 Correct 204 ms 26576 KB Output is correct
7 Correct 205 ms 26672 KB Output is correct
8 Correct 201 ms 26700 KB Output is correct
9 Correct 195 ms 26468 KB Output is correct
10 Correct 213 ms 26804 KB Output is correct
11 Correct 200 ms 26620 KB Output is correct
12 Correct 394 ms 30284 KB Output is correct
13 Correct 197 ms 26616 KB Output is correct
14 Correct 115 ms 33596 KB Output is correct
15 Correct 121 ms 33640 KB Output is correct
16 Correct 376 ms 30360 KB Output is correct
17 Correct 364 ms 29420 KB Output is correct
18 Correct 402 ms 29960 KB Output is correct
19 Correct 190 ms 28348 KB Output is correct
20 Correct 181 ms 28424 KB Output is correct
21 Correct 184 ms 28396 KB Output is correct
22 Correct 179 ms 28376 KB Output is correct
23 Correct 493 ms 30468 KB Output is correct
24 Correct 243 ms 28516 KB Output is correct
25 Correct 200 ms 21740 KB Output is correct
26 Correct 210 ms 21200 KB Output is correct
27 Correct 200 ms 21132 KB Output is correct
28 Correct 203 ms 21964 KB Output is correct
29 Correct 206 ms 21244 KB Output is correct
30 Correct 201 ms 21480 KB Output is correct
31 Correct 209 ms 21612 KB Output is correct
32 Correct 215 ms 21300 KB Output is correct
33 Correct 211 ms 21740 KB Output is correct
34 Correct 467 ms 30060 KB Output is correct
35 Correct 214 ms 21584 KB Output is correct
36 Correct 183 ms 42612 KB Output is correct
37 Correct 191 ms 43556 KB Output is correct
38 Incorrect 463 ms 30164 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 -