Submission #707307

#	Time	Username	Problem	Language	Result	Execution time	Memory
707307		Stickfish	Robot (JOI21_ho_t4)	C++17	100 / 100	999 ms	177236 KiB

Main

#include <iostream>
#include <algorithm>
#include <cassert>
#include <bitset>
#include <set>
#include <map>
#include <vector>
using namespace std;
using ll = long long;

const int MAXN = 1e6 + 123;
const ll INF = 1e18 + 177013;
vector<pair<int, ll>> edg[MAXN];
vector<pair<int, pair<int, int>>> edg_init[MAXN];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<pair<int, int>, pair<int, int>>> edges;
    for (int i = 0; i < m; ++i) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        --a, --b;
        edges.push_back({{c, p}, {a, b}});
        edg_init[a].push_back({c, {b, p}});
        edg_init[b].push_back({c, {a, p}});
    }
    int sz = 0;
    vector<int> tin(n);
    vector<int> tin_cl(n);
    vector<vector<int>> clrs(n);
    vector<vector<ll>> clrssm(n);
    vector<vector<ll>> clrsmx(n);
    for (int v = 0; v < n; ++v) {
        sort(edg_init[v].begin(), edg_init[v].end());
        tin[v] = sz;
        tin_cl[v] = tin[v] + edg_init[v].size() + 1;
        for (auto e : edg_init[v]) {
            clrs[v].push_back(e.first);
        }
        clrs[v].resize(unique(clrs[v].begin(), clrs[v].end()) - clrs[v].begin());
        clrssm[v].resize(clrs[v].size());
        clrsmx[v].resize(clrs[v].size());
        for (auto [c, e] : edg_init[v]) {
            int ci = lower_bound(clrs[v].begin(), clrs[v].end(), c) - clrs[v].begin();
            clrssm[v][ci] += e.second;
            clrsmx[v][ci] = max(clrsmx[v][ci], 1ll * e.second);
        }
        sz += edg_init[v].size() + clrs[v].size() + 1;
        for (int i = tin[v] + 1; i < sz; ++i) {
            edg[i].push_back({tin[v], 0});
        }
        for (size_t i = 0; i < clrs[v].size(); ++i) {
            clrsmx[v][i] = min(clrsmx[v][i], clrssm[v][i] - clrsmx[v][i]);
            //if (clrsmx[v][i] == clrssm[v][i])
                //clrsmx[v][i] = 0;
            edg[tin[v]].push_back({tin_cl[v] + i, clrsmx[v][i]});
        }
    }
    //vector<map<int, int>> smp(n);
    //vector<map<int, int>> mxp(n);
    for (int v = 0; v < n; ++v) {
        int cv = 0;
        vector<pair<int, pair<int, int>>> imag_edges;
        for (size_t evu = 0; evu < edg_init[v].size(); ++evu) {
            auto [c, e] = edg_init[v][evu];
            while (clrs[v][cv] < c)
                ++cv;
            auto [u, p] = e;
            int euv = lower_bound(edg_init[u].begin(), edg_init[u].end(), pair<int, pair<int, int>>(c, {v, p})) - edg_init[u].begin();
            edg[tin[v]].push_back({tin[u] + euv + 1, p});
            if (p > clrsmx[v][cv]) {
                imag_edges.push_back({tin[v] + int(evu) + 1, {tin_cl[v] + cv, clrsmx[v][cv] - p}});
            } else {
                edg[tin[v] + evu + 1].push_back({tin_cl[v] + cv, clrsmx[v][cv] - p});
            }
            edg[tin_cl[v] + cv].push_back({tin[u], clrssm[v][cv] - p - clrsmx[v][cv]});
            //assert(clrssm[v][cv] - p - clrsmx[v][cv] >= 0);
        }
        for (auto [nv, e] : imag_edges) {
            auto [u, w] = e;
            cv = lower_bound(clrs[v].begin(), clrs[v].end(), edg_init[v][nv - 1 - tin[v]].first) - clrs[v].begin();
            for (auto [nu, nw] : edg[u]) {
                //cout << nv << ' ' << nu << " -> " << w + nw << "(" << clrssm[v][cv] << ' ' << clrsmx[v][cv] << ' ' << edg_init[v][nv - 1 - tin[v]].second.second << ") {" << w << ' ' << nw << "} " << endl;
                edg[nv].push_back({nu, max(0ll, w + nw)});
            }
        }
    }
    //if (n == 100000 && m == 200000) {
        //return 0;
    //}
    //bitset<MAXN> used;
    vector<ll> dist(sz, INF);
    dist[0] = 0;
    set<pair<ll, int>> rdist;
    rdist.insert({0, 0});
    while (rdist.size()) {
        int v = rdist.begin()->second;
        rdist.erase(rdist.begin());
        //if (used[v])
            //continue;
        //used[v] = 1;
        for (auto [u, w] : edg[v]) {
            if (dist[u] > dist[v] + w) {
                rdist.erase({dist[u], u});
                dist[u] = min(dist[u], dist[v] + w);
                rdist.insert({dist[u], u});
            }
        }
    }
    //for (int v = 0; v < n; ++v)
        //cout << tin[v] << ' ';
    //cout << endl;
    //cout << "---" << endl;
    //for (int v = 0; v < sz; ++v) {
        //cout << v << ": ";
        //for (auto [u, w] : edg[v])
            //cout << u << ' ';
        //cout << endl;
    //}
    //for (int v = 0; v < n; ++v)
        //cout << dist[tin[v]] << ' ';
    //cout << endl;
    if (dist[tin[n - 1]] == INF) {
        cout << "-1\n";
    } else {
        cout << dist[tin[n - 1]] << '\n';
    }
}

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