oj.uz

Submission #483905

# Submission time Handle Problem Language Result Execution time Memory
483905 2021-11-01T10:13:08 Z evenvalue Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 151 ms 262148 KB 
#include "crocodile.h"
#include <vector>
using namespace std;

struct edge {
  int x;
  int y;
  int w;
};

class solution {
  const int kInf = 1e9 + 10;
  const int n;
  const int m;
  const vector<edge> edges;
  const int k;
  const vector<int> end;
  vector<vector<pair<int, int>>> g;
  vector<int> dp;

  int dfs(const int x, const int p) {
    if (dp[x] == 0) return 0;
    int mn = kInf, mn2 = kInf;
    for (const auto &[y, w] : g[x]) {
      if (y == p) continue;
      const int cur = dfs(y, x) + w;
      if (cur < mn) {
        mn2 = mn;
        mn = cur;
      } else {
        mn2 = min(mn2, cur);
      }
    }
    return (dp[x] = mn2);
  }

public:
  explicit solution(const int n, const vector<edge> &edges, const vector<int> &end) : n(n), m(edges.size()), edges(edges), k(end.size()), end(end), g(n), dp(n, kInf) {
    for (const auto &[x, y, w] : edges) {
      g[x].emplace_back(y, w);
      g[y].emplace_back(x, w);
    }
    for (const int x : end) dp[x] = 0;
  }

  int solve() {
    return dfs(0, -1);
  }
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  vector<edge> edges(M);
  for (int i = 0; i < M; i++) {
    edges[i].x = R[i][0];
    edges[i].y = R[i][1];
    edges[i].w = L[i];
  }
  vector<int> end(K);
  for (int i = 0; i < K; i++) {
    end[i] = P[i];
  }
  solution s(N, edges, end);
  return s.solve();
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Runtime error 151 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Runtime error 151 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -