Submission #43985

#	Time	Username	Problem	Language	Result	Execution time	Memory
43985		ruhanhabib39	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1927 ms	300920 KiB

bitaro

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

const int MAXN = 1e5;
const int BLOCK = 320;

int N, M, Q;
vector<int> to[MAXN + 10];

struct dat {
   int w, u;
   dat(int w_, int u_) : w(w_), u(u_) {}
   dat(const dat& d) : w(d.w), u(d.u) {}
   // datA before datB if datA.w > datB.w
   bool operator<(dat d) const {
      if(w == d.w) return u < d.u;
      return w > d.w;
   }
};

vector<int> from[MAXN + 10];

int qi = 0;
int bad[MAXN + 10];


int dp[MAXN + 10];

int solve1(int V) {
   for(int v = 1; v <= V; v++) {
      if(bad[v] != qi) dp[v] = 0;
      else dp[v] = -1e9;
      for(int u : from[v]) {
         dp[v] = max(dp[v], 1 + dp[u]);
      }
   }
   if(dp[V] < 0) dp[V] = -1;
   return dp[V];
}

vector<dat> best[MAXN + 10];
int done[MAXN + 10], di = 0;

void work(int u) {
   vector<dat> cp(best[u].begin(), best[u].end());
   for(dat& it : cp) it.w++;

   for(int v : to[u]) {
      auto mIt = best[v].insert(best[v].end(), cp.begin(), cp.end());
      inplace_merge(best[v].begin(), mIt, best[v].end());
      
      vector<dat> cpV; cpV.reserve(BLOCK);
      ++di;
      for(auto it : best[v]) {
         if(done[it.u] < di) {
            done[it.u] = di;
            cpV.push_back(it);
         }
         if(cpV.size() >= BLOCK) break;
      }
      best[v].swap(cpV);
   }
}

int solve2(int V) {
   for(auto& it : best[V]) {
      if(bad[it.u] != qi) return it.w;
   }
   if(bad[V] != qi) return 0;
   return -1;
}

int main() {
   assert(scanf("%d%d%d", &N, &M, &Q) == 3);
   for(int i = 0; i < M; i++) {
      int u, v; assert(scanf("%d%d", &u, &v) == 2);
      to[u].push_back(v);
      from[v].push_back(u);
   }
   for(int u = 1; u <= N; u++) {
      best[u].emplace_back(0, u);
   }
   for(int u = 1; u <= N; u++) {
      work(u);
   }
   for(qi = 1; qi <= Q; qi++) {
      int dest, badc;
      assert(scanf("%d%d", &dest, &badc) == 2);
      for(int i = 0; i < badc; i++) {
         int v; assert(scanf("%d", &v) == 1);
         bad[v] = qi;
      }
      int res = -1;
      if(badc >= BLOCK) res = solve1(dest);
      else res = solve2(dest);
      printf("%d\n", res);
   }
}

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