oj.uz

Submission #954824

# Submission time Handle Problem Language Result Execution time Memory
954824 2024-03-28T16:15:41 Z evenvalue Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 228668 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef evenvalue
  #include "debug.h"
#else
  #define debug(...)
#endif

using int64 = long long;
using ld = long double;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

namespace Read {
int Int() {
  int x;
  cin >> x;
  return x;
}
int64 Int64() {
  int64 x;
  cin >> x;
  return x;
}
char Char() {
  char c;
  cin >> c;
  return c;
}
string String() {
  string s;
  cin >> s;
  return s;
}
double Double() {
  return stod(String());
}
ld LongDouble() {
  return stold(String());
}
template<typename T1, typename T2>
pair<T1, T2> Pair() {
  pair<T1, T2> p;
  cin >> p.first >> p.second;
  return p;
}
template<typename T>
vector<T> Vec(const int n) {
  vector<T> v(n);
  for (T &x : v) {
    cin >> x;
  }
  return v;
}
template<typename T>
vector<vector<T>> VecVec(const int n, const int m) {
  vector<vector<T>> v(n);
  for (vector<T> &vec : v) {
    vec = Vec<T>(m);
  }
  return v;
}
}//namespace Read

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kMaxN = 2e5 + 10;
constexpr int kSqrtN = 170;

inline void solution() {
  const int n = Read::Int();
  const int m = Read::Int();
  const int q = Read::Int();

  vector<vector<int>> in(n);
  for (int i = 0; i < m; i++) {
    const int x = Read::Int() - 1;
    const int y = Read::Int() - 1;
    in[y].push_back(x);
  }

  auto calc_dp = [&](const int size, vector<bool> &busy, const int till) {
    vector<vector<pair<int, int>>> dp(n);
    for (int x = 0; x <= till; x++) {
      vector<pair<int, int>> best;
      if (not busy[x]) best.emplace_back(-1, x);
      for (const int y : in[x]) {
        best.insert(best.end(), dp[y].begin(), dp[y].end());
      }
      sort(best.rbegin(), best.rend());
      for (const auto [dist, y] : best) {
        if (busy[y]) continue;
        busy[y] = true;
        dp[x].emplace_back(dist + 1, y);
        if (dp[x].size() == size) break;
      }
      for (const auto [dist, y] : dp[x]) {
        busy[y] = false;
      }
    }
    return dp;
  };

  vector<bool> busy(n);
  const auto best_paths = calc_dp(kSqrtN, busy, n - 1);

  for (int qry = 0; qry < q; qry++) {
    const int x = Read::Int() - 1;
    const vector<int> nerds = Read::Vec<int>(Read::Int());

    for (const int nerd : nerds) {
      busy[nerd - 1] = true;
    }

    if (nerds.size() >= kSqrtN) {
      const auto &dp = calc_dp(1, busy, x);
      cout << (dp[x].empty() ? -1 : dp[x][0].first) << '\n';
    } else {
      bool found = false;
      for (const auto [dist, y] : best_paths[x]) {
        if (busy[y]) continue;
        found = true;
        cout << dist << '\n';
        break;
      }
      if (not found) cout << -1 << '\n';
    }

    for (const int nerd : nerds) {
      busy[nerd - 1] = false;
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  //freopen(".in", "r", stdin);
  //freopen(".out", "w", stdout);

  cout << fixed << setprecision(10);

  int testcases = 1;
  //cin >> testcases;
  while (testcases--) {
    solution();
  }
}

Compilation message

bitaro.cpp: In lambda function:
bitaro.cpp:100:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  100 |         if (dp[x].size() == size) break;
      |             ~~~~~~~~~~~~~^~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 13 ms 2396 KB Output is correct
9 Correct 13 ms 2548 KB Output is correct
10 Correct 13 ms 2396 KB Output is correct
11 Correct 14 ms 2396 KB Output is correct
12 Correct 8 ms 1624 KB Output is correct
13 Correct 14 ms 2308 KB Output is correct
14 Correct 11 ms 1624 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 11 ms 1628 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 7 ms 1372 KB Output is correct
19 Correct 11 ms 1976 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 13 ms 2396 KB Output is correct
9 Correct 13 ms 2548 KB Output is correct
10 Correct 13 ms 2396 KB Output is correct
11 Correct 14 ms 2396 KB Output is correct
12 Correct 8 ms 1624 KB Output is correct
13 Correct 14 ms 2308 KB Output is correct
14 Correct 11 ms 1624 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 11 ms 1628 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 7 ms 1372 KB Output is correct
19 Correct 11 ms 1976 KB Output is correct
20 Correct 1807 ms 4772 KB Output is correct
21 Correct 1766 ms 4844 KB Output is correct
22 Correct 1804 ms 4392 KB Output is correct
23 Correct 1803 ms 6252 KB Output is correct
24 Correct 1233 ms 160700 KB Output is correct
25 Correct 1303 ms 166184 KB Output is correct
26 Correct 1292 ms 166208 KB Output is correct
27 Correct 1310 ms 228320 KB Output is correct
28 Correct 1318 ms 228668 KB Output is correct
29 Correct 1315 ms 228352 KB Output is correct
30 Correct 1520 ms 228036 KB Output is correct
31 Correct 1790 ms 222468 KB Output is correct
32 Correct 1523 ms 227928 KB Output is correct
33 Correct 1148 ms 141640 KB Output is correct
34 Correct 1058 ms 120732 KB Output is correct
35 Correct 1128 ms 140576 KB Output is correct
36 Correct 1448 ms 186180 KB Output is correct
37 Correct 1413 ms 171772 KB Output is correct
38 Correct 1432 ms 186704 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 13 ms 2396 KB Output is correct
9 Correct 13 ms 2548 KB Output is correct
10 Correct 13 ms 2396 KB Output is correct
11 Correct 14 ms 2396 KB Output is correct
12 Correct 8 ms 1624 KB Output is correct
13 Correct 14 ms 2308 KB Output is correct
14 Correct 11 ms 1624 KB Output is correct
15 Correct 6 ms 1368 KB Output is correct
16 Correct 11 ms 1628 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 7 ms 1372 KB Output is correct
19 Correct 11 ms 1976 KB Output is correct
20 Correct 1807 ms 4772 KB Output is correct
21 Correct 1766 ms 4844 KB Output is correct
22 Correct 1804 ms 4392 KB Output is correct
23 Correct 1803 ms 6252 KB Output is correct
24 Correct 1233 ms 160700 KB Output is correct
25 Correct 1303 ms 166184 KB Output is correct
26 Correct 1292 ms 166208 KB Output is correct
27 Correct 1310 ms 228320 KB Output is correct
28 Correct 1318 ms 228668 KB Output is correct
29 Correct 1315 ms 228352 KB Output is correct
30 Correct 1520 ms 228036 KB Output is correct
31 Correct 1790 ms 222468 KB Output is correct
32 Correct 1523 ms 227928 KB Output is correct
33 Correct 1148 ms 141640 KB Output is correct
34 Correct 1058 ms 120732 KB Output is correct
35 Correct 1128 ms 140576 KB Output is correct
36 Correct 1448 ms 186180 KB Output is correct
37 Correct 1413 ms 171772 KB Output is correct
38 Correct 1432 ms 186704 KB Output is correct
39 Correct 1266 ms 159860 KB Output is correct
40 Correct 1279 ms 161312 KB Output is correct
41 Correct 1271 ms 161596 KB Output is correct
42 Execution timed out 2047 ms 164096 KB Time limit exceeded
43 Halted 0 ms 0 KB -