oj.uz

Submission #583073

# Submission time Handle Problem Language Result Execution time Memory
583073 2022-06-24T18:26:39 Z AlexLuchianov Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 671 ms 217728 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using ll = long long;

int const nmax = 100000;
int const threshold = 260;
std::vector<int> g[5 + nmax];

int cap[5 + nmax];
std::pair<int, int> dp[5 + nmax][5 + threshold];
std::pair<int,int> aux[5 + threshold * 2];

namespace lowmap{
  int frec[5 + nmax];
  int timestamp = 1;
  void reset() {
    ++timestamp;
  }
  bool find(int val) {
    return frec[val] == timestamp;
  }
  void insert(int val) {
    frec[val] = timestamp;
  }
};

int dpBrut[5 + nmax];

int brute(int target) {
  for(int i = 1;i <= target; i++) {
    if(lowmap::find(i) == 0)
      dpBrut[i] = 1;
    else
      dpBrut[i] = 0;
    for(int h = 0; h < g[i].size(); h++) {
      int to = g[i][h];
      if(0 < dpBrut[to])
        dpBrut[i] = std::max(dpBrut[i], dpBrut[to] + 1);
    }
  }
  return dpBrut[target] - 1;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, m, q;
  std::cin >> n >> m >> q;
  for(int i = 1;i <= m; i++) {
    int x, y;
    std::cin >> x >> y;
    g[y].push_back(x);
  }
  for(int i = 1;i <= n; i++) {
    cap[i] = 1;
    dp[i][1] = {0, i};
    for(int h = 0; h < g[i].size(); h++) {
      int to = g[i][h];
      std::merge(dp[i] + 1, dp[i] + cap[i] + 1, 
                 dp[to] + 1, dp[to] + cap[to] + 1,
                 aux + 1, std::greater<std::pair<int,int>>() );
      lowmap::reset();
      int lim = cap[i] + cap[to];
      cap[i] = 0;
      for(int j = 1;j <= lim && cap[i] < threshold; j++) {
        if(lowmap::find(aux[j].second) == 0) {
          lowmap::insert(aux[j].second);
          dp[i][++cap[i]] = aux[j];
        }
      }
    }
    for(int j = 1;j <= cap[i]; j++)
      dp[i][j].first++;
  }

  for(int i = 1;i <= q; i++) {
    int x, k;
    std::cin >> x >> k;
    lowmap::reset();
    for(int j = 1;j <= k; j++) {
      int val;
      std::cin >> val;
      lowmap::insert(val);
    }
    if(k < threshold) {
      bool solved = false;
      for(int j = 1; j <= cap[x]; j++)
        if(lowmap::find(dp[x][j].second) == 0) {
          std::cout << dp[x][j].first -1 << '\n';
          solved = true;
          break;
        }
      if(solved == false)
        std::cout << -1 << '\n'; 
    } else {
      std::cout << brute(x) << '\n';
    }
  }
  return 0;
}

Compilation message

