oj.uz

Submission #954827

# Submission time Handle Problem Language Result Execution time Memory
954827 2024-03-28T16:28:56 Z evenvalue Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1698 ms 221260 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<basic_string<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);
  }

  vector<bool> busy(n);
  vector<vector<pair<int, int>>> best_paths(n);
  for (int x = 0; x < n; 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(), best_paths[y].begin(), best_paths[y].end());
    }
    sort(best.rbegin(), best.rend());
    for (const auto [dist, y] : best) {
      if (busy[y]) continue;
      busy[y] = true;
      best_paths[x].emplace_back(dist + 1, y);
      if (best_paths[x].size() == kSqrtN) break;
    }
    for (const auto [dist, y] : best_paths[x]) {
      busy[y] = false;
    }
  }


  vector<int> dp(n);
  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) {
      fill(dp.begin(), dp.begin() + x + 1, 0);
      for (const int nerd : nerds) {
        dp[nerd - 1] = -kInf;
      }
      for (int y = 0; y <= x; y++) {
        for (const int z : in[y]) {
          dp[y] = max(dp[y], dp[z] + 1);
        }
      }
      cout << max(dp[x], -1) << '\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();
  }
}

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 0 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 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 13 ms 2360 KB Output is correct
9 Correct 11 ms 2392 KB Output is correct
10 Correct 11 ms 2396 KB Output is correct
11 Correct 13 ms 2140 KB Output is correct
12 Correct 7 ms 1628 KB Output is correct
13 Correct 12 ms 2140 KB Output is correct
14 Correct 9 ms 1628 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 9 ms 1628 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 7 ms 1368 KB Output is correct
19 Correct 11 ms 1884 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 0 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 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 13 ms 2360 KB Output is correct
9 Correct 11 ms 2392 KB Output is correct
10 Correct 11 ms 2396 KB Output is correct
11 Correct 13 ms 2140 KB Output is correct
12 Correct 7 ms 1628 KB Output is correct
13 Correct 12 ms 2140 KB Output is correct
14 Correct 9 ms 1628 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 9 ms 1628 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 7 ms 1368 KB Output is correct
19 Correct 11 ms 1884 KB Output is correct
20 Correct 1577 ms 4756 KB Output is correct
21 Correct 1524 ms 4680 KB Output is correct
22 Correct 1544 ms 4496 KB Output is correct
23 Correct 1513 ms 6460 KB Output is correct
24 Correct 1070 ms 154076 KB Output is correct
25 Correct 1148 ms 159104 KB Output is correct
26 Correct 1149 ms 159392 KB Output is correct
27 Correct 1108 ms 217172 KB Output is correct
28 Correct 1084 ms 216972 KB Output is correct
29 Correct 1090 ms 217052 KB Output is correct
30 Correct 1267 ms 217072 KB Output is correct
31 Correct 1522 ms 211504 KB Output is correct
32 Correct 1270 ms 216860 KB Output is correct
33 Correct 976 ms 134736 KB Output is correct
34 Correct 886 ms 115324 KB Output is correct
35 Correct 969 ms 133872 KB Output is correct
36 Correct 1208 ms 176668 KB Output is correct
37 Correct 1201 ms 163804 KB Output is correct
38 Correct 1214 ms 177324 KB Output is correct

