Submission #1037178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037178		tintingyn21	Robot (JOI21_ho_t4)	C++14	0 / 100	186 ms	65740 KiB

Main

#include <bits/stdc++.h>
#define ull unsigned long long
#define db double
#define fi first
#define se second
#define PB push_back
#define EB emplace_back
#define ll long long
                                 #define int long long    // consider carefully
#define pii pair<int, int>
#define pli pair<ll, int>
//                                  TIME IS LIMITED ...
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pii>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define  rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, b, a) for (int i = (b); i >= (a); --i)
#define repv(v, H) for(auto &v: H)
#define FOR rep
#define FORD repd
//                                          REFLECT ON THE PAST ...
#define FORV(v, H) for(auto &v: H)
#define reset(c, x) memset(c, x, sizeof(c))
#define FULL(i) (1LL << (i))
#define BIT(mask, i) ((mask >> i) & 1)
#define ONBIT(mask, i) (mask  (1LL << (i)))
#define OFFBIT(mask, i) (mask &~ (1LL << (i)))
#define REV(mask, i) (mask ^ (1LL << (i)))
#define COUNTBIT __builtin_popcountll
#define lwb lower_bound
#define upb upper_bound
#define ALL(v) v.begin(), v.end()
#define SE(v) ((int) v.size())
#define special(v) v.erase(unique(ALL(v)), v.end())
#define sp ' '
#define nl '\n'
#define yes "YES"
#define no "NO"
#define Lg2(n) (63 - __builtin_clzll(n))
#define left __left
#define right __right
#define lef(id) (id << 1)
#define rig(id) ((id << 1) | 1)

using namespace std;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

//template <class... T>
//void print(T&&... n) {
//    using exp = int[];
//    exp{0, (cerr << n << sp, 0)...};
//    cerr << endl;
//}

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

const long long oo = 1e18 + 7;
const int INF      = INT_MAX;
const int MAX      = 1e5 + 7;
const int MOD      = 1e9 + 7;
const int MAXV     = 1e6 + 7;
const int base     = 311;


/****************************/

// 3, 2, 1, STARTTT, CODEE !!


int N, M;

struct Edge {

    int u, v, c, w;
} ee[MAX << 1];

struct Data {
    int x1, x2, x3, x4;

    Data(int _x1 = 0, int _x2 = 0, int _x3 = 0, int _x4 = 0) : x1(_x1), x2(_x2), x3(_x3), x4(_x4) {}

    bool operator < (const Data &ot) const {
        return x2 <= ot.x2;
    }

};
vector<Data> G[MAX];

namespace subtask1 {

    static const int MAX = 1e3 + 10;

    ll d[MAX][2][MAX << 1];

    struct panda {
        ll dd;
        int v, t, id;

        panda(ll _dd = 0, int _v = 0, int _t = 0, int _id = 0) :
        dd(_dd), v(_v), t(_t), id(_id) {}

        bool operator < (const panda &ot) const {
            return dd > ot.dd;
        }
    };

    void SOLVE() {

        vector<vector<ll>> sum(N + 5, vector<ll>(M + 5, 0));

        rep(u, 1, N) {
            repv(e, G[u]) {
                int v = e.x1;
                int c = e.x2;
                int w = e.x3;
                int id = e.x4;

                sum[u][c] += w;
            }
        }

        priority_queue<panda> pq;

        rep(i, 1, N) {
            rep(j, 0, M) rep(t, 0, 1) d[i][t][j] = oo;
        }

        d[1][0][0] = 0;
        pq.push(panda(0, 1, 0, 0));

        while(!pq.empty()) {
            auto cur = pq.top();
            pq.pop();
            ll du = cur.dd;
            int u = cur.v;
            int t = cur.t;
            int id = cur.id;
            if(du != d[u][t][id]) continue;

            int prew = ee[id].w;
            int c = ee[id].c;

            repv(e, G[u]) {
                int v = e.x1;
                int c2 = e.x2;
                int w = e.x3;
                int id2 = e.x4;
                if(id2 == id) continue;

//                print(v, c2, w, id2);

                bool ok = sum[u][c] > 0;
                if(ok) sum[u][c] -= prew * t;

                ll new_w = min((ll) w, sum[u][c2] - w);
                int t2 = w <= sum[u][c2] ? 1 : 0;

                if(d[v][t2][id2] > du + new_w) {
                    d[v][t2][id2] = du + new_w;
                    pq.push(panda(du + new_w, v, t2, id2));
                }

                if(ok) sum[u][c] += prew * t;
            }
        }


        ll ans = oo;
        rep(j, 1, M) rep(t, 0, 1) {
            minimize(ans, d[N][t][j]);
        }

        cout << (ans == oo ? -1 : ans) << nl;

    }

}

namespace subtask2 {

//    static const int MAX = 1e3 + 10;


    map<int, ll> d[MAX][2];
    map<int, ll> sum[MAX];

    struct panda {
        ll dd;
        int v, t, id;

