Submission #65860

#	Time	Username	Problem	Language	Result	Execution time	Memory
65860		funcsr	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2033 ms	137496 KiB

bitaro

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
const int B = 100;

int N, M, Q;
vector<int> G[100000], Grev[100000];
int D[100000];
bool BAD[100000];
vector<P> dp[100000];
bool used[100000];

vector<P> filter(const vector<P> &seq) {
  vector<P> ret;
  for (P p : seq) if (!used[p._2]) ret.pb(p), used[p._2] = true;
  for (P p : seq) used[p._2] = false;
  if (ret.size() > B) ret.resize(B);
  return ret;
}

vector<P> merge(const vector<P> &a, const vector<P> &b) {
  vector<P> ret;
  int x = 0, y = 0;
  while (x<a.size() && y<b.size()) {
    if (a[x]>=b[y]) ret.pb(a[x++]);
    else ret.pb(b[y++]);
  }
  while (x<a.size()) ret.pb(a[x++]);
  while (y<b.size()) ret.pb(b[y++]);
  return filter(ret);
}

int solve(int s) {
  rep(i, N) D[i] = -1;
  D[s] = 0;
  int m = -1;
  for (int x=s; x>=0; x--) if (D[x] != -1) {
    if (!BAD[x]) m = max(m, D[x]);
    for (int t : Grev[x]) D[t] = max(D[t], D[x]+1);
  }
  return m;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M >> Q;
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].pb(b);
    Grev[b].pb(a);
  }
  rep(x, N) dp[x].pb(P(0, x));
  rep(x, N) {
    vector<P> seq(dp[x]);
    for (P &p : seq) p._1++;
    for (int t : G[x]) dp[t] = merge(dp[t], seq);
  }

  rep(i, Q) {
    int x, k;
    cin >> x >> k;
    x--;
    vector<int> bad(k);
    rep(i, k) cin >> bad[i], bad[i]--;
    for (int i : bad) BAD[i] = true;

    if (k < B) {
      int m = -1;
      for (P p : dp[x]) if (!BAD[p._2]) m = max(m, p._1);
      cout << m << "\n";
    }
    else {
      cout << solve(x) << "\n";
    }
    for (int i : bad) BAD[i] = false;
  }
  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (x<a.size() && y<b.size()) {
          ~^~~~~~~~~
bitaro.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (x<a.size() && y<b.size()) {
                        ~^~~~~~~~~
bitaro.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (x<a.size()) ret.pb(a[x++]);
          ~^~~~~~~~~
bitaro.cpp:51:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (y<b.size()) ret.pb(b[y++]);
          ~^~~~~~~~~

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