oj.uz

Submission #635559

# Submission time Handle Problem Language Result Execution time Memory
635559 2022-08-26T12:54:01 Z Trent Robot (JOI21_ho_t4) C++14
100 / 100
 554 ms 113156 KB 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define open(g) string _name_ = g; freopen((_name_ + ".in").c_str(), "r", stdin); freopen((_name_ + ".out").c_str(), "w", stdout)
#define printArr(a, len) for(int asdf = 0; asdf < (len); ++asdf) cout << (a)[asdf] << ' '; cout << '\n';
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(i) i.begin(), i.end()
#define pii pair<int, int>
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define int ll

const int MN = 1e5 + 10;
const ll INF = 1e18;
struct edge{int n, c1, c2, p;};
struct node{int i, cc; ll d;}; // node, color channel (0 for none), distance
bool operator <(const node& a, const node& b){ return a.d > b.d; }
vector<edge> adj[MN];
vector<vector<edge>> ce[MN];
vector<ll> cs[MN], dis[MN];
// gp_hash_table<int, vector<edge>> ce[MN]; // colors split into channels
// gp_hash_table<int, ll> cs[MN]; // color sum of each node
// gp_hash_table<int, ll> dis[MN];
gp_hash_table<int, int> ci[MN];

signed main(){
    boost();
    int N, M; cin >> N >> M;
    REP(i, 1, N + 1) cs[i].push_back(0), dis[i].push_back(INF), ce[i].emplace_back();
    forR(i, M){
        int a, b, c, p; cin >> a >> b >> c >> p;
        if(ci[a].find(c) == ci[a].end()) ci[a][c] = ce[a].size(), cs[a].push_back(0), dis[a].push_back(INF), ce[a].emplace_back();
        if(ci[b].find(c) == ci[b].end()) ci[b][c] = ce[b].size(), cs[b].push_back(0), dis[b].push_back(INF), ce[b].emplace_back();
        adj[a].push_back({b, ci[a][c], ci[b][c], p}); adj[b].push_back({a, ci[b][c], ci[a][c], p});
    }

    REP(i, 1, N + 1){
        dis[i][0] = INF;
        for(auto [n, c1, c2, p] : adj[i]) cs[i][c1] += p, dis[i][c1] = INF, ce[i][c1].push_back({n, c1, c2, p});
    }
    priority_queue<node> dij;
    dij.push({1, 0, 0});
    dis[1][0] = 0;
    int tot = 0;
    while(!dij.empty()){
        auto [i, cc, d] = dij.top(); dij.pop();
        if(d > dis[i][cc]) continue;
        ++tot; assert(tot <= 2 * M + N);
        if(cc == 0){
            for(auto [n, c1, c2, p] : adj[i]) {
                ll oc = cs[i][c1] - p;
                if(dis[i][0] + min(oc, (ll) p) < dis[n][0]){
                    dis[n][0] = dis[i][0] + min(oc, (ll) p);
                    dij.push({n, 0, dis[n][0]});
                }
                if(c1 != 0 && dis[i][0] < dis[n][c2]){
                    dis[n][c2] = dis[i][0];
                    dij.push({n, c2, dis[n][c2]});
                }
            }
        } else {
            for(auto [n, c1, c2, p] : ce[i][cc]){
                ll cos = cs[i][cc] - p;
                if(dis[i][cc] + cos < dis[n][0]){
                    dis[n][0] = dis[i][cc] + cos;
                    dij.push({n, 0, dis[n][0]});
                }
            }
        }
    }
    cout << (dis[N][0] >= INF ? -1 : dis[N][0]) << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for(auto [n, c1, c2, p] : adj[i]) cs[i][c1] += p, dis[i][c1] = INF, ce[i][c1].push_back({n, c1, c2, p});
      |                  ^
Main.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |         auto [i, cc, d] = dij.top(); dij.pop();
      |              ^
Main.cpp:60:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |             for(auto [n, c1, c2, p] : adj[i]) {
      |                      ^
Main.cpp:72:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |             for(auto [n, c1, c2, p] : ce[i][cc]){
      |                      ^

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 40148 KB Output is correct
2 Correct 25 ms 40192 KB Output is correct
3 Correct 27 ms 40216 KB Output is correct
4 Correct 27 ms 40204 KB Output is correct
5 Correct 28 ms 40192 KB Output is correct
6 Correct 28 ms 40168 KB Output is correct
7 Correct 30 ms 40432 KB Output is correct
8 Correct 27 ms 40360 KB Output is correct
9 Correct 31 ms 40780 KB Output is correct
10 Correct 29 ms 40860 KB Output is correct
11 Correct 29 ms 40708 KB Output is correct
12 Correct 30 ms 40648 KB Output is correct
13 Correct 30 ms 40768 KB Output is correct
14 Correct 29 ms 40788 KB Output is correct
15 Correct 28 ms 40448 KB Output is correct
16 Correct 30 ms 40680 KB Output is correct
17 Correct 29 ms 40720 KB Output is correct
18 Correct 28 ms 40456 KB Output is correct
19 Correct 29 ms 40720 KB Output is correct
20 Correct 29 ms 40564 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 60828 KB Output is correct
2 Correct 99 ms 50188 KB Output is correct
3 Correct 169 ms 70192 KB Output is correct
4 Correct 139 ms 55464 KB Output is correct
5 Correct 472 ms 107784 KB Output is correct
6 Correct 461 ms 105084 KB Output is correct
7 Correct 377 ms 95624 KB Output is correct
8 Correct 459 ms 92216 KB Output is correct
9 Correct 450 ms 92232 KB Output is correct
10 Correct 330 ms 74568 KB Output is correct
11 Correct 218 ms 69300 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 40148 KB Output is correct
2 Correct 25 ms 40192 KB Output is correct
3 Correct 27 ms 40216 KB Output is correct
4 Correct 27 ms 40204 KB Output is correct
5 Correct 28 ms 40192 KB Output is correct
6 Correct 28 ms 40168 KB Output is correct
7 Correct 30 ms 40432 KB Output is correct
8 Correct 27 ms 40360 KB Output is correct
9 Correct 31 ms 40780 KB Output is correct
10 Correct 29 ms 40860 KB Output is correct
11 Correct 29 ms 40708 KB Output is correct
12 Correct 30 ms 40648 KB Output is correct
13 Correct 30 ms 40768 KB Output is correct
14 Correct 29 ms 40788 KB Output is correct
15 Correct 28 ms 40448 KB Output is correct
16 Correct 30 ms 40680 KB Output is correct
17 Correct 29 ms 40720 KB Output is correct
18 Correct 28 ms 40456 KB Output is correct
19 Correct 29 ms 40720 KB Output is correct
20 Correct 29 ms 40564 KB Output is correct
21 Correct 189 ms 60828 KB Output is correct
22 Correct 99 ms 50188 KB Output is correct
23 Correct 169 ms 70192 KB Output is correct
24 Correct 139 ms 55464 KB Output is correct
25 Correct 472 ms 107784 KB Output is correct
26 Correct 461 ms 105084 KB Output is correct
27 Correct 377 ms 95624 KB Output is correct
28 Correct 459 ms 92216 KB Output is correct
29 Correct 450 ms 92232 KB Output is correct
30 Correct 330 ms 74568 KB Output is correct
31 Correct 218 ms 69300 KB Output is correct
32 Correct 113 ms 68200 KB Output is correct
33 Correct 168 ms 67688 KB Output is correct
34 Correct 360 ms 77616 KB Output is correct
35 Correct 306 ms 72832 KB Output is correct
36 Correct 351 ms 79672 KB Output is correct
37 Correct 392 ms 87224 KB Output is correct
38 Correct 403 ms 101812 KB Output is correct
39 Correct 162 ms 77560 KB Output is correct
40 Correct 458 ms 92244 KB Output is correct
41 Correct 489 ms 92364 KB Output is correct
42 Correct 554 ms 93272 KB Output is correct
43 Correct 207 ms 67528 KB Output is correct
44 Correct 234 ms 84676 KB Output is correct
45 Correct 412 ms 82112 KB Output is correct
46 Correct 370 ms 80584 KB Output is correct
47 Correct 380 ms 83900 KB Output is correct
48 Correct 551 ms 113156 KB Output is correct