oj.uz

Submission #544206

# Submission time Handle Problem Language Result Execution time Memory
544206 2022-04-01T10:31:39 Z Cookie197 Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 286 ms 28808 KB 
// Cookie197 
// the people who invented competitive programming must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
//#define mod 998244353
#define mod 1000000007
#define endl "\n"
#define inf (ll)5e18
#define out(x) cout << #x << " = " << x <<endl;
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << "  second = " << x.second << endl

#define mt(a,b,c) mp(a,mp(b,c))
int n,m,S,T,U,V;
vector<pair<int,pii> > adj[100005]; // node, dist, id
ll dist[100005];
int discount[200005];

int vis[100005];
void dfs(int node){
    vis[node] = true;
    for (pair<int,pii> p:adj[node]){
        int u = p.first;
        ll wei = p.second.first;
        int id = p.second.second;
        if (dist[node] - wei == dist[u]) {
            discount[id] = true;
            if (!vis[u]) dfs(u);
        }
    }
}
signed main(){
    Why_does_competitive_programming_even_exist;
    cin>>n>>m>>S>>T>>U>>V;
    for (int i=1;i<=m;i++){
        int a,b; ll c; cin>>a>>b>>c;
        c *= 1000000;
        adj[a].push_back(mt(b,c,i));
        adj[b].push_back(mt(a,c,i));
    }

    for (int i=1;i<=n;i++) dist[i] = -1;
    priority_queue<pii,vector<pii>, greater<pii> > pq;
    pq.push(mp(0,S));
    while(pq.size()){
        int node = pq.top().second;
        ll d = pq.top().first;
        pq.pop();
        if (dist[node] != -1) continue;
        dist[node] = d;
        for (pair<int,pii> p:adj[node]){
            int u = p.first;
            ll wei = p.second.first;
            int id = p.second.second;
            pq.push(mp(wei+d, u));
        }
    }

    //for (int i=1;i<=n;i++) out2(dist,i);
    //return 0;

    dfs(T);

    for (int i=1;i<=n;i++) dist[i] = -1;
    pq.push(mp(0,U));
    while(pq.size()){
        int node = pq.top().second;
        ll d = pq.top().first;
        pq.pop();
        if (dist[node] != -1) continue;
        dist[node] = d;
        for (pair<int,pii> p:adj[node]){
            int u = p.first;
            ll wei = p.second.first;
            int id = p.second.second;
            if (discount[id]) wei = 1;
            if (dist[u] != -1) continue;
            pq.push(mp(wei+d, u));
        }
    }
    
    cout<<dist[V]/1000000<<endl;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:76:17: warning: unused variable 'id' [-Wunused-variable]
   76 |             int id = p.second.second;
      |                 ^~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 26056 KB Output is correct
2 Correct 239 ms 25808 KB Output is correct
3 Correct 242 ms 28808 KB Output is correct
4 Correct 247 ms 25976 KB Output is correct
5 Correct 242 ms 24280 KB Output is correct
6 Correct 244 ms 25956 KB Output is correct
7 Correct 258 ms 25812 KB Output is correct
8 Correct 248 ms 25736 KB Output is correct
9 Correct 252 ms 26688 KB Output is correct
10 Correct 250 ms 26708 KB Output is correct
11 Correct 83 ms 15388 KB Output is correct
12 Correct 245 ms 26464 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 26872 KB Output is correct
2 Correct 236 ms 26584 KB Output is correct
3 Correct 250 ms 26244 KB Output is correct
4 Correct 236 ms 26472 KB Output is correct
5 Correct 241 ms 26928 KB Output is correct
6 Correct 245 ms 28540 KB Output is correct
7 Correct 243 ms 28656 KB Output is correct
8 Correct 234 ms 26628 KB Output is correct
9 Correct 248 ms 26928 KB Output is correct
10 Correct 247 ms 26368 KB Output is correct
11 Correct 92 ms 16716 KB Output is correct
12 Correct 244 ms 28772 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5320 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 26056 KB Output is correct
2 Correct 239 ms 25808 KB Output is correct
3 Correct 242 ms 28808 KB Output is correct
4 Correct 247 ms 25976 KB Output is correct
5 Correct 242 ms 24280 KB Output is correct
6 Correct 244 ms 25956 KB Output is correct
7 Correct 258 ms 25812 KB Output is correct
8 Correct 248 ms 25736 KB Output is correct
9 Correct 252 ms 26688 KB Output is correct
10 Correct 250 ms 26708 KB Output is correct
11 Correct 83 ms 15388 KB Output is correct
12 Correct 245 ms 26464 KB Output is correct
13 Correct 286 ms 26872 KB Output is correct
14 Correct 236 ms 26584 KB Output is correct
15 Correct 250 ms 26244 KB Output is correct
16 Correct 236 ms 26472 KB Output is correct
17 Correct 241 ms 26928 KB Output is correct
18 Correct 245 ms 28540 KB Output is correct
19 Correct 243 ms 28656 KB Output is correct
20 Correct 234 ms 26628 KB Output is correct
21 Correct 248 ms 26928 KB Output is correct
22 Correct 247 ms 26368 KB Output is correct
23 Correct 92 ms 16716 KB Output is correct
24 Correct 244 ms 28772 KB Output is correct
25 Correct 17 ms 5320 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Incorrect 2 ms 2644 KB Output isn't correct
28 Halted 0 ms 0 KB -