oj.uz

Submission #705834

# Submission time Handle Problem Language Result Execution time Memory
705834 2023-03-05T12:54:16 Z noedit Aesthetic (NOI20_aesthetic) C++17
38 / 100
 613 ms 48564 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;
}

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 1 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 1 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 494 ms 38192 KB Output is correct
2 Correct 461 ms 38328 KB Output is correct
3 Correct 553 ms 37804 KB Output is correct
4 Correct 503 ms 37848 KB Output is correct
5 Correct 456 ms 38060 KB Output is correct
6 Correct 503 ms 38816 KB Output is correct
7 Correct 493 ms 38632 KB Output is correct
8 Correct 504 ms 38860 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 39072 KB Output is correct
2 Correct 477 ms 38256 KB Output is correct
3 Correct 469 ms 38268 KB Output is correct
4 Correct 509 ms 38932 KB Output is correct
5 Correct 463 ms 38104 KB Output is correct
6 Correct 522 ms 38348 KB Output is correct
7 Correct 484 ms 38280 KB Output is correct
8 Correct 509 ms 38464 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 35952 KB Output is correct
2 Correct 202 ms 34084 KB Output is correct
3 Correct 219 ms 33216 KB Output is correct
4 Correct 265 ms 33260 KB Output is correct
5 Correct 269 ms 33196 KB Output is correct
6 Correct 232 ms 33356 KB Output is correct
7 Correct 221 ms 33376 KB Output is correct
8 Correct 256 ms 33428 KB Output is correct
9 Correct 246 ms 33180 KB Output is correct
10 Correct 256 ms 33604 KB Output is correct
11 Correct 222 ms 33400 KB Output is correct
12 Correct 493 ms 36228 KB Output is correct
13 Correct 235 ms 33380 KB Output is correct
14 Correct 120 ms 40388 KB Output is correct
15 Correct 124 ms 40264 KB Output is correct
16 Correct 482 ms 36176 KB Output is correct
17 Correct 448 ms 35184 KB Output is correct
18 Correct 492 ms 35844 KB Output is correct
19 Correct 189 ms 33928 KB Output is correct
20 Correct 204 ms 34008 KB Output is correct
21 Correct 186 ms 33920 KB Output is correct
22 Correct 183 ms 33912 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 35952 KB Output is correct
2 Correct 202 ms 34084 KB Output is correct
3 Correct 219 ms 33216 KB Output is correct
4 Correct 265 ms 33260 KB Output is correct
5 Correct 269 ms 33196 KB Output is correct
6 Correct 232 ms 33356 KB Output is correct
7 Correct 221 ms 33376 KB Output is correct
8 Correct 256 ms 33428 KB Output is correct
9 Correct 246 ms 33180 KB Output is correct
10 Correct 256 ms 33604 KB Output is correct
11 Correct 222 ms 33400 KB Output is correct
12 Correct 493 ms 36228 KB Output is correct
13 Correct 235 ms 33380 KB Output is correct
14 Correct 120 ms 40388 KB Output is correct
15 Correct 124 ms 40264 KB Output is correct
16 Correct 482 ms 36176 KB Output is correct
17 Correct 448 ms 35184 KB Output is correct
18 Correct 492 ms 35844 KB Output is correct
19 Correct 189 ms 33928 KB Output is correct
20 Correct 204 ms 34008 KB Output is correct
21 Correct 186 ms 33920 KB Output is correct
22 Correct 183 ms 33912 KB Output is correct
23 Correct 613 ms 36100 KB Output is correct
24 Correct 271 ms 33996 KB Output is correct
25 Correct 245 ms 27944 KB Output is correct
26 Correct 218 ms 27340 KB Output is correct
27 Correct 230 ms 27400 KB Output is correct
28 Correct 239 ms 28228 KB Output is correct
29 Correct 225 ms 27476 KB Output is correct
30 Correct 252 ms 27724 KB Output is correct
31 Correct 239 ms 27880 KB Output is correct
32 Correct 225 ms 27212 KB Output is correct
33 Correct 270 ms 27872 KB Output is correct
34 Correct 584 ms 35308 KB Output is correct
35 Correct 246 ms 27524 KB Output is correct
36 Correct 180 ms 48564 KB Output is correct
37 Correct 207 ms 48420 KB Output is correct
38 Incorrect 538 ms 34968 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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