oj.uz

Submission #581180

# Submission time Handle Problem Language Result Execution time Memory
581180 2022-06-22T10:30:07 Z Theo830 Robot (JOI21_ho_t4) C++17
100 / 100
 527 ms 101852 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
vector<vector<ii> >adj;
vector<vector<iii> >exo;
vector<ll> dist;
void dijkstra(ll s){
    priority_queue<ii,vector<ii>, greater<ii> >pq;
    pq.push(ii(0,s));
    dist[s] = 0;
    while(!pq.empty()){
        ii f = pq.top();
        pq.pop();
        ll w = f.F;
        ll u = f.S;
        if(w > dist[u]){
            continue;
        }
        for(auto v:adj[u]){
            if(dist[u] + v.S < dist[v.F]){
                dist[v.F] = dist[u] + v.S;
                pq.push(ii(dist[v.F],v.F));
            }
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    ll siz = 2 * (n + m + 5);
    adj.assign(siz,vector<ii>());
    exo.assign(siz,vector<iii>());
    dist.assign(siz,1e18);
    ll fake = n+5;
    f(i,0,m){
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        adj[a].pb(ii(b,d));
        adj[b].pb(ii(a,d));
        exo[a].pb(iii(b,ii(c,d)));
        exo[b].pb(iii(a,ii(c,d)));
    }
    ll sum[m+1] = {0};
    ll xroma[m+1] = {0};
    f(i,1,n+1){
        for(auto x:exo[i]){
            sum[x.S.F] += x.S.S;
            if(!xroma[x.S.F]){
                xroma[x.S.F] = fake;
                fake++;
            }
        }
        for(auto x:exo[i]){
            adj[i].pb(ii(x.F,sum[x.S.F] - x.S.S));
            adj[x.F].pb(ii(xroma[x.S.F],sum[x.S.F]));
            adj[xroma[x.S.F]].pb(ii(x.F,-x.S.S));
        }
        for(auto x:exo[i]){
            sum[x.S.F] -= x.S.S;
            xroma[x.S.F] = 0;
        }
    }
    dijkstra(1);
    if(dist[n] == 1e18){
        dist[n] = -1;
    }
    cout<<dist[n]<<"\n";
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 3 ms 1296 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 2 ms 1108 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 3 ms 1272 KB Output is correct
17 Correct 3 ms 980 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 3 ms 1108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 35416 KB Output is correct
2 Correct 62 ms 16520 KB Output is correct
3 Correct 172 ms 55116 KB Output is correct
4 Correct 110 ms 24136 KB Output is correct
5 Correct 495 ms 91596 KB Output is correct
6 Correct 466 ms 93516 KB Output is correct
7 Correct 395 ms 96936 KB Output is correct
8 Correct 425 ms 94300 KB Output is correct
9 Correct 496 ms 94420 KB Output is correct
10 Correct 241 ms 56896 KB Output is correct
11 Correct 181 ms 49136 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 3 ms 1296 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 2 ms 1108 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 3 ms 1272 KB Output is correct
17 Correct 3 ms 980 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 3 ms 1108 KB Output is correct
21 Correct 154 ms 35416 KB Output is correct
22 Correct 62 ms 16520 KB Output is correct
23 Correct 172 ms 55116 KB Output is correct
24 Correct 110 ms 24136 KB Output is correct
25 Correct 495 ms 91596 KB Output is correct
26 Correct 466 ms 93516 KB Output is correct
27 Correct 395 ms 96936 KB Output is correct
28 Correct 425 ms 94300 KB Output is correct
29 Correct 496 ms 94420 KB Output is correct
30 Correct 241 ms 56896 KB Output is correct
31 Correct 181 ms 49136 KB Output is correct
32 Correct 123 ms 60668 KB Output is correct
33 Correct 144 ms 51180 KB Output is correct
34 Correct 316 ms 65736 KB Output is correct
35 Correct 267 ms 55736 KB Output is correct
36 Correct 365 ms 64928 KB Output is correct
37 Correct 352 ms 79940 KB Output is correct
38 Correct 307 ms 91352 KB Output is correct
39 Correct 185 ms 76448 KB Output is correct
40 Correct 527 ms 95476 KB Output is correct
41 Correct 482 ms 95972 KB Output is correct
42 Correct 494 ms 87716 KB Output is correct
43 Correct 159 ms 43860 KB Output is correct
44 Correct 221 ms 86284 KB Output is correct
45 Correct 401 ms 74440 KB Output is correct
46 Correct 318 ms 73776 KB Output is correct
47 Correct 391 ms 74880 KB Output is correct
48 Correct 503 ms 101852 KB Output is correct