Subtask #3
86.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 0 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 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 13 ms 2360 KB Output is correct
9 Correct 11 ms 2392 KB Output is correct
10 Correct 11 ms 2396 KB Output is correct
11 Correct 13 ms 2140 KB Output is correct
12 Correct 7 ms 1628 KB Output is correct
13 Correct 12 ms 2140 KB Output is correct
14 Correct 9 ms 1628 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 9 ms 1628 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Correct 7 ms 1368 KB Output is correct
19 Correct 11 ms 1884 KB Output is correct
20 Correct 1577 ms 4756 KB Output is correct
21 Correct 1524 ms 4680 KB Output is correct
22 Correct 1544 ms 4496 KB Output is correct
23 Correct 1513 ms 6460 KB Output is correct
24 Correct 1070 ms 154076 KB Output is correct
25 Correct 1148 ms 159104 KB Output is correct
26 Correct 1149 ms 159392 KB Output is correct
27 Correct 1108 ms 217172 KB Output is correct
28 Correct 1084 ms 216972 KB Output is correct
29 Correct 1090 ms 217052 KB Output is correct
30 Correct 1267 ms 217072 KB Output is correct
31 Correct 1522 ms 211504 KB Output is correct
32 Correct 1270 ms 216860 KB Output is correct
33 Correct 976 ms 134736 KB Output is correct
34 Correct 886 ms 115324 KB Output is correct
35 Correct 969 ms 133872 KB Output is correct
36 Correct 1208 ms 176668 KB Output is correct
37 Correct 1201 ms 163804 KB Output is correct
38 Correct 1214 ms 177324 KB Output is correct
39 Correct 1123 ms 155772 KB Output is correct
40 Correct 1118 ms 156904 KB Output is correct
41 Correct 1125 ms 157168 KB Output is correct
42 Correct 1152 ms 157120 KB Output is correct
43 Correct 1105 ms 158060 KB Output is correct
44 Correct 1591 ms 6528 KB Output is correct
45 Correct 1566 ms 6380 KB Output is correct
46 Correct 1563 ms 6752 KB Output is correct
47 Correct 1568 ms 6312 KB Output is correct
48 Correct 1555 ms 6416 KB Output is correct
49 Correct 1132 ms 220824 KB Output is correct
50 Correct 1113 ms 219476 KB Output is correct
51 Correct 1545 ms 7240 KB Output is correct
52 Correct 1534 ms 6424 KB Output is correct
53 Correct 1251 ms 179692 KB Output is correct
54 Correct 1230 ms 166944 KB Output is correct
55 Correct 1212 ms 178732 KB Output is correct
56 Correct 1227 ms 166948 KB Output is correct
57 Correct 1583 ms 7380 KB Output is correct
58 Correct 1592 ms 7272 KB Output is correct
59 Correct 1571 ms 6688 KB Output is correct
60 Correct 1559 ms 6712 KB Output is correct
61 Correct 1150 ms 219672 KB Output is correct
62 Correct 1288 ms 179428 KB Output is correct
63 Correct 1236 ms 165360 KB Output is correct
64 Correct 1268 ms 219500 KB Output is correct
65 Correct 1345 ms 179056 KB Output is correct
66 Correct 1346 ms 167264 KB Output is correct
67 Correct 1290 ms 219360 KB Output is correct
68 Correct 1468 ms 179396 KB Output is correct
69 Correct 1413 ms 164428 KB Output is correct
70 Correct 1104 ms 219644 KB Output is correct
71 Correct 1229 ms 179816 KB Output is correct
72 Correct 1228 ms 166064 KB Output is correct
73 Correct 1129 ms 219544 KB Output is correct
74 Correct 1256 ms 179432 KB Output is correct
75 Correct 1206 ms 166116 KB Output is correct
76 Correct 1138 ms 221260 KB Output is correct
77 Correct 1235 ms 220068 KB Output is correct
78 Correct 1110 ms 220168 KB Output is correct
79 Correct 1558 ms 7348 KB Output is correct
80 Correct 1554 ms 6376 KB Output is correct
81 Correct 1538 ms 6320 KB Output is correct
82 Correct 1319 ms 221116 KB Output is correct
83 Correct 1616 ms 215384 KB Output is correct
84 Correct 1378 ms 219540 KB Output is correct
85 Correct 1698 ms 213824 KB Output is correct
86 Correct 1278 ms 220188 KB Output is correct
87 Correct 1620 ms 214532 KB Output is correct
88 Correct 1591 ms 7596 KB Output is correct
89 Correct 1596 ms 7376 KB Output is correct
90 Correct 1595 ms 6568 KB Output is correct
91 Correct 1620 ms 6476 KB Output is correct
92 Correct 1586 ms 6548 KB Output is correct
93 Correct 1571 ms 6208 KB Output is correct
94 Correct 1016 ms 139032 KB Output is correct
95 Correct 930 ms 118784 KB Output is correct
96 Correct 1101 ms 136608 KB Output is correct
97 Correct 1027 ms 119672 KB Output is correct
98 Correct 1016 ms 137208 KB Output is correct
99 Correct 944 ms 119308 KB Output is correct
100 Correct 1602 ms 8292 KB Output is correct
101 Correct 1517 ms 8684 KB Output is correct
102 Correct 1575 ms 7600 KB Output is correct
103 Correct 1540 ms 7672 KB Output is correct
104 Correct 1570 ms 7260 KB Output is correct
105 Correct 1519 ms 7208 KB Output is correct
106 Correct 1294 ms 180048 KB Output is correct
107 Correct 1245 ms 167308 KB Output is correct
108 Correct 1335 ms 179968 KB Output is correct
109 Correct 1305 ms 165796 KB Output is correct
110 Correct 1240 ms 179900 KB Output is correct
111 Correct 1244 ms 166752 KB Output is correct
112 Correct 1577 ms 7188 KB Output is correct
113 Correct 1593 ms 7432 KB Output is correct
114 Correct 1587 ms 6740 KB Output is correct
115 Correct 1601 ms 6960 KB Output is correct
116 Correct 1574 ms 6108 KB Output is correct
117 Correct 1573 ms 6848 KB Output is correct
118 Correct 1157 ms 219180 KB Output is correct
119 Correct 1268 ms 179996 KB Output is correct
120 Correct 1202 ms 165840 KB Output is correct
121 Correct 1121 ms 219472 KB Output is correct
122 Correct 1219 ms 178904 KB Output is correct
123 Correct 1205 ms 165560 KB Output is correct
124 Correct 1108 ms 219288 KB Output is correct
125 Correct 1259 ms 179872 KB Output is correct
126 Correct 1219 ms 165540 KB Output is correct