oj.uz

Submission #666863

# Submission time Handle Problem Language Result Execution time Memory
666863 2022-11-29T19:48:15 Z kirakaminski968 Robot (JOI21_ho_t4) C++17
100 / 100
 783 ms 113116 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define setp() cout << setprecision(15)
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;
struct Edge{
  int nxt,c; 
  ll e; 
};
int n,m; 
ll dist[N][2] ;
vector<Edge> g[N]; 
map<int,ll> s[N]; 
int t; 
void solve(){
  cin >> n >> m; 
  for(int i = 0;i<m;++i){
    int u,v,c;
    ll e; 
    cin >> u >> v >> c >> e; 
    g[u].push_back({v,c,e}); 
    g[v].push_back({u,c,e}); 
    s[u][c] += e; 
    s[v][c] += e; 
  }
  for(int i = 1;i<=n;++i) dist[i][0] = dist[i][1] = 1e18; 
  priority_queue<array<ll,3>> pq; 
  vector<bool> vis[2]; 
  vis[0].resize(n+1); 
  vis[1].resize(n+1); 
  dist[n][0] = 0; 
  pq.push({0,n,-1}); 
  while(pq.size()){
    int v = pq.top()[1], cc = pq.top()[2]; 
    ll D = -pq.top()[0]; 
    pq.pop(); 
    if(vis[cc == -1][v]) continue; 
    vis[cc == -1][v] = 1; 
    for(auto E : g[v]){
      int c = E.c, nxt = E.nxt; 
      ll e = E.e, val = s[nxt][c]; 
      if(cc == c) e = 0; 
      if(D + e < dist[nxt][0]){
        dist[nxt][0] = D+e; 
        pq.push({-dist[nxt][0],nxt,-1}); 
      }
      if(D - e + val < dist[nxt][1]){
        dist[nxt][1] = D-e+val; 
        pq.push({-dist[nxt][1],nxt,c}); 
      }
    }
  }
  if(min(dist[1][0],dist[1][1]) == 1e18) cout << -1; 
  else cout << min(dist[1][0],dist[1][1]); 
}
int main(){
  solve(); 
  return 0; 
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 70748 KB Output is correct
2 Correct 37 ms 70740 KB Output is correct
3 Correct 37 ms 70748 KB Output is correct
4 Correct 37 ms 70768 KB Output is correct
5 Correct 37 ms 70740 KB Output is correct
6 Correct 38 ms 70660 KB Output is correct
7 Correct 38 ms 70824 KB Output is correct
8 Correct 39 ms 70804 KB Output is correct
9 Correct 40 ms 71132 KB Output is correct
10 Correct 41 ms 71156 KB Output is correct
11 Correct 39 ms 71016 KB Output is correct
12 Correct 38 ms 70996 KB Output is correct
13 Correct 39 ms 71088 KB Output is correct
14 Correct 40 ms 70972 KB Output is correct
15 Correct 40 ms 70904 KB Output is correct
16 Correct 40 ms 70892 KB Output is correct
17 Correct 41 ms 70868 KB Output is correct
18 Correct 39 ms 70808 KB Output is correct
19 Correct 39 ms 70860 KB Output is correct
20 Correct 45 ms 70864 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 80980 KB Output is correct
2 Correct 95 ms 76572 KB Output is correct
3 Correct 226 ms 84536 KB Output is correct
4 Correct 137 ms 78536 KB Output is correct
5 Correct 663 ms 106896 KB Output is correct
6 Correct 543 ms 101060 KB Output is correct
7 Correct 408 ms 97496 KB Output is correct
8 Correct 437 ms 91236 KB Output is correct
9 Correct 426 ms 91348 KB Output is correct
10 Correct 250 ms 87804 KB Output is correct
11 Correct 215 ms 83544 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 70748 KB Output is correct
2 Correct 37 ms 70740 KB Output is correct
3 Correct 37 ms 70748 KB Output is correct
4 Correct 37 ms 70768 KB Output is correct
5 Correct 37 ms 70740 KB Output is correct
6 Correct 38 ms 70660 KB Output is correct
7 Correct 38 ms 70824 KB Output is correct
8 Correct 39 ms 70804 KB Output is correct
9 Correct 40 ms 71132 KB Output is correct
10 Correct 41 ms 71156 KB Output is correct
11 Correct 39 ms 71016 KB Output is correct
12 Correct 38 ms 70996 KB Output is correct
13 Correct 39 ms 71088 KB Output is correct
14 Correct 40 ms 70972 KB Output is correct
15 Correct 40 ms 70904 KB Output is correct
16 Correct 40 ms 70892 KB Output is correct
17 Correct 41 ms 70868 KB Output is correct
18 Correct 39 ms 70808 KB Output is correct
19 Correct 39 ms 70860 KB Output is correct
20 Correct 45 ms 70864 KB Output is correct
21 Correct 198 ms 80980 KB Output is correct
22 Correct 95 ms 76572 KB Output is correct
23 Correct 226 ms 84536 KB Output is correct
24 Correct 137 ms 78536 KB Output is correct
25 Correct 663 ms 106896 KB Output is correct
26 Correct 543 ms 101060 KB Output is correct
27 Correct 408 ms 97496 KB Output is correct
28 Correct 437 ms 91236 KB Output is correct
29 Correct 426 ms 91348 KB Output is correct
30 Correct 250 ms 87804 KB Output is correct
31 Correct 215 ms 83544 KB Output is correct
32 Correct 266 ms 81172 KB Output is correct
33 Correct 261 ms 83732 KB Output is correct
34 Correct 454 ms 90504 KB Output is correct
35 Correct 351 ms 87344 KB Output is correct
36 Correct 400 ms 93196 KB Output is correct
37 Correct 433 ms 93204 KB Output is correct
38 Correct 426 ms 97396 KB Output is correct
39 Correct 301 ms 84984 KB Output is correct
40 Correct 470 ms 91268 KB Output is correct
41 Correct 500 ms 91344 KB Output is correct
42 Correct 400 ms 93896 KB Output is correct
43 Correct 222 ms 83592 KB Output is correct
44 Correct 383 ms 89364 KB Output is correct
45 Correct 369 ms 88148 KB Output is correct
46 Correct 335 ms 88800 KB Output is correct
47 Correct 383 ms 94576 KB Output is correct
48 Correct 783 ms 113116 KB Output is correct