oj.uz

Submission #597410

# Submission time Handle Problem Language Result Execution time Memory
597410 2022-07-16T01:09:10 Z ljuba Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 456 ms 37348 KB 
#include <bits/stdc++.h>
#include <queue>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
typedef vector<vi> vvi;
typedef vector<vll> vvll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
 
namespace debug {
    void __print(int x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
 
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef ljuba
#define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
}
 
using namespace debug;
 
const char nl = '\n';
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
/*
“If you win, you live. If you lose, you die. If you don’t fight, you can’t win!”
― Eren Yaeger
*/
 
const ll INF = 1e18 + 12;
 
vector<array<int, 3>> nadjiSpecijalne(int n, int s, int t, const vector<array<int, 3>> &edges) {
    vector<vpll> adj(n);
    vll dist(n, INF);
 
    vvpii sa(n);
 
    for(auto &z : edges) {
        adj[z[0]].pb({z[1], z[2]});
        adj[z[1]].pb({z[0], z[2]});
    }
 
    priority_queue<pll, vpll, greater<>> pq;
    pq.push({0, s});
    dist[s] = 0;
 
    while(!pq.empty()) {
        auto tren = pq.top();
        pq.pop();
 
        if(dist[tren.se] != tren.fi) continue;

        //dbg(tren.se, dist[tren.se]);
 
        for(auto e : adj[tren.se]) {
            if(ckmin(dist[e.fi], dist[tren.se] + e.se)) {
                pq.push({dist[e.fi], e.fi});
                sa[e.fi].clear();
                sa[e.fi].pb({tren.se, e.se});
            } else if(dist[e.fi] == dist[tren.se] + e.se) {
                sa[e.fi].pb({tren.se, e.se});
            }
        }
    }

    //dbg(sa);
 
    vector<array<int, 3>> ans;
 
    set<int> trenutne;
    trenutne.insert(t);
 
    vector<bool> posetio(n, false);
 
    while(sz(trenutne)) {
        int tren = *trenutne.begin();
        //dbg(tren);
        trenutne.erase(tren);
        posetio[tren] = true;
 
        for(auto e : sa[tren]) {
            ans.pb({e.fi, tren, e.se});
            if(!posetio[e.fi]) {
                trenutne.insert(e.fi);
            }
        }
    }
 
    return ans;
}
 
ll dijkstra(int n, int s, int t, const vector<array<int, 3>> &edges) {
    vvpii adj(n);
    vll dist(n, INF);
 
    for(auto &z : edges) {
        adj[z[0]].pb({z[1], z[2]});
    }
 
    priority_queue<pll, vpll, greater<>> pq;
    pq.push({0, s});
    dist[s] = 0;
 
    while(!pq.empty()) {
        auto tren = pq.top();
        pq.pop();
 
        if(dist[tren.se] != tren.fi) continue;
 
        for(auto e : adj[tren.se]) {
            if(ckmin(dist[e.fi], dist[tren.se] + e.se)) {
                pq.push({dist[e.fi], e.fi});
            }
        }
    }
 
    return dist[t];
}
 
void solve() {
    int n, m;
    cin >> n >> m;
 
    int s, t, u, v;
    cin >> s >> t >> u >> v;
    --s, --t, --u, --v;
 
    vector<array<int, 3>> edges;
 
    for(int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        edges.pb({a, b, c});
    }
 
    auto spec = nadjiSpecijalne(n, s, t, edges);

    for(auto z : spec) {
        //dbg(z[0] + 1, z[1] + 1, z[2]);
    }
 
    auto ostale = spec;
    ostale.clear();
 
    {
        set<array<int, 3>> gas;
        for(auto z : spec) {
            gas.insert(z);
            gas.insert({z[1], z[0], z[2]});
        }
 
        for(auto z : edges) {
            if(gas.count(z)) continue;
            ostale.pb(z);
        }
    }
 
    auto sveee = edges;
    for(auto z : edges) {
        sveee.pb({z[1], z[0], z[2]});
    }
 
    vector<array<int, 3>> qwer;
    qwer = sveee;
 
    for(auto z : spec) {
        qwer.pb({z[0], z[1], 0});
        // qwer.pb({z[1], z[0], z[2]});
    }
 
    ll ans = dijkstra(n, u, v, qwer);
    //ckmin(ans, dijkstra(n, v, u, qwer));
 
    qwer = sveee;
 
    for(auto z : spec) {
        // qwer.pb({z[0], z[1], z[2]});
        qwer.pb({z[1], z[0], 0});
    }
 
    ckmin(ans, dijkstra(n, u, v, qwer));
    //ckmin(ans, dijkstra(n, v, u, qwer));
 
    cout << ans << nl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int testCases = 1;
    //cin >> testCases;
    while(testCases--)
        solve();
}

Compilation message

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:180:14: warning: variable 'z' set but not used [-Wunused-but-set-variable]
  180 |     for(auto z : spec) {
      |              ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 34824 KB Output is correct
2 Correct 374 ms 36848 KB Output is correct
3 Correct 438 ms 35300 KB Output is correct
4 Correct 295 ms 36324 KB Output is correct
5 Correct 445 ms 31740 KB Output is correct
6 Correct 298 ms 34248 KB Output is correct
7 Correct 439 ms 35980 KB Output is correct
8 Correct 420 ms 32948 KB Output is correct
9 Correct 312 ms 35780 KB Output is correct
10 Correct 267 ms 35876 KB Output is correct
11 Correct 208 ms 19008 KB Output is correct
12 Correct 316 ms 36008 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 34016 KB Output is correct
2 Correct 377 ms 36548 KB Output is correct
3 Correct 385 ms 36380 KB Output is correct
4 Correct 391 ms 36424 KB Output is correct
5 Correct 420 ms 34404 KB Output is correct
6 Correct 426 ms 34608 KB Output is correct
7 Correct 456 ms 37348 KB Output is correct
8 Correct 392 ms 36176 KB Output is correct
9 Correct 402 ms 36676 KB Output is correct
10 Correct 385 ms 36312 KB Output is correct
11 Correct 232 ms 20036 KB Output is correct
12 Correct 428 ms 34520 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3896 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 18 ms 6152 KB Output is correct
5 Correct 10 ms 3408 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Incorrect 2 ms 724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 34824 KB Output is correct
2 Correct 374 ms 36848 KB Output is correct
3 Correct 438 ms 35300 KB Output is correct
4 Correct 295 ms 36324 KB Output is correct
5 Correct 445 ms 31740 KB Output is correct
6 Correct 298 ms 34248 KB Output is correct
7 Correct 439 ms 35980 KB Output is correct
8 Correct 420 ms 32948 KB Output is correct
9 Correct 312 ms 35780 KB Output is correct
10 Correct 267 ms 35876 KB Output is correct
11 Correct 208 ms 19008 KB Output is correct
12 Correct 316 ms 36008 KB Output is correct
13 Correct 377 ms 34016 KB Output is correct
14 Correct 377 ms 36548 KB Output is correct
15 Correct 385 ms 36380 KB Output is correct
16 Correct 391 ms 36424 KB Output is correct
17 Correct 420 ms 34404 KB Output is correct
18 Correct 426 ms 34608 KB Output is correct
19 Correct 456 ms 37348 KB Output is correct
20 Correct 392 ms 36176 KB Output is correct
21 Correct 402 ms 36676 KB Output is correct
22 Correct 385 ms 36312 KB Output is correct
23 Correct 232 ms 20036 KB Output is correct
24 Correct 428 ms 34520 KB Output is correct
25 Correct 17 ms 3896 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 18 ms 6152 KB Output is correct
29 Correct 10 ms 3408 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Incorrect 2 ms 724 KB Output isn't correct
32 Halted 0 ms 0 KB -