oj.uz

Submission #954823

# Submission time Handle Problem Language Result Execution time Memory
954823 2024-03-28T16:14:26 Z evenvalue Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 221268 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 = 150;

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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 11 ms 2444 KB Output is correct
10 Correct 12 ms 2396 KB Output is correct
11 Correct 13 ms 2396 KB Output is correct
12 Correct 8 ms 1624 KB Output is correct
13 Correct 13 ms 2140 KB Output is correct
14 Correct 10 ms 1628 KB Output is correct
15 Correct 6 ms 1112 KB Output is correct
16 Correct 13 ms 1884 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 6 ms 1372 KB Output is correct
19 Correct 10 ms 1880 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 11 ms 2444 KB Output is correct
10 Correct 12 ms 2396 KB Output is correct
11 Correct 13 ms 2396 KB Output is correct
12 Correct 8 ms 1624 KB Output is correct
13 Correct 13 ms 2140 KB Output is correct
14 Correct 10 ms 1628 KB Output is correct
15 Correct 6 ms 1112 KB Output is correct
16 Correct 13 ms 1884 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 6 ms 1372 KB Output is correct
19 Correct 10 ms 1880 KB Output is correct
20 Correct 1637 ms 4496 KB Output is correct
21 Correct 1590 ms 4536 KB Output is correct
22 Correct 1626 ms 4400 KB Output is correct
23 Correct 1607 ms 6168 KB Output is correct
24 Correct 1132 ms 157408 KB Output is correct
25 Correct 1197 ms 162640 KB Output is correct
26 Correct 1183 ms 162564 KB Output is correct
27 Correct 1150 ms 221104 KB Output is correct
28 Correct 1144 ms 221004 KB Output is correct
29 Correct 1140 ms 221268 KB Output is correct
30 Correct 1286 ms 220888 KB Output is correct
31 Correct 1584 ms 215368 KB Output is correct
32 Correct 1290 ms 220992 KB Output is correct
33 Correct 1016 ms 137812 KB Output is correct
34 Correct 933 ms 118356 KB Output is correct
35 Correct 997 ms 136920 KB Output is correct
36 Correct 1266 ms 179856 KB Output is correct
37 Correct 1261 ms 167096 KB Output is correct
38 Correct 1262 ms 180536 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 11 ms 2444 KB Output is correct
10 Correct 12 ms 2396 KB Output is correct
11 Correct 13 ms 2396 KB Output is correct
12 Correct 8 ms 1624 KB Output is correct
13 Correct 13 ms 2140 KB Output is correct
14 Correct 10 ms 1628 KB Output is correct
15 Correct 6 ms 1112 KB Output is correct
16 Correct 13 ms 1884 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 6 ms 1372 KB Output is correct
19 Correct 10 ms 1880 KB Output is correct
20 Correct 1637 ms 4496 KB Output is correct
21 Correct 1590 ms 4536 KB Output is correct
22 Correct 1626 ms 4400 KB Output is correct
23 Correct 1607 ms 6168 KB Output is correct
24 Correct 1132 ms 157408 KB Output is correct
25 Correct 1197 ms 162640 KB Output is correct
26 Correct 1183 ms 162564 KB Output is correct
27 Correct 1150 ms 221104 KB Output is correct
28 Correct 1144 ms 221004 KB Output is correct
29 Correct 1140 ms 221268 KB Output is correct
30 Correct 1286 ms 220888 KB Output is correct
31 Correct 1584 ms 215368 KB Output is correct
32 Correct 1290 ms 220992 KB Output is correct
33 Correct 1016 ms 137812 KB Output is correct
34 Correct 933 ms 118356 KB Output is correct
35 Correct 997 ms 136920 KB Output is correct
36 Correct 1266 ms 179856 KB Output is correct
37 Correct 1261 ms 167096 KB Output is correct
38 Correct 1262 ms 180536 KB Output is correct
39 Correct 1171 ms 156536 KB Output is correct
40 Correct 1181 ms 157832 KB Output is correct
41 Correct 1173 ms 158144 KB Output is correct
42 Execution timed out 2061 ms 160800 KB Time limit exceeded
43 Halted 0 ms 0 KB -