oj.uz

답안 #422421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422421 2021-06-10T06:16:41 Z jlallas384 Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 499 ms 22052 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float 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 char *x) {cerr << '\"' << x << '\"';}
void __print(const string &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 &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

int main(){
    int n,m,s,t,u,v;
    cin >> n >> m >> s >> t >> u >> v,s--,t--,u--,v--;
    vector<vector<int>> g(n);
    vector<tuple<int,int,int>> e;
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c,a--,b--;
        g[a].push_back(i);
        g[b].push_back(i);
        e.emplace_back(a,b,c);
    }
    auto f = [&](int i,int x){
        return x ^ get<0>(e[i]) ^ get<1>(e[i]);
    };
    vector<ll> dist(n,1e17);
    vector<vector<int>> par(n);
    priority_queue<pair<ll,int>> pq;
    dist[s] = 0;
    pq.emplace(0,s);
    while(pq.size()){
        auto [dst,cur] = pq.top(); pq.pop();
        if(-dst > dist[cur]) continue;
        for(int id: g[cur]){
            int nxt = f(id,cur);
            ll nw = dist[cur] + get<2>(e[id]);
            if(nw < dist[nxt]){
                dist[nxt] = nw;
                pq.emplace(-nw,nxt);
                par[nxt].clear();
                par[nxt].push_back(id);
            }else if(nw == dist[nxt]){
                par[nxt].push_back(id);
            }
        }
    }
    stack<int> stk;
    stk.push(t);
    vector<int> vis(n);
    while(stk.size()){
        int cur = stk.top(); stk.pop();
        for(int id: par[cur]){
            get<2>(e[id]) = 0;
            if(!vis[f(id,cur)]){
                stk.push(f(id,cur));
                vis[f(id,cur)] = 1;
            }
        }
    }
    dist = vector<ll>(n,1e17);
    dist[u] = 0;
    pq.emplace(0,u);
    while(pq.size()){
        auto [dst,cur] = pq.top(); pq.pop();
        if(-dst > dist[cur]) continue;
        for(int id: g[cur]){
            int nxt = f(id,cur);
            ll nw = dist[cur] + get<2>(e[id]);
            if(nw < dist[nxt]){
                dist[nxt] = nw;
                pq.emplace(-nw,nxt);
            }
        }
    }
    cout << dist[v];
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 412 ms 21332 KB Output is correct
2 Correct 422 ms 20620 KB Output is correct
3 Correct 410 ms 20848 KB Output is correct
4 Correct 499 ms 21064 KB Output is correct
5 Correct 452 ms 20304 KB Output is correct
6 Correct 487 ms 21596 KB Output is correct
7 Correct 452 ms 20532 KB Output is correct
8 Correct 414 ms 20512 KB Output is correct
9 Correct 437 ms 21312 KB Output is correct
10 Correct 435 ms 21336 KB Output is correct
11 Correct 204 ms 16348 KB Output is correct
12 Correct 469 ms 21188 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 21944 KB Output is correct
2 Correct 427 ms 20596 KB Output is correct
3 Correct 453 ms 21940 KB Output is correct
4 Correct 419 ms 20468 KB Output is correct
5 Correct 464 ms 21612 KB Output is correct
6 Correct 414 ms 20740 KB Output is correct
7 Correct 426 ms 22052 KB Output is correct
8 Correct 436 ms 20660 KB Output is correct
9 Correct 427 ms 21648 KB Output is correct
10 Correct 415 ms 20708 KB Output is correct
11 Correct 216 ms 16376 KB Output is correct
12 Correct 402 ms 20800 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1356 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 412 ms 21332 KB Output is correct
2 Correct 422 ms 20620 KB Output is correct
3 Correct 410 ms 20848 KB Output is correct
4 Correct 499 ms 21064 KB Output is correct
5 Correct 452 ms 20304 KB Output is correct
6 Correct 487 ms 21596 KB Output is correct
7 Correct 452 ms 20532 KB Output is correct
8 Correct 414 ms 20512 KB Output is correct
9 Correct 437 ms 21312 KB Output is correct
10 Correct 435 ms 21336 KB Output is correct
11 Correct 204 ms 16348 KB Output is correct
12 Correct 469 ms 21188 KB Output is correct
13 Correct 483 ms 21944 KB Output is correct
14 Correct 427 ms 20596 KB Output is correct
15 Correct 453 ms 21940 KB Output is correct
16 Correct 419 ms 20468 KB Output is correct
17 Correct 464 ms 21612 KB Output is correct
18 Correct 414 ms 20740 KB Output is correct
19 Correct 426 ms 22052 KB Output is correct
20 Correct 436 ms 20660 KB Output is correct
21 Correct 427 ms 21648 KB Output is correct
22 Correct 415 ms 20708 KB Output is correct
23 Correct 216 ms 16376 KB Output is correct
24 Correct 402 ms 20800 KB Output is correct
25 Correct 24 ms 1356 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Incorrect 1 ms 332 KB Output isn't correct
28 Halted 0 ms 0 KB -