oj.uz

Submission #476028

# Submission time Handle Problem Language Result Execution time Memory
476028 2021-09-24T15:59:34 Z CodeChamp_SS Robot (JOI21_ho_t4) C++17
100 / 100
 1117 ms 96072 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ff                  first
#define ss                  second
#define pb                  push_back
#define eb                  emplace_back
#define mp                  make_pair
#define lb                  lower_bound
#define ub                  upper_bound
#define setbits(x)          __builtin_popcountll(x)
#define zrobits(x)          __builtin_ctzll(x)
#define sz(v)               (int)v.size()
#define ps(y)               cout << fixed << setprecision(y)
#define ms(arr, v)          memset(arr, v, sizeof(arr))
#define all(v)              v.begin(), v.end()
#define rall(v)             v.rbegin(), v.rend()
#define trav(x, v)          for(auto &x: v)
#define w(t)                int t; cin >> t; while(t--)
#define rep(i, a, b)        for(int i = a; i <= b; i++)
#define rrep(i, a, b)       for(int i = a; i >= b; i--)
#define rep0(i, n)          rep(i, 0, n - 1)
#define rrep0(i, n)         rrep(i, n - 1, 0)
#define rep1(i, n)          rep(i, 1, n)
#define rrep1(i, n)         rrep(i, n, 1)
#define inp(arr, n)         rep0(i, n) cin >> arr[i];

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef map<ll, ll> mii;
typedef map<char, ll> mci;
typedef priority_queue<ll> pq_mx;
typedef priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq_mn;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds;
/*
 * find_by_order(i) -> returns an iterator to the element at ith position (0 based)
 * order_of_key(i)  -> returns the position of element i (0 based)
 */

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll inf = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fio() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
}

struct Edge {
    int v, c;
    ll p;
};

int n, m;
ll dp[N];
vector<Edge> gr[N];
map<int, vector<Edge>> cgr[N];
mii dp1[N], pre[N];

