oj.uz

Submission #409488

# Submission time Handle Problem Language Result Execution time Memory
409488 2021-05-20T23:29:51 Z 534351 Robot (JOI21_ho_t4) C++17
34 / 100
 302 ms 49100 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 = 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, vector<array<int, 3> > > 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, d, i});
        edge[v][c].PB({u, d, 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), [&](array<int, 3> a, array<int, 3> b)
            {
                return a[1] > b[1];
            });
            // 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];
            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[0]; ll dis = e[1]; int eid = e[2];
                ll nd = d + min(dis, sum[u][cl] - dis - cost[c]);
                if (dist[v] > nd)
                {
                    dist[v] = nd;
                    pq.push({nd, v, -1});
                }
                // 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[0]; ll dis = e[1]; int eid = e[2];
                    //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;
}

Compilation message

Main.cpp:98:18: warning: #warning cut time complexity by limiting it to two iterations? [-Wcpp]
   98 |                 #warning cut time complexity by limiting it to two iterations?
      |                  ^~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:99:50: warning: unused variable 'eid' [-Wunused-variable]
   99 |                 int v = e[0]; ll dis = e[1]; int eid = e[2];
      |                                                  ^~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14352 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14352 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 10 ms 14572 KB Output is correct
8 Correct 9 ms 14540 KB Output is correct
9 Correct 13 ms 15180 KB Output is correct
10 Correct 14 ms 15052 KB Output is correct
11 Correct 20 ms 14968 KB Output is correct
12 Correct 13 ms 14900 KB Output is correct
13 Correct 18 ms 14936 KB Output is correct
14 Correct 20 ms 15052 KB Output is correct
15 Correct 10 ms 14680 KB Output is correct
16 Correct 12 ms 14944 KB Output is correct
17 Correct 11 ms 14924 KB Output is correct
18 Correct 9 ms 14540 KB Output is correct
19 Correct 12 ms 14924 KB Output is correct
20 Correct 10 ms 14796 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 40276 KB Output is correct
2 Correct 130 ms 26740 KB Output is correct
3 Runtime error 116 ms 49100 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14352 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14352 KB Output is correct
6 Correct 9 ms 14412 KB Output is correct
7 Correct 10 ms 14572 KB Output is correct
8 Correct 9 ms 14540 KB Output is correct
9 Correct 13 ms 15180 KB Output is correct
10 Correct 14 ms 15052 KB Output is correct
11 Correct 20 ms 14968 KB Output is correct
12 Correct 13 ms 14900 KB Output is correct
13 Correct 18 ms 14936 KB Output is correct
14 Correct 20 ms 15052 KB Output is correct
15 Correct 10 ms 14680 KB Output is correct
16 Correct 12 ms 14944 KB Output is correct
17 Correct 11 ms 14924 KB Output is correct
18 Correct 9 ms 14540 KB Output is correct
19 Correct 12 ms 14924 KB Output is correct
20 Correct 10 ms 14796 KB Output is correct
21 Correct 302 ms 40276 KB Output is correct
22 Correct 130 ms 26740 KB Output is correct
23 Runtime error 116 ms 49100 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -