oj.uz

Submission #409494

# Submission time Handle Problem Language Result Execution time Memory
409494 2021-05-20T23:36:40 Z 534351 Robot (JOI21_ho_t4) C++17
100 / 100
 1672 ms 114684 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

const long long LLINF = 3e18;
const int MAXN = 200013;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M;
map<int, vpi> edge[MAXN];
int color[MAXN];
int cost[MAXN];
map<int, ll> sum[MAXN];
//you can only save it if its color is unique or its color is twice and you just used one of them & paid.
ll dist[MAXN];
map<int, ll> special[MAXN];
priority_queue<array<ll, 3>, vector<array<ll, 3> >, greater<array<ll, 3> > > pq;
ll ans;
//distance, vertex, edge

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    FOR(i, 0, M)
    {
        int u, v, c, d;
        cin >> u >> v >> c >> d; u--; v--;
        edge[u][c].PB({v, i});
        edge[v][c].PB({u, i});
        sum[u][c] += d;
        sum[v][c] += d;
        color[i] = c;
        cost[i] = d;
        // edge[u].PB({v, c, d});
        // edge[v].PB({u, c, d});
    }
    FOR(u, 0, N)
    {
        for (auto &p : edge[u])
        {
            sort(ALL(p.se), [&](pii a, pii b)
            {
                return cost[a.se] > cost[b.se];
            });
            // for (auto e : p.se)
            // {
            //     cerr << "EDGE " << u << ' ' << e.fi << ' ' << " color " << p.fi << " dis " << e.se << endl;
            // }
        }
    }
    fill(dist, dist + N, LLINF);
    dist[0] = 0;
    pq.push({0, 0, -1});
    while(!pq.empty())
    {
        ll d = pq.top()[0]; int u = pq.top()[1], c = pq.top()[2];
        pq.pop();
        if (c != -1)
        {
            if (d != special[u][c]) continue;
            int cl = color[c];
            int it = 0;
            for (auto e : edge[u][cl]) //you can take an edge for free if you just came here w edge of that color && deg is 2.
            {
                // #warning cut time complexity by limiting it to two iterations?
                int v = e.fi, eid = e.se; ll dis = cost[eid];
                ll nd = d + min(dis, sum[u][cl] - dis - cost[c]);
                if (dist[v] > nd)
                {
                    dist[v] = nd;
                    pq.push({nd, v, -1});
                }
                it++;
                if (it > 3) break;
                // if (special[v].find(eid) == special[v].end() || special[v])
            }
        }
        else
        {
            if (d != dist[u]) continue;
            for (auto p : edge[u])
            {
                int cl = p.fi;
                for (auto e : p.se)
                {
                    int v = e.fi, eid = e.se; ll dis = cost[eid];
                    //no guarantees -> you just need to make this the unique color from u.
                    ll nd = d + min(dis, sum[u][cl] - dis);
                    // ll nd = d + dis;
                    if (dist[v] > nd)
                    {
                        dist[v] = nd;
                        pq.push({nd, v, -1});
                    }
                    //but also set the special distance. here you have to actually pay to set this.
                    nd = d + dis;
                    if ((special[v].find(eid) == special[v].end() || special[v][eid] > nd))
                    {
                        special[v][eid] = nd;
                        pq.push({nd, v, eid});
                    }
                }
            }
        }
    }
    ans = dist[N - 1];
    if (ans >= LLINF) ans = -1;
    cout << ans << '\n';
    return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28492 KB Output is correct
2 Correct 16 ms 28424 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 16 ms 28480 KB Output is correct
5 Correct 16 ms 28560 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 19 ms 28720 KB Output is correct
8 Correct 17 ms 28680 KB Output is correct
9 Correct 21 ms 29260 KB Output is correct
10 Correct 21 ms 29132 KB Output is correct
11 Correct 19 ms 29060 KB Output is correct
12 Correct 18 ms 28884 KB Output is correct
13 Correct 18 ms 29016 KB Output is correct
14 Correct 19 ms 29056 KB Output is correct
15 Correct 17 ms 28748 KB Output is correct
16 Correct 26 ms 28908 KB Output is correct
17 Correct 18 ms 28876 KB Output is correct
18 Correct 16 ms 28632 KB Output is correct
19 Correct 19 ms 28976 KB Output is correct
20 Correct 17 ms 28780 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 53912 KB Output is correct
2 Correct 134 ms 40628 KB Output is correct
3 Correct 585 ms 60136 KB Output is correct
4 Correct 217 ms 45040 KB Output is correct
5 Correct 1518 ms 106848 KB Output is correct
6 Correct 1259 ms 97392 KB Output is correct
7 Correct 831 ms 81984 KB Output is correct
8 Correct 582 ms 77168 KB Output is correct
9 Correct 601 ms 77188 KB Output is correct
10 Correct 533 ms 66472 KB Output is correct
11 Correct 166 ms 44300 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28492 KB Output is correct
2 Correct 16 ms 28424 KB Output is correct
3 Correct 16 ms 28492 KB Output is correct
4 Correct 16 ms 28480 KB Output is correct
5 Correct 16 ms 28560 KB Output is correct
6 Correct 16 ms 28492 KB Output is correct
7 Correct 19 ms 28720 KB Output is correct
8 Correct 17 ms 28680 KB Output is correct
9 Correct 21 ms 29260 KB Output is correct
10 Correct 21 ms 29132 KB Output is correct
11 Correct 19 ms 29060 KB Output is correct
12 Correct 18 ms 28884 KB Output is correct
13 Correct 18 ms 29016 KB Output is correct
14 Correct 19 ms 29056 KB Output is correct
15 Correct 17 ms 28748 KB Output is correct
16 Correct 26 ms 28908 KB Output is correct
17 Correct 18 ms 28876 KB Output is correct
18 Correct 16 ms 28632 KB Output is correct
19 Correct 19 ms 28976 KB Output is correct
20 Correct 17 ms 28780 KB Output is correct
21 Correct 339 ms 53912 KB Output is correct
22 Correct 134 ms 40628 KB Output is correct
23 Correct 585 ms 60136 KB Output is correct
24 Correct 217 ms 45040 KB Output is correct
25 Correct 1518 ms 106848 KB Output is correct
26 Correct 1259 ms 97392 KB Output is correct
27 Correct 831 ms 81984 KB Output is correct
28 Correct 582 ms 77168 KB Output is correct
29 Correct 601 ms 77188 KB Output is correct
30 Correct 533 ms 66472 KB Output is correct
31 Correct 166 ms 44300 KB Output is correct
32 Correct 793 ms 66952 KB Output is correct
33 Correct 572 ms 56876 KB Output is correct
34 Correct 816 ms 76976 KB Output is correct
35 Correct 588 ms 66028 KB Output is correct
36 Correct 569 ms 71092 KB Output is correct
37 Correct 800 ms 78376 KB Output is correct
38 Correct 834 ms 85384 KB Output is correct
39 Correct 579 ms 64100 KB Output is correct
40 Correct 588 ms 82212 KB Output is correct
41 Correct 656 ms 82424 KB Output is correct
42 Correct 875 ms 85420 KB Output is correct
43 Correct 393 ms 55980 KB Output is correct
44 Correct 1111 ms 78448 KB Output is correct
45 Correct 477 ms 72308 KB Output is correct
46 Correct 384 ms 70192 KB Output is correct
47 Correct 697 ms 80964 KB Output is correct
48 Correct 1672 ms 114684 KB Output is correct