Submission #502500

#	Time	Username	Problem	Language	Result	Execution time	Memory
502500		cs142857	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	708 ms	267792 KiB

bitaro

// 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();
    tmp.reserve(S);
    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 (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86