oj.uz

Submission #476037

# Submission time Handle Problem Language Result Execution time Memory
476037 2021-09-24T16:21:48 Z CodeChamp_SS Robot (JOI21_ho_t4) C++17
100 / 100
 1181 ms 90868 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]) {
                // we can'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});
                }
            }
        } 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 9 ms 16716 KB Output is correct
2 Correct 9 ms 16740 KB Output is correct
3 Correct 8 ms 16716 KB Output is correct
4 Correct 9 ms 16716 KB Output is correct
5 Correct 9 ms 16816 KB Output is correct
6 Correct 10 ms 16672 KB Output is correct
7 Correct 11 ms 16976 KB Output is correct
8 Correct 9 ms 16760 KB Output is correct
9 Correct 13 ms 17512 KB Output is correct
10 Correct 13 ms 17440 KB Output is correct
11 Correct 11 ms 17236 KB Output is correct
12 Correct 11 ms 17100 KB Output is correct
13 Correct 11 ms 17196 KB Output is correct
14 Correct 14 ms 17100 KB Output is correct
15 Correct 10 ms 17100 KB Output is correct
16 Correct 13 ms 17100 KB Output is correct
17 Correct 13 ms 17160 KB Output is correct
18 Correct 9 ms 16972 KB Output is correct
19 Correct 11 ms 17108 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 231 ms 39196 KB Output is correct
2 Correct 94 ms 28004 KB Output is correct
3 Correct 228 ms 37796 KB Output is correct
4 Correct 133 ms 31784 KB Output is correct
5 Correct 1129 ms 90404 KB Output is correct
6 Correct 976 ms 79740 KB Output is correct
7 Correct 395 ms 64076 KB Output is correct
8 Correct 587 ms 59304 KB Output is correct
9 Correct 581 ms 59332 KB Output is correct
10 Correct 380 ms 53684 KB Output is correct
11 Correct 189 ms 38092 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16740 KB Output is correct
3 Correct 8 ms 16716 KB Output is correct
4 Correct 9 ms 16716 KB Output is correct
5 Correct 9 ms 16816 KB Output is correct
6 Correct 10 ms 16672 KB Output is correct
7 Correct 11 ms 16976 KB Output is correct
8 Correct 9 ms 16760 KB Output is correct
9 Correct 13 ms 17512 KB Output is correct
10 Correct 13 ms 17440 KB Output is correct
11 Correct 11 ms 17236 KB Output is correct
12 Correct 11 ms 17100 KB Output is correct
13 Correct 11 ms 17196 KB Output is correct
14 Correct 14 ms 17100 KB Output is correct
15 Correct 10 ms 17100 KB Output is correct
16 Correct 13 ms 17100 KB Output is correct
17 Correct 13 ms 17160 KB Output is correct
18 Correct 9 ms 16972 KB Output is correct
19 Correct 11 ms 17108 KB Output is correct
20 Correct 10 ms 17100 KB Output is correct
21 Correct 231 ms 39196 KB Output is correct
22 Correct 94 ms 28004 KB Output is correct
23 Correct 228 ms 37796 KB Output is correct
24 Correct 133 ms 31784 KB Output is correct
25 Correct 1129 ms 90404 KB Output is correct
26 Correct 976 ms 79740 KB Output is correct
27 Correct 395 ms 64076 KB Output is correct
28 Correct 587 ms 59304 KB Output is correct
29 Correct 581 ms 59332 KB Output is correct
30 Correct 380 ms 53684 KB Output is correct
31 Correct 189 ms 38092 KB Output is correct
32 Correct 160 ms 33992 KB Output is correct
33 Correct 177 ms 34240 KB Output is correct
34 Correct 470 ms 55400 KB Output is correct
35 Correct 372 ms 46444 KB Output is correct
36 Correct 365 ms 52764 KB Output is correct
37 Correct 472 ms 56852 KB Output is correct
38 Correct 390 ms 63620 KB Output is correct
39 Correct 216 ms 38676 KB Output is correct
40 Correct 553 ms 59276 KB Output is correct
41 Correct 587 ms 59288 KB Output is correct
42 Correct 595 ms 67288 KB Output is correct
43 Correct 365 ms 41208 KB Output is correct
44 Correct 562 ms 49764 KB Output is correct
45 Correct 451 ms 53684 KB Output is correct
46 Correct 394 ms 53956 KB Output is correct
47 Correct 382 ms 55300 KB Output is correct
48 Correct 1181 ms 90868 KB Output is correct