Submission #436166

#	Time	Username	Problem	Language	Result	Execution time	Memory
436166		peijar	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2089 ms	91228 KiB

bitaro

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

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

vector<int> adj[MAXN];
vector<int> revAdj[MAXN];
vector<pair<int, int>> furthest[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() {
  for (int iSommet = 0; iSommet < nbSommets; ++iSommet) {
    priority_queue<tuple<int, int, int>> pq;
    set<int> used;
    for (auto v : revAdj[iSommet]) {
      assert(!furthest[v].empty());
      auto [u, d] = furthest[v].back();
      pq.emplace(d, v, (int)furthest[v].size() - 1);
    }

    for (int iter = 0; (int)furthest[iSommet].size() < TRESH and !pq.empty();
         ++iter) {
      auto [dis, from, id] = pq.top();
      pq.pop();
      if (!used.count(furthest[from][id].first)) {
        furthest[iSommet].emplace_back(furthest[from][id].first,
                                       furthest[from][id].second + 1);
        used.insert(furthest[from][id].first);
      }
      if (id > 0)
        pq.emplace(furthest[from][id - 1].second, from, id - 1);
    }
    if ((int)furthest[iSommet].size() < TRESH)
      furthest[iSommet].emplace_back(iSommet, 0);
    reverse(furthest[iSommet].begin(), furthest[iSommet].end());
  }
}

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) {
      if (iRequete == 6)
        cerr << "GREATER" << endl;
      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 {
      if (iRequete == 6) {
        cerr << "LESS" << ' ' << TRESH - furthest[source].size() << endl;
        for (auto v : interdits)
          cerr << v << ' ';
        cerr << endl;
        for (auto [u, v] : furthest[source])
          cerr << u << ' ';
        cerr << endl;
      }
      int ret = -1;
      assert(interdits.size() < TRESH);
      for (int i = (int)furthest[source].size() - 1; i >= 0; --i) {
        if (!interdits.count(furthest[source][i].first)) {
          ret = furthest[source][i].second;
          break;
        }
      }
      if (iRequete == 6 and (int) furthest[source].size() == TRESH)
        assert(ret != -1);
      cout << ret << '\n';
    }
  }
}

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