Submission #436122

#	Time	Username	Problem	Language	Result	Execution time	Memory
436122		peijar	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1500 ms	421592 KiB

bitaro

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

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

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

vector<int> naiveDp(int source) {
  vector<int> dp(nbSommets, -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);
  return dp;
}

void init() {
  for (int iSommet = 0; iSommet < nbSommets; ++iSommet) {
    priority_queue<tuple<int, int, int>> pq;
    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; iter < TRESH and !pq.empty(); ++iter) {
      auto [dis, from, id] = pq.top();
      pq.pop();
      furthest[iSommet].emplace_back(furthest[from][id].first,
                                     furthest[from][id].second + 1);
      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);
    }
    if (nbInterdits >= TRESH) {
      auto dp = 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;
      for (int i = (int)furthest[source].size() - 1; i >= 0; --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: 0 / 86