        panda(ll _dd = 0, int _v = 0, int _t = 0, int _id = 0) :
        dd(_dd), v(_v), t(_t), id(_id) {}

        bool operator < (const panda &ot) const {
            return dd > ot.dd;
        }
    };

    void SOLVE() {

        rep(u, 1, N) {
            repv(e, G[u]) {
                int v = e.x1;
                int c = e.x2;
                int w = e.x3;
                int id = e.x4;

                sum[u][c] += w;
            }
        }

        priority_queue<panda> pq;

        d[1][0][0] = 0;
        pq.push(panda(0, 1, 0, 0));

        while(!pq.empty()) {
            auto cur = pq.top();
            pq.pop();
            ll du = cur.dd;
            int u = cur.v;
            int t = cur.t;
            int id = cur.id;
            if(du != d[u][t][id]) continue;

            int prew = ee[id].w;
            int c = ee[id].c;

            repv(e, G[u]) {
                int v = e.x1;
                int c2 = e.x2;
                int w = e.x3;
                int id2 = e.x4;
                if(id2 == id) continue;

//                print(v, c2, w, id2);

                bool ok = sum[u].count(c) > 0;
                if(ok) sum[u][c] -= prew * t;

                ll new_w = min((ll) w, sum[u][c2] - w);
                int t2 = w <= sum[u][c2] ? 1 : 0;

                if(d[v][t2].count(id2) == 0 || d[v][t2][id2] > du + new_w) {
                    d[v][t2][id2] = du + new_w;
                    pq.push(panda(du + new_w, v, t2, id2));
                }

                if(ok) sum[u][c] += prew * t;
            }
        }


        ll ans = oo;
        rep(t, 0, 1) {
            repv(pa, d[N][t]) {
                minimize(ans, pa.se);
            }
        }

        cout << (ans == oo ? -1 : ans) << nl;

    }

}

namespace subtask3 {


    void SOLVE() {
        vll sum(N + 5, 0);

        vector<vector<pair<ll, int>>> G2(N + 2 * M + 10, vector<pair<ll, int>>());

        int dem = N;

        rep(u, 1, N) {
            repv(e, G[u]) {
                int c = e.x2;
                int w = e.x3;
                sum[c] += w;
            }
            sort(ALL(G[u]));

            int last = 0;
            repv(e, G[u]) {
                int v = e.x1;
                int c = e.x2;
                int w = e.x3;
                if(c != last) {
                    last = c;
                    ++dem;
                    G2[u].emplace_back(0, dem);
                }
                G2[v].emplace_back(sum[c] - w, dem);
                G2[dem].emplace_back(sum[c] - w, v);

                G2[u].emplace_back(w, v);
                G2[v].emplace_back(w, u);
            }

            repv(e, G[u]) {
                int c = e.x2;
                int w = e.x3;
                sum[c] -= w;
            }
        }

        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

        vll d(dem + 5, oo);
        d[1] = 0;
        pq.emplace(0, 1);

        while(!pq.empty()) {
            auto cur = pq.top();
            pq.pop();
            int u = cur.se;
            ll du = cur.fi;
            if(d[u] != du) continue;
            repv(e, G2[u]) {
                int v = e.se;
                ll w = e.fi;
                if(minimize(d[v], d[u] + w)) {
                    pq.emplace(d[v], v);
                }
            }
        }

        ll ans = d[N];

        cout << (ans == oo ? -1 : ans) << nl;

    }

}

void roxie() {

    cin >> N >> M;

    rep(i, 1, M) {
        int u, v, c, w;
        cin >> u >> v >> c >> w;
        ee[i] = {u, v, c, w};
        G[u].push_back(Data(v, c, w, i));
        G[v].push_back(Data(u, c, w, i));
    }

    if(N <= 1000 && M <= 2000)
        subtask1:: SOLVE();
    else
        subtask2:: SOLVE();

}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string task = "robot1";

    if(fopen((task + ".inp").c_str(), "r")) {
        freopen((task + ".inp").c_str(), "r", stdin);
        freopen((task + ".out").c_str(), "w", stdout);
    }

    int test = 1;
    // cin >> test;

    while(test--) {

        roxie();

    }


    cerr << nl << "run in: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s" << nl << nl;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void subtask1::SOLVE()':
Main.cpp:127:21: warning: unused variable 'v' [-Wunused-variable]
  127 |                 int v = e.x1;
      |                     ^
Main.cpp:130:21: warning: unused variable 'id' [-Wunused-variable]
  130 |                 int id = e.x4;
      |                     ^~
Main.cpp: In function 'void subtask2::SOLVE()':
Main.cpp:217:21: warning: unused variable 'v' [-Wunused-variable]
  217 |                 int v = e.x1;
      |                     ^
Main.cpp:220:21: warning: unused variable 'id' [-Wunused-variable]
  220 |                 int id = e.x4;
      |                     ^~
Main.cpp: In function 'int main()':
Main.cpp:379:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  379 |         freopen((task + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:380:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  380 |         freopen((task + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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