oj.uz

Submission #378075

# Submission time Handle Problem Language Result Execution time Memory
378075 2021-03-15T22:49:41 Z MilosMilutinovic Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 170 ms 262148 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

vector<vector<pair<int, int>>> g(N);
vector<bool> esc(N, false);
vector<int> dp(N, 0);

void Dfs(int u, int p) {
  if (esc[u]) {
    return;
  }
  for (auto v : g[u]) {
    if (v.first == p) {
      continue;
    }
    Dfs(v.first, u);
  }
  vector<pair<int, int>> id;
  for (auto v : g[u]) {
    if (v.first != p) {
      id.emplace_back(dp[v.first], v.second);
    }
  }
  sort(id.begin(), id.end(), [&](pair<int, int> i, pair<int, int> j) {
    return i.first + i. second < j.first + j.second;
  });
  assert((int) id.size() >= 2);
  dp[u] = id[1].first + id[1].second;
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
  for (int i = 0; i < m; i++) {
    g[r[i][0]].emplace_back(r[i][1], l[i]);
    g[r[i][1]].emplace_back(r[i][0], l[i]);
  }
  for (int i = 0; i < k; i++) {
    esc[p[i]] = true;
  }
  Dfs(0, -1);
  return dp[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3052 KB Output is correct
2 Correct 2 ms 3052 KB Output is correct
3 Correct 2 ms 3052 KB Output is correct
4 Correct 3 ms 3180 KB Output is correct
5 Correct 3 ms 3180 KB Output is correct
6 Correct 3 ms 3180 KB Output is correct
7 Correct 3 ms 3180 KB Output is correct
8 Correct 4 ms 3180 KB Output is correct
9 Runtime error 170 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 2 ms 3052 KB Output is correct
2 Correct 2 ms 3052 KB Output is correct
3 Correct 2 ms 3052 KB Output is correct
4 Correct 3 ms 3180 KB Output is correct
5 Correct 3 ms 3180 KB Output is correct
6 Correct 3 ms 3180 KB Output is correct
7 Correct 3 ms 3180 KB Output is correct
8 Correct 4 ms 3180 KB Output is correct
9 Runtime error 170 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -