oj.uz

Submission #502498

# Submission time Handle Problem Language Result Execution time Memory
502498 2022-01-06T06:49:05 Z cs142857 Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 940 ms 420924 KB 
// JOI 2018, Bitaro’s Party

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

#ifdef DBG
  #define dbg 1
  #define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
  #define Dps(...) Dbgs(__VA_ARGS__)
#else
  #define dbg 0
  #define dpf(...) 42
  #define Dps(...) 42
#endif
 
#define SIZE(c) int((c).size())
#define FOR(i,l,r) for(int i = (l); i < (r); ++i)
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;

template <typename T> inline bool UpdateMax(T& x, T v) {
  if(v > x) {x=v; return 1;} else return 0;
}
template <typename T> inline bool UpdateMin(T& x, T v) {
  if(v < x) {x=v; return 1;} else return 0;
}

template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;

inline namespace output {
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) {
  return os << "{" << v.first << " " << v.second << "}";
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "{";
  bool first = 1;
  REP(x, v) {
    if(first) first=0; else os << " ";
    os << x;
  }
  return os << "}";
}
}  // namespace output

inline namespace output {  // Only for debug now.
template <class T>
void PrSep(std::ostream& os, string, const T& t) { os << t; }
template <class T, class... U>
void PrSep(std::ostream& os, string sep, const T& t, const U&... u) {
  PrSep(os, sep, t); os << sep; PrSep(os, sep, u...);
}

// Print w/ spaces, end with newline
void Ps() { cout << "\n"; }
template<class ...T> void Ps(const T&... t) { PrSep(cout," ",t...); Ps(); } 
template<class ...T> void Dbgs(const T&... t) { PrSep(cerr," ",t...); cerr << endl; } 
}  // namespace output

const int S = 320;

int n;
vector<VI> g, rg;

vector<vector<PI>> max_dis_u;

void Com() {
  int counter = 0;
  VI u_counter(n, 0);
  vector<PI> tmp;

  auto Merge = [&](const vector<PI>& prev, vector<PI>& target) {
    ++counter;
    auto p1 = prev.begin();
    auto p2 = target.begin();
    tmp.clear();
    while (SIZE(tmp) < S) {
      if (p1 == prev.end() && p2 == target.end()) break;
      int u, w;
      if (p2 == target.end() || (p1 != prev.end() && p1->fi + 1 > p2->fi)) {
        u = p1->se, w = p1->fi + 1;
        ++p1;
      } else {
        u = p2->se, w = p2->fi;
        ++p2;
      }
      if (u_counter[u] != counter) {
        u_counter[u] = counter;
        tmp.eb(w, u);
      }
    }
    target.swap(tmp);
  };

  max_dis_u.resize(n);
  FOR(i, 0, n) {
    max_dis_u[i] = {{0, i}};
    REP(prev, rg[i]) {
      Merge(max_dis_u[prev], max_dis_u[i]);
    }
    Dps("node", i);
    Dps(max_dis_u[i]);
  }
}

void Solve() {
  int m, nq;
  scanf("%d%d%d",&n,&m,&nq);
  g.assign(n, {});
  rg.assign(n, {});
  while(m--) {
    int u,v;
    scanf("%d%d",&u,&v);
    --u,--v;
    g[u].pb(v);
    rg[v].pb(u);
  }

  Com();

  VI mark(n, -1), mark2(n, -1);
  VI f(n);
  while (nq--) {
    int t, y;
    scanf("%d%d",&t,&y);
    --t;
    FOR(i, 0, y) {
      int x;
      scanf("%d", &x);
      --x;
      mark[x] = nq;
    }
    if(y < S) {
      int ans = -1;
      REP(p, max_dis_u[t]) if(mark[p.se]!=nq) {
        ans = p.fi;
        break;
      }
      printf("%d\n",ans);
    } else {
      int ans = -1;
      f[t] = 0, mark2[t] = nq;
      if (mark[t] != nq) UpdateMax(ans, f[t]);
      for (int i = t - 1; i >= 0; --i) {
        f[i] = -1, mark2[i] = nq;
        REP(v, g[i]) if(mark2[v]==nq && f[v]!=-1) {
          UpdateMax(f[i], f[v] + 1);
        }
        if (mark[i] != nq) UpdateMax(ans, f[i]);
      }
      printf("%d\n", ans);
    }
  }
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  for (int i = 1; i <= t; ++i) {
    // printf("Case #%d: ", i);
    Solve();
  }

  return 0;
}

Compilation message

bitaro.cpp: In function 'void Com()':
bitaro.cpp:37:20: warning: statement has no effect [-Wunused-value]
   37 |   #define Dps(...) 42
      |                    ^~
bitaro.cpp:139:5: note: in expansion of macro 'Dps'
  139 |     Dps("node", i);
      |     ^~~
