oj.uz

Submission #286079

# Submission time Handle Problem Language Result Execution time Memory
286079 2020-08-30T04:58:28 Z kevlee Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 750 ms 64492 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
vp edges[100005];
int n, m;
ll dist[100005], dist2[100005];
int vis[100005];
int travel_plan(int N, int M, int r[][2], int l[], int K, int P[]) {
  n = N;
  m = M;
  FOR(i, 0, m-1) {
    edges[r[i][0]].emplace_back(r[i][1], l[i]);
    edges[r[i][1]].emplace_back(r[i][0], l[i]);
  }
  priority_queue <pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
  FOR(i, 0, n-1) {
    dist[i] = 1e15;
    dist2[i] = 1e15;
  }
  FOR(i, 0, K-1) {
    dist[P[i]] = 0;
    dist2[P[i]] = 0;
    vis[P[i]] = 1;
    pq.push({0LL, P[i]});
  }
  while (!pq.empty()) {
    pll f = pq.top();
    pq.pop();
    int u = f.se;
    ll d = f.fi;
    if (vis[u] == 2) continue;
    if (!vis[u]) {
      vis[u] = 1;
      //cout << u << ' ' << dist[u] << endl;
      continue;
    }
    vis[u] = 2;
    //cout << u << ' ' << dist2[u] << endl;
    for (auto edge: edges[u]) {
      if (vis[edge.fi] < 2 && dist[edge.fi] > dist2[u] + edge.se) {
        dist2[edge.fi] = dist[edge.fi];
        dist[edge.fi] = dist2[u] + edge.se;
        pq.push({dist[edge.fi], edge.fi});
      } else if (vis[edge.fi] < 2 && dist2[edge.fi] > dist2[u] + edge.se) {
        dist2[edge.fi] = dist2[u] + edge.se;
        pq.push({dist2[edge.fi], edge.fi});
      }
    }
  }
  return dist2[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:47:8: warning: unused variable 'd' [-Wunused-variable]
   47 |     ll d = f.fi;
      |        ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2944 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2944 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3200 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2944 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3200 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Correct 594 ms 60712 KB Output is correct
17 Correct 95 ms 14968 KB Output is correct
18 Correct 125 ms 16504 KB Output is correct
19 Correct 750 ms 64492 KB Output is correct
20 Correct 325 ms 49656 KB Output is correct
21 Correct 46 ms 8056 KB Output is correct
22 Correct 370 ms 46456 KB Output is correct