oj.uz

답안 #707307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707307 2023-03-08T18:22:37 Z Stickfish Robot (JOI21_ho_t4) C++17
100 / 100
 999 ms 177236 KB 
#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.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47224 KB Output is correct
3 Correct 24 ms 47248 KB Output is correct
4 Correct 24 ms 47288 KB Output is correct
5 Correct 25 ms 47316 KB Output is correct
6 Correct 26 ms 47184 KB Output is correct
7 Correct 32 ms 47700 KB Output is correct
8 Correct 24 ms 47404 KB Output is correct
9 Correct 27 ms 48340 KB Output is correct
10 Correct 27 ms 48260 KB Output is correct
11 Correct 27 ms 48156 KB Output is correct
12 Correct 29 ms 48024 KB Output is correct
13 Correct 28 ms 48184 KB Output is correct
14 Correct 32 ms 48076 KB Output is correct
15 Correct 27 ms 47776 KB Output is correct
16 Correct 28 ms 48068 KB Output is correct
17 Correct 26 ms 48092 KB Output is correct
18 Correct 23 ms 47592 KB Output is correct
19 Correct 29 ms 47956 KB Output is correct
20 Correct 30 ms 47908 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 84964 KB Output is correct
2 Correct 127 ms 64972 KB Output is correct
3 Correct 446 ms 100828 KB Output is correct
4 Correct 183 ms 72616 KB Output is correct
5 Correct 814 ms 155540 KB Output is correct
6 Correct 693 ms 145840 KB Output is correct
7 Correct 560 ms 138228 KB Output is correct
8 Correct 595 ms 124360 KB Output is correct
9 Correct 598 ms 124336 KB Output is correct
10 Correct 431 ms 105996 KB Output is correct
11 Correct 220 ms 92276 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47224 KB Output is correct
3 Correct 24 ms 47248 KB Output is correct
4 Correct 24 ms 47288 KB Output is correct
5 Correct 25 ms 47316 KB Output is correct
6 Correct 26 ms 47184 KB Output is correct
7 Correct 32 ms 47700 KB Output is correct
8 Correct 24 ms 47404 KB Output is correct
9 Correct 27 ms 48340 KB Output is correct
10 Correct 27 ms 48260 KB Output is correct
11 Correct 27 ms 48156 KB Output is correct
12 Correct 29 ms 48024 KB Output is correct
13 Correct 28 ms 48184 KB Output is correct
14 Correct 32 ms 48076 KB Output is correct
15 Correct 27 ms 47776 KB Output is correct
16 Correct 28 ms 48068 KB Output is correct
17 Correct 26 ms 48092 KB Output is correct
18 Correct 23 ms 47592 KB Output is correct
19 Correct 29 ms 47956 KB Output is correct
20 Correct 30 ms 47908 KB Output is correct
21 Correct 298 ms 84964 KB Output is correct
22 Correct 127 ms 64972 KB Output is correct
23 Correct 446 ms 100828 KB Output is correct
24 Correct 183 ms 72616 KB Output is correct
25 Correct 814 ms 155540 KB Output is correct
26 Correct 693 ms 145840 KB Output is correct
27 Correct 560 ms 138228 KB Output is correct
28 Correct 595 ms 124360 KB Output is correct
29 Correct 598 ms 124336 KB Output is correct
30 Correct 431 ms 105996 KB Output is correct
31 Correct 220 ms 92276 KB Output is correct
32 Correct 483 ms 107312 KB Output is correct
33 Correct 433 ms 95372 KB Output is correct
34 Correct 696 ms 120356 KB Output is correct
35 Correct 522 ms 105848 KB Output is correct
36 Correct 511 ms 120608 KB Output is correct
37 Correct 539 ms 130992 KB Output is correct
38 Correct 451 ms 140500 KB Output is correct
39 Correct 391 ms 104312 KB Output is correct
40 Correct 608 ms 130912 KB Output is correct
41 Correct 665 ms 133292 KB Output is correct
42 Correct 855 ms 139204 KB Output is correct
43 Correct 323 ms 93444 KB Output is correct
44 Correct 768 ms 121124 KB Output is correct
45 Correct 461 ms 117656 KB Output is correct
46 Correct 389 ms 107868 KB Output is correct
47 Correct 487 ms 130964 KB Output is correct
48 Correct 999 ms 177236 KB Output is correct