Submission #985364

#	Time	Username	Problem	Language	Result	Execution time	Memory
985364		underwaterkillerwhale	Robot (JOI21_ho_t4)	C++17	34 / 100	3037 ms	62776 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e18;
const int BASE = 1337;

struct toData {
    ll v, C, P, eid;
};
struct DataE {
    ll u, v, C, P;
};
int n, m;
vector<ll> dp[N];
DataE Edge[N];
vector<toData> ke[N];
int color[N];
ll costcol[N];

void solution () {
    cin >> n >> m;
    rep (i, 1, n) ke[i].push_back({0, 0, 0, -1});
    rep (i, 1, m) {
        ll u, v, C, P;
        cin >> u >> v >> C >> P;
        Edge[i] = {u, v, C, P};
        ke[u].push_back({v, C, P, i});
        ke[v].push_back({u, C, P, i});
        color[i] = C;
    }
    if (m == 1) {
        bool ok = 0;
        rep (i, 1, m) {
            if (Edge[i].u == 1 && Edge[i].v == n) ok = 1;
        }
        if (ok) cout << 0 <<"\n";
        else cout << -1 <<"\n";
        return;
    }
    rep (i, 1, n) {
        sort (ALL(ke[i]), [] (toData A, toData B) {return A.eid < B.eid; });
        dp[i].resize(SZ(ke[i]));
    }
    struct Data {
        ll u, eid, w;
    };
    struct cmp {
        bool operator () (Data A, Data B) { return A.w > B.w; }
    };

    rep (i, 1, n) {
        dp[i][0] = INF;
        rep (j, 0, SZ(ke[i]) - 1) dp[i][j] = INF;
    }

    priority_queue<Data, vector<Data>, cmp> pq;
    pq.push({1, 0, 0});
    dp[1][0] = 0;
    while (!pq.empty()) {
        ll u = pq.top().u, ueid = pq.top().eid;
        int uueid = ke[u][ueid].eid;
//        cout << u <<" "<<ueid <<" "<<dp[u][ueid] <<"\n";
        pq.pop();
        if (u == n) break;
        static set<int> curcol;
        iter (&id, curcol) costcol[id] = 0;
        curcol.clear();

        iter (&id, ke[u]) {
            curcol.insert(id.C);
            costcol[id.C] += id.P;
        }
        rep (i, 1, SZ(ke[u]) - 1) {
            toData &id = ke[u][i];
            ll v = id.v, C = id.C, p = id.P, toid = id.eid;
            int vtoid; {
                int lf = 1, rt = SZ(ke[v]) - 1;
                while (lf < rt) {
                    int mid = lf + rt >> 1;
                    if (ke[v][mid].eid >= toid) rt = mid;
                    else lf = mid + 1;
                }
//                cout << v <<" "<<SZ(ke[v]) <<"\n";
//                assert(lf <= SZ(ke[v]) - 1);
                vtoid = lf;
            }
            if (dp[v][0] > dp[u][ueid] + costcol[id.C] - id.P - (id.C == color[uueid]) * Edge[uueid].P) {
                dp[v][0] = dp[u][ueid] + costcol[id.C] - id.P - (id.C == color[uueid]) * Edge[uueid].P;
                pq.push({v, 0, dp[v][0]});
            }
            if (SZ(curcol) < m) {
                if (dp[v][vtoid] > dp[u][ueid] + id.P) {
                    dp[v][vtoid] = dp[u][ueid] + id.P;
                    pq.push({v, vtoid, dp[v][vtoid]});
                }
            }
        }
    }
    ll res = INF;
    rep (i, 0, SZ(ke[n]) - 1) res = min(res, dp[n][i]);
    if (res != INF) cout << res <<"\n";
    else cout << -1 <<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13

*/

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:98:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |                     int mid = lf + rt >> 1;
      |                               ~~~^~~~
Main.cpp:94:26: warning: unused variable 'C' [-Wunused-variable]
   94 |             ll v = id.v, C = id.C, p = id.P, toid = id.eid;
      |                          ^
Main.cpp:94:36: warning: unused variable 'p' [-Wunused-variable]
   94 |             ll v = id.v, C = id.C, p = id.P, toid = id.eid;
      |                                    ^

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42