int main() {
    fio();

    cin >> n >> m;
    rep0(x, m) {
        int u, v, c;
        ll p;
        cin >> u >> v >> c >> p;
        gr[u].pb({v, c, p}), gr[v].pb({u, c, p});
        cgr[u][c].pb({v, c, p}), cgr[v][c].pb({u, c, p});
        pre[u][c] += p, pre[v][c] += p;
    }
    rep0(x, n + 1) dp[x] = inf;

    pq_mn q;
    q.push({0, 1, 0}), dp[1] = 0;
    while (!q.empty()) {
        auto[cost, cur, col] = q.top();
        q.pop();
        if (col) {
            if (dp1[cur][col] != cost) continue;
            trav(neigh, cgr[cur][col]) {
                if (neigh.c != col) continue;
                // we can't flip the same edge again
                ll curCost = pre[cur][neigh.c] - neigh.p + cost;
                if (curCost < dp[neigh.v]) {
                    dp[neigh.v] = curCost;
                    q.push({dp[neigh.v], neigh.v, 0});
                }
            }
        } else {
            if (dp[cur] != cost) continue;
            trav(neigh, gr[cur]) {
                // we don't flip this edge
                ll curCost = pre[cur][neigh.c] - neigh.p + cost;
                if (curCost < dp[neigh.v]) {
                    dp[neigh.v] = curCost;
                    q.push({dp[neigh.v], neigh.v, 0});
                }
                // we flip this edge but not others with the same color
                curCost = neigh.p + cost;
                if (curCost < dp[neigh.v]) {
                    dp[neigh.v] = curCost;
                    q.push({dp[neigh.v], neigh.v, 0});
                }
                // we don't include this edge and robot will leave 'cur' with some other edge having color 'col'
                curCost = cost;
                if (!dp1[neigh.v].count(neigh.c) or dp1[neigh.v][neigh.c] > curCost) {
                    dp1[neigh.v][neigh.c] = curCost;
                    q.push({curCost, neigh.v, neigh.c});
                }
            }
        }
    }
    cout << (dp[n] == inf ? -1 : dp[n]);

    return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16668 KB Output is correct
2 Correct 10 ms 16648 KB Output is correct
3 Correct 9 ms 16768 KB Output is correct
4 Correct 8 ms 16772 KB Output is correct
5 Correct 8 ms 16716 KB Output is correct
6 Correct 9 ms 16716 KB Output is correct
7 Correct 10 ms 16972 KB Output is correct
8 Correct 11 ms 16784 KB Output is correct
9 Correct 14 ms 17484 KB Output is correct
10 Correct 12 ms 17356 KB Output is correct
11 Correct 11 ms 17228 KB Output is correct
12 Correct 10 ms 17100 KB Output is correct
13 Correct 10 ms 17228 KB Output is correct
14 Correct 12 ms 17112 KB Output is correct
15 Correct 10 ms 16972 KB Output is correct
16 Correct 11 ms 17100 KB Output is correct
17 Correct 12 ms 17188 KB Output is correct
18 Correct 9 ms 16972 KB Output is correct
19 Correct 11 ms 17100 KB Output is correct
20 Correct 10 ms 17100 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 39188 KB Output is correct
2 Correct 117 ms 28124 KB Output is correct
3 Correct 258 ms 37692 KB Output is correct
4 Correct 176 ms 31772 KB Output is correct
5 Correct 1105 ms 90504 KB Output is correct
6 Correct 958 ms 83640 KB Output is correct
7 Correct 374 ms 68092 KB Output is correct
8 Correct 558 ms 63280 KB Output is correct
9 Correct 561 ms 63508 KB Output is correct
10 Correct 379 ms 56160 KB Output is correct
11 Correct 186 ms 40004 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16668 KB Output is correct
2 Correct 10 ms 16648 KB Output is correct
3 Correct 9 ms 16768 KB Output is correct
4 Correct 8 ms 16772 KB Output is correct
5 Correct 8 ms 16716 KB Output is correct
6 Correct 9 ms 16716 KB Output is correct
7 Correct 10 ms 16972 KB Output is correct
8 Correct 11 ms 16784 KB Output is correct
9 Correct 14 ms 17484 KB Output is correct
10 Correct 12 ms 17356 KB Output is correct
11 Correct 11 ms 17228 KB Output is correct
12 Correct 10 ms 17100 KB Output is correct
13 Correct 10 ms 17228 KB Output is correct
14 Correct 12 ms 17112 KB Output is correct
15 Correct 10 ms 16972 KB Output is correct
16 Correct 11 ms 17100 KB Output is correct
17 Correct 12 ms 17188 KB Output is correct
18 Correct 9 ms 16972 KB Output is correct
19 Correct 11 ms 17100 KB Output is correct
20 Correct 10 ms 17100 KB Output is correct
21 Correct 245 ms 39188 KB Output is correct
22 Correct 117 ms 28124 KB Output is correct
23 Correct 258 ms 37692 KB Output is correct
24 Correct 176 ms 31772 KB Output is correct
25 Correct 1105 ms 90504 KB Output is correct
26 Correct 958 ms 83640 KB Output is correct
27 Correct 374 ms 68092 KB Output is correct
28 Correct 558 ms 63280 KB Output is correct
29 Correct 561 ms 63508 KB Output is correct
30 Correct 379 ms 56160 KB Output is correct
31 Correct 186 ms 40004 KB Output is correct
32 Correct 150 ms 37576 KB Output is correct
33 Correct 191 ms 37288 KB Output is correct
34 Correct 451 ms 59044 KB Output is correct
35 Correct 354 ms 49456 KB Output is correct
36 Correct 354 ms 55700 KB Output is correct
37 Correct 422 ms 60052 KB Output is correct
38 Correct 381 ms 67316 KB Output is correct
39 Correct 174 ms 43248 KB Output is correct
40 Correct 546 ms 64732 KB Output is correct
41 Correct 578 ms 64900 KB Output is correct
42 Correct 585 ms 72084 KB Output is correct
43 Correct 234 ms 43708 KB Output is correct
44 Correct 461 ms 54736 KB Output is correct
45 Correct 410 ms 57780 KB Output is correct
46 Correct 356 ms 57780 KB Output is correct
47 Correct 369 ms 58860 KB Output is correct
48 Correct 1117 ms 96072 KB Output is correct