oj.uz

Submission #36351

# Submission time Handle Problem Language Result Execution time Memory
36351 2017-12-08T02:49:21 Z funcsr Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1529 ms 174380 KB 
#include <iostream>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define _1 first
#define _2 second
typedef pair<int, int> P;

int N, M;
vector<P> G[100000];
priority_queue<P, vector<P>, greater<P> > Q;
int dp[100000];
bool flag[100000], used[100000];
void set(int x, int val) {
  used[x] = true;
  dp[x] = val;
  for (P p : G[x]) {
    int t = p._1, l = p._2;
    Q.push(P(val+l, t));
  }
}

int travel_plan(int n, int m, int R[][2], int L[], int K, int p[]) {
  N = n, M = m;
  rep(i, M) {
    G[R[i][0]].pb(P(R[i][1], L[i]));
    G[R[i][1]].pb(P(R[i][0], L[i]));
  }
  rep(i, N) dp[i] = INF, flag[i] = used[i] = false;
  rep(i, K) {
    int x = p[i];
    set(x, 0);
  }
  while (!Q.empty()) {
    int val = Q.top()._1, x = Q.top()._2;
    Q.pop();
    if (used[x]) continue;
    if (flag[x]) set(x, val);
    else flag[x] = true;
  }
  return dp[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122328 KB Output is correct
2 Correct 0 ms 122328 KB Output is correct
3 Correct 0 ms 122328 KB Output is correct
4 Correct 3 ms 122460 KB Output is correct
5 Correct 3 ms 122464 KB Output is correct
6 Correct 0 ms 122328 KB Output is correct
7 Correct 3 ms 122460 KB Output is correct
8 Correct 3 ms 122328 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 122736 KB Output is correct
2 Correct 0 ms 122328 KB Output is correct
3 Correct 0 ms 122460 KB Output is correct
4 Correct 9 ms 123016 KB Output is correct
5 Correct 9 ms 123096 KB Output is correct
6 Correct 0 ms 122328 KB Output is correct
7 Correct 0 ms 122460 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1466 ms 172020 KB Output is correct
2 Correct 133 ms 127080 KB Output is correct
3 Correct 176 ms 128268 KB Output is correct
4 Correct 1529 ms 174380 KB Output is correct
5 Correct 853 ms 169880 KB Output is correct
6 Correct 73 ms 124704 KB Output is correct
7 Correct 703 ms 141464 KB Output is correct