Submission #436457

#	Time	Username	Problem	Language	Result	Execution time	Memory
436457		peijar	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1782 ms	176268 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;
const int TRESH = 200;

vector<int> adj[MAXN];
bitset<MAXN> seen;
vector<int> revAdj[MAXN];
vector<pair<int, int>> furthest[MAXN];
int buffer[MAXN];
int nbSommets, nbAretes;

int dp[MAXN];

void naiveDp(int source) {
  for (int i = 0; i < nbSommets; ++i)
    dp[i] = -1;
  dp[source] = 0;
  for (int iSommet = source - 1; iSommet >= 0; --iSommet)
    for (auto iFils : adj[iSommet])
      if (dp[iFils] >= 0)
        dp[iSommet] = max(dp[iSommet], dp[iFils] + 1);
}

void init() {

  auto combine = [&](const vector<pair<int, int>> &lft,
                     const vector<pair<int, int>> &rgt) {
    vector<pair<int, int>> ret;
    int lftSize = lft.size(), rgtSize = rgt.size();
    ret.reserve(min(lftSize + rgtSize, TRESH));
    int posDel = 0;
    int posLft = 0, posRgt = 0;
    for (int i = 0;
         (posLft < lftSize or posRgt < rgtSize) and (int) ret.size() < TRESH;
         ++i) {
      if (posLft < lftSize and seen[lft[posLft].first]) {
        ++posLft;
        continue;
      }
      if (posRgt < rgtSize and seen[rgt[posRgt].first]) {
        ++posRgt;
        continue;
      }
      if (posRgt == rgtSize or
          (posLft < lftSize and lft[posLft].second > rgt[posRgt].second)) {
        buffer[posDel++] = lft[posLft].first;
        seen[lft[posLft].first] = true;
        ret.push_back(lft[posLft++]);
      } else {
        buffer[posDel++] = rgt[posRgt].first;
        seen[rgt[posRgt].first] = true;
        ret.push_back(rgt[posRgt++]);
      }
    }
    while (posDel > 0)
      seen[buffer[--posDel]] = false;
    return ret;
  };

  for (int iSommet = 0; iSommet < nbSommets; ++iSommet) {
    vector<pair<int, int>> cur;
    for (int iPere : revAdj[iSommet])
      cur = combine(cur, furthest[iPere]);
    for (auto &[u, d] : cur)
      d++;
    if ((int)cur.size() < TRESH)
      cur.emplace_back(iSommet, 0);
    furthest[iSommet] = move(cur);
  }
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbRequetes;
  cin >> nbSommets >> nbAretes >> nbRequetes;
  for (int i = 0; i < nbAretes; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    revAdj[v].push_back(u);
  }

  init();

  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int source, nbInterdits;
    cin >> source >> nbInterdits;
    --source;
    set<int> interdits;
    for (int i = 0; i < nbInterdits; ++i) {
      int u;
      cin >> u;
      interdits.insert(u - 1);
    }
    assert((int)interdits.size() == nbInterdits);
    if (nbInterdits >= TRESH) {
      naiveDp(source);
      int sol = -1;
      for (int i = 0; i < nbSommets; ++i)
        if (dp[i] > sol and !interdits.count(i))
          sol = dp[i];
      cout << sol << '\n';
    } else {
      int ret = -1;
      assert(interdits.size() < TRESH);
      for (int i = 0; i < (int)furthest[source].size(); ++i)
        if (!interdits.count(furthest[source][i].first)) {
          ret = furthest[source][i].second;
          break;
        }
      cout << ret << '\n';
    }
  }
}

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