bitaro.cpp:37:20: warning: statement has no effect [-Wunused-value]
   37 |   #define Dps(...) 42
      |                    ^~
bitaro.cpp:140:5: note: in expansion of macro 'Dps'
  140 |     Dps(max_dis_u[i]);
      |     ^~~
bitaro.cpp: In function 'void Solve()':
bitaro.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |   scanf("%d%d%d",&n,&m,&nq);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:151:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     scanf("%d%d",&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:163:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |     scanf("%d%d",&t,&y);
      |     ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:167:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |       scanf("%d", &x);
      |       ~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 944 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 5 ms 3740 KB Output is correct
9 Correct 6 ms 3772 KB Output is correct
10 Correct 5 ms 3748 KB Output is correct
11 Correct 6 ms 3336 KB Output is correct
12 Correct 4 ms 1836 KB Output is correct
13 Correct 5 ms 3148 KB Output is correct
14 Correct 4 ms 2600 KB Output is correct
15 Correct 3 ms 1484 KB Output is correct
16 Correct 4 ms 2508 KB Output is correct
17 Correct 4 ms 2864 KB Output is correct
18 Correct 3 ms 1740 KB Output is correct
19 Correct 4 ms 2864 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 944 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 5 ms 3740 KB Output is correct
9 Correct 6 ms 3772 KB Output is correct
10 Correct 5 ms 3748 KB Output is correct
11 Correct 6 ms 3336 KB Output is correct
12 Correct 4 ms 1836 KB Output is correct
13 Correct 5 ms 3148 KB Output is correct
14 Correct 4 ms 2600 KB Output is correct
15 Correct 3 ms 1484 KB Output is correct
16 Correct 4 ms 2508 KB Output is correct
17 Correct 4 ms 2864 KB Output is correct
18 Correct 3 ms 1740 KB Output is correct
19 Correct 4 ms 2864 KB Output is correct
20 Correct 360 ms 7668 KB Output is correct
21 Correct 312 ms 7628 KB Output is correct
22 Correct 342 ms 7592 KB Output is correct
23 Correct 400 ms 7704 KB Output is correct
24 Correct 525 ms 290056 KB Output is correct
25 Correct 521 ms 299964 KB Output is correct
26 Correct 543 ms 299084 KB Output is correct
27 Correct 632 ms 419388 KB Output is correct
28 Correct 598 ms 419424 KB Output is correct
29 Correct 613 ms 419264 KB Output is correct
30 Correct 544 ms 418212 KB Output is correct
31 Correct 598 ms 404652 KB Output is correct
32 Correct 570 ms 418136 KB Output is correct
33 Correct 444 ms 286012 KB Output is correct
34 Correct 430 ms 240728 KB Output is correct
35 Correct 443 ms 284932 KB Output is correct
36 Correct 545 ms 355260 KB Output is correct
37 Correct 521 ms 329920 KB Output is correct
38 Correct 503 ms 355748 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 944 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 5 ms 3740 KB Output is correct
9 Correct 6 ms 3772 KB Output is correct
10 Correct 5 ms 3748 KB Output is correct
11 Correct 6 ms 3336 KB Output is correct
12 Correct 4 ms 1836 KB Output is correct
13 Correct 5 ms 3148 KB Output is correct
14 Correct 4 ms 2600 KB Output is correct
15 Correct 3 ms 1484 KB Output is correct
16 Correct 4 ms 2508 KB Output is correct
17 Correct 4 ms 2864 KB Output is correct
18 Correct 3 ms 1740 KB Output is correct
19 Correct 4 ms 2864 KB Output is correct
20 Correct 360 ms 7668 KB Output is correct
21 Correct 312 ms 7628 KB Output is correct
22 Correct 342 ms 7592 KB Output is correct
23 Correct 400 ms 7704 KB Output is correct
24 Correct 525 ms 290056 KB Output is correct
25 Correct 521 ms 299964 KB Output is correct
26 Correct 543 ms 299084 KB Output is correct
27 Correct 632 ms 419388 KB Output is correct
28 Correct 598 ms 419424 KB Output is correct
29 Correct 613 ms 419264 KB Output is correct
30 Correct 544 ms 418212 KB Output is correct
31 Correct 598 ms 404652 KB Output is correct
32 Correct 570 ms 418136 KB Output is correct
33 Correct 444 ms 286012 KB Output is correct
34 Correct 430 ms 240728 KB Output is correct
35 Correct 443 ms 284932 KB Output is correct
36 Correct 545 ms 355260 KB Output is correct
37 Correct 521 ms 329920 KB Output is correct
38 Correct 503 ms 355748 KB Output is correct
39 Correct 609 ms 294292 KB Output is correct
40 Correct 580 ms 295444 KB Output is correct
41 Correct 535 ms 297612 KB Output is correct
42 Correct 742 ms 296092 KB Output is correct
43 Correct 561 ms 295792 KB Output is correct
44 Correct 399 ms 8980 KB Output is correct
45 Correct 420 ms 8040 KB Output is correct
46 Correct 345 ms 8048 KB Output is correct
47 Correct 422 ms 7940 KB Output is correct
48 Correct 377 ms 7708 KB Output is correct
49 Correct 658 ms 420540 KB Output is correct
50 Correct 581 ms 419424 KB Output is correct
51 Correct 370 ms 8712 KB Output is correct
52 Correct 358 ms 7912 KB Output is correct
53 Correct 585 ms 355592 KB Output is correct
54 Correct 548 ms 332092 KB Output is correct
55 Correct 541 ms 354608 KB Output is correct
56 Correct 513 ms 331796 KB Output is correct
57 Correct 376 ms 8772 KB Output is correct
58 Correct 420 ms 8804 KB Output is correct
59 Correct 362 ms 7848 KB Output is correct
60 Correct 370 ms 7936 KB Output is correct
61 Correct 690 ms 419476 KB Output is correct
62 Correct 611 ms 355512 KB Output is correct
63 Correct 653 ms 330444 KB Output is correct
64 Correct 940 ms 419360 KB Output is correct
65 Correct 836 ms 354460 KB Output is correct
66 Correct 838 ms 331372 KB Output is correct
67 Correct 575 ms 419332 KB Output is correct
68 Correct 507 ms 355268 KB Output is correct
69 Correct 536 ms 328892 KB Output is correct
70 Correct 609 ms 419488 KB Output is correct
71 Correct 554 ms 355484 KB Output is correct
72 Correct 547 ms 331008 KB Output is correct
73 Correct 626 ms 419488 KB Output is correct
74 Correct 552 ms 355580 KB Output is correct
75 Correct 552 ms 331360 KB Output is correct
76 Correct 627 ms 420924 KB Output is correct
77 Correct 614 ms 419608 KB Output is correct
78 Correct 592 ms 419652 KB Output is correct
79 Correct 354 ms 8940 KB Output is correct
80 Correct 333 ms 8072 KB Output is correct
81 Correct 332 ms 7588 KB Output is correct
82 Correct 619 ms 419664 KB Output is correct
83 Correct 619 ms 406492 KB Output is correct
84 Correct 592 ms 418420 KB Output is correct
85 Correct 581 ms 404824 KB Output is correct
86 Correct 592 ms 418364 KB Output is correct
87 Correct 602 ms 405564 KB Output is correct
88 Correct 370 ms 9028 KB Output is correct
89 Correct 389 ms 8876 KB Output is correct
90 Correct 369 ms 7920 KB Output is correct
91 Correct 383 ms 8040 KB Output is correct
92 Correct 375 ms 7640 KB Output is correct
93 Correct 361 ms 7772 KB Output is correct
94 Correct 547 ms 288284 KB Output is correct
95 Correct 485 ms 240956 KB Output is correct
96 Correct 518 ms 285080 KB Output is correct
97 Correct 452 ms 243484 KB Output is correct
98 Correct 448 ms 285628 KB Output is correct
99 Correct 450 ms 242628 KB Output is correct
100 Correct 412 ms 8900 KB Output is correct
101 Correct 393 ms 8904 KB Output is correct
102 Correct 370 ms 8128 KB Output is correct
103 Correct 386 ms 8004 KB Output is correct
104 Correct 388 ms 7760 KB Output is correct
105 Correct 366 ms 7644 KB Output is correct
106 Correct 563 ms 355976 KB Output is correct
107 Correct 569 ms 332504 KB Output is correct
108 Correct 526 ms 356076 KB Output is correct
109 Correct 612 ms 330916 KB Output is correct
110 Correct 564 ms 355992 KB Output is correct
111 Correct 565 ms 331584 KB Output is correct
112 Correct 378 ms 9008 KB Output is correct
113 Correct 382 ms 8920 KB Output is correct
114 Correct 339 ms 8096 KB Output is correct
115 Correct 418 ms 7988 KB Output is correct
116 Correct 340 ms 7608 KB Output is correct
117 Correct 356 ms 7548 KB Output is correct
118 Correct 601 ms 419388 KB Output is correct
119 Correct 515 ms 356068 KB Output is correct
120 Correct 506 ms 330640 KB Output is correct
121 Correct 603 ms 419628 KB Output is correct
122 Correct 516 ms 354816 KB Output is correct
123 Correct 550 ms 330768 KB Output is correct
124 Correct 582 ms 419368 KB Output is correct
125 Correct 551 ms 356156 KB Output is correct
126 Correct 565 ms 329628 KB Output is correct