oj.uz

Submission #409487

# Submission time Handle Problem Language Result Execution time Memory
409487 2021-05-20T23:00:56 Z 534351 Robot (JOI21_ho_t4) C++17
24 / 100
 944 ms 76272 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--)

#define int long long

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

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];
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, color

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, d});
        edge[v][c].PB({u, d});
        sum[u][c] += d;
        sum[v][c] += d;
        // edge[u].PB({v, c, d});
        // edge[v].PB({u, c, d});
    }
    // FOR(u, 0, N)
    // {
    //     for (auto p : edge[u])
    //     {
    //         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, 0});
    while(!pq.empty())
    {
        ll d = pq.top()[0]; int u = pq.top()[1], c = pq.top()[2];
        pq.pop();
        if (c != 0)
        {
            if (d != special[u][c]) continue;
            for (auto p : edge[u][c]) //you can take an edge for free if you just came here w edge of that color && deg is 2.
            {
                int v = p.fi;
                if (dist[v] > d)
                {
                    dist[v] = d;
                    pq.push({d, v, 0});
                }
            }
        }
        else
        {
            if (d != dist[u]) continue;
            for (auto p : edge[u])
            {
                int cl = p.fi;
                for (auto e : p.se)
                {
                    int v = e.fi; ll dis = e.se;
                    //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, 0});
                    }
                    //but also set the special distance. here you have to actually pay to set this.
                    nd = d + dis;
                    if ((special[v].find(cl) == special[v].end() || special[v][cl] > nd) && SZ(edge[v][cl]) == 2)
                    {
                        special[v][cl] = nd;
                        pq.push({nd, v, cl});
                    }
                }
            }
        }
    }
    ans = dist[N - 1];
    if (ans >= LLINF) ans = -1;
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14344 KB Output is correct
3 Correct 9 ms 14364 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14540 KB Output is correct
8 Correct 9 ms 14468 KB Output is correct
9 Correct 12 ms 15016 KB Output is correct
10 Correct 11 ms 14924 KB Output is correct
11 Correct 10 ms 14796 KB Output is correct
12 Incorrect 13 ms 14708 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 29972 KB Output is correct
2 Correct 73 ms 22528 KB Output is correct
3 Correct 201 ms 27588 KB Output is correct
4 Correct 122 ms 24748 KB Output is correct
5 Correct 944 ms 76272 KB Output is correct
6 Correct 719 ms 68644 KB Output is correct
7 Correct 359 ms 51224 KB Output is correct
8 Correct 380 ms 41292 KB Output is correct
9 Correct 392 ms 41408 KB Output is correct
10 Correct 306 ms 41464 KB Output is correct
11 Correct 143 ms 30876 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 8 ms 14344 KB Output is correct
3 Correct 9 ms 14364 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 9 ms 14540 KB Output is correct
8 Correct 9 ms 14468 KB Output is correct
9 Correct 12 ms 15016 KB Output is correct
10 Correct 11 ms 14924 KB Output is correct
11 Correct 10 ms 14796 KB Output is correct
12 Incorrect 13 ms 14708 KB Output isn't correct
13 Halted 0 ms 0 KB -