bitaro.cpp: In function 'int brute(int)':
bitaro.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int h = 0; h < g[i].size(); h++) {
      |                    ~~^~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int h = 0; h < g[i].size(); h++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 4 ms 4820 KB Output is correct
7 Correct 4 ms 4692 KB Output is correct
8 Correct 7 ms 4796 KB Output is correct
9 Correct 5 ms 4828 KB Output is correct
10 Correct 5 ms 4792 KB Output is correct
11 Correct 6 ms 4692 KB Output is correct
12 Correct 5 ms 4820 KB Output is correct
13 Correct 6 ms 4692 KB Output is correct
14 Correct 5 ms 4744 KB Output is correct
15 Correct 4 ms 4692 KB Output is correct
16 Correct 5 ms 4692 KB Output is correct
17 Correct 5 ms 4692 KB Output is correct
18 Correct 5 ms 4692 KB Output is correct
19 Correct 5 ms 4876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 4 ms 4820 KB Output is correct
7 Correct 4 ms 4692 KB Output is correct
8 Correct 7 ms 4796 KB Output is correct
9 Correct 5 ms 4828 KB Output is correct
10 Correct 5 ms 4792 KB Output is correct
11 Correct 6 ms 4692 KB Output is correct
12 Correct 5 ms 4820 KB Output is correct
13 Correct 6 ms 4692 KB Output is correct
14 Correct 5 ms 4744 KB Output is correct
15 Correct 4 ms 4692 KB Output is correct
16 Correct 5 ms 4692 KB Output is correct
17 Correct 5 ms 4692 KB Output is correct
18 Correct 5 ms 4692 KB Output is correct
19 Correct 5 ms 4876 KB Output is correct
20 Correct 353 ms 5932 KB Output is correct
21 Correct 287 ms 5916 KB Output is correct
22 Correct 336 ms 6016 KB Output is correct
23 Correct 400 ms 5960 KB Output is correct
24 Correct 486 ms 213836 KB Output is correct
25 Correct 516 ms 213836 KB Output is correct
26 Correct 487 ms 213796 KB Output is correct
27 Correct 407 ms 214220 KB Output is correct
28 Correct 403 ms 214220 KB Output is correct
29 Correct 419 ms 214148 KB Output is correct
30 Correct 445 ms 214060 KB Output is correct
31 Correct 440 ms 214404 KB Output is correct
32 Correct 432 ms 213960 KB Output is correct
33 Correct 351 ms 213636 KB Output is correct
34 Correct 329 ms 213840 KB Output is correct
35 Correct 345 ms 213760 KB Output is correct
36 Correct 377 ms 213988 KB Output is correct
37 Correct 393 ms 213940 KB Output is correct
38 Correct 392 ms 213760 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 4 ms 4820 KB Output is correct
7 Correct 4 ms 4692 KB Output is correct
8 Correct 7 ms 4796 KB Output is correct
9 Correct 5 ms 4828 KB Output is correct
10 Correct 5 ms 4792 KB Output is correct
11 Correct 6 ms 4692 KB Output is correct
12 Correct 5 ms 4820 KB Output is correct
13 Correct 6 ms 4692 KB Output is correct
14 Correct 5 ms 4744 KB Output is correct
15 Correct 4 ms 4692 KB Output is correct
16 Correct 5 ms 4692 KB Output is correct
17 Correct 5 ms 4692 KB Output is correct
18 Correct 5 ms 4692 KB Output is correct
19 Correct 5 ms 4876 KB Output is correct
20 Correct 353 ms 5932 KB Output is correct
21 Correct 287 ms 5916 KB Output is correct
22 Correct 336 ms 6016 KB Output is correct
23 Correct 400 ms 5960 KB Output is correct
24 Correct 486 ms 213836 KB Output is correct
25 Correct 516 ms 213836 KB Output is correct
26 Correct 487 ms 213796 KB Output is correct
27 Correct 407 ms 214220 KB Output is correct
28 Correct 403 ms 214220 KB Output is correct
29 Correct 419 ms 214148 KB Output is correct
30 Correct 445 ms 214060 KB Output is correct
31 Correct 440 ms 214404 KB Output is correct
32 Correct 432 ms 213960 KB Output is correct
33 Correct 351 ms 213636 KB Output is correct
34 Correct 329 ms 213840 KB Output is correct
35 Correct 345 ms 213760 KB Output is correct
36 Correct 377 ms 213988 KB Output is correct
37 Correct 393 ms 213940 KB Output is correct
38 Correct 392 ms 213760 KB Output is correct
39 Correct 549 ms 213940 KB Output is correct
40 Correct 494 ms 213684 KB Output is correct
41 Correct 480 ms 213616 KB Output is correct
42 Correct 555 ms 214152 KB Output is correct
43 Correct 486 ms 214088 KB Output is correct
44 Correct 368 ms 6468 KB Output is correct
45 Correct 354 ms 6064 KB Output is correct
46 Correct 351 ms 6140 KB Output is correct
47 Correct 377 ms 6032 KB Output is correct
48 Correct 357 ms 6016 KB Output is correct
49 Correct 466 ms 214296 KB Output is correct
50 Correct 436 ms 213652 KB Output is correct
51 Correct 368 ms 6308 KB Output is correct
52 Correct 313 ms 5888 KB Output is correct
53 Correct 454 ms 214372 KB Output is correct
54 Correct 473 ms 213904 KB Output is correct
55 Correct 451 ms 213656 KB Output is correct
56 Correct 441 ms 213680 KB Output is correct
57 Correct 400 ms 6352 KB Output is correct
58 Correct 412 ms 6348 KB Output is correct
59 Correct 371 ms 5908 KB Output is correct
60 Correct 410 ms 6000 KB Output is correct
61 Correct 535 ms 214116 KB Output is correct
62 Correct 527 ms 214116 KB Output is correct
63 Correct 507 ms 213988 KB Output is correct
64 Correct 662 ms 214140 KB Output is correct
65 Correct 638 ms 214180 KB Output is correct
66 Correct 671 ms 214012 KB Output is correct
67 Correct 454 ms 213612 KB Output is correct
68 Correct 437 ms 213692 KB Output is correct
69 Correct 412 ms 213588 KB Output is correct
70 Correct 475 ms 214036 KB Output is correct
71 Correct 431 ms 213992 KB Output is correct
72 Correct 465 ms 214008 KB Output is correct
73 Correct 498 ms 214188 KB Output is correct
74 Correct 450 ms 213964 KB Output is correct
75 Correct 443 ms 213960 KB Output is correct
76 Correct 512 ms 214704 KB Output is correct
77 Correct 459 ms 214092 KB Output is correct
78 Correct 486 ms 214352 KB Output is correct
79 Correct 328 ms 6304 KB Output is correct
80 Correct 332 ms 5964 KB Output is correct
81 Correct 324 ms 6000 KB Output is correct
82 Correct 537 ms 214600 KB Output is correct
83 Correct 567 ms 214348 KB Output is correct
84 Correct 495 ms 214008 KB Output is correct
85 Correct 495 ms 214056 KB Output is correct
86 Correct 469 ms 214288 KB Output is correct
87 Correct 470 ms 214372 KB Output is correct
88 Correct 390 ms 6360 KB Output is correct
89 Correct 392 ms 6380 KB Output is correct
90 Correct 383 ms 6044 KB Output is correct
91 Correct 401 ms 5960 KB Output is correct
92 Correct 374 ms 5972 KB Output is correct
93 Correct 360 ms 5948 KB Output is correct
94 Correct 423 ms 214032 KB Output is correct
95 Correct 406 ms 213844 KB Output is correct
96 Correct 380 ms 216516 KB Output is correct
97 Correct 370 ms 216408 KB Output is correct
98 Correct 389 ms 216844 KB Output is correct
99 Correct 405 ms 216724 KB Output is correct
100 Correct 501 ms 8816 KB Output is correct
101 Correct 438 ms 8788 KB Output is correct
102 Correct 454 ms 7932 KB Output is correct
103 Correct 445 ms 7844 KB Output is correct
104 Correct 450 ms 7568 KB Output is correct
105 Correct 437 ms 7552 KB Output is correct
106 Correct 515 ms 217728 KB Output is correct
107 Correct 467 ms 217588 KB Output is correct
108 Correct 414 ms 216556 KB Output is correct
109 Correct 479 ms 216444 KB Output is correct
110 Correct 444 ms 216924 KB Output is correct
111 Correct 456 ms 216916 KB Output is correct
112 Correct 400 ms 8904 KB Output is correct
113 Correct 422 ms 8832 KB Output is correct
114 Correct 386 ms 7924 KB Output is correct
115 Correct 391 ms 7904 KB Output is correct
116 Correct 365 ms 7544 KB Output is correct
117 Correct 379 ms 7648 KB Output is correct
118 Correct 467 ms 216328 KB Output is correct
119 Correct 425 ms 216320 KB Output is correct
120 Correct 419 ms 216180 KB Output is correct
121 Correct 475 ms 216296 KB Output is correct
122 Correct 427 ms 216300 KB Output is correct
123 Correct 422 ms 216248 KB Output is correct
124 Correct 433 ms 216236 KB Output is correct
125 Correct 410 ms 216340 KB Output is correct
126 Correct 449 ms 216192 KB Output is correct