Submission #1042787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042787		pera	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	685 ms	215756 KiB

bitaro

#include<bits/stdc++.h>
#define pii pair<int , int>
using namespace std;
const int N = 1e5 + 1 , B = 200;
int n , m , q;
vector<int> e(N) , d(N) , f(N);
vector<vector<int>> g(N);
vector<vector<pii>> v(N);
vector<pii> merge(vector<pii> x , vector<pii> y){
   vector<pii> z;
   int px = 0 , py = 0;
   while((int)z.size() <= B && px + py < (int)x.size() + (int)y.size()){
      while(px < (int)x.size() && f[x[px].second]){
         ++px;
      }
      while(py < (int)y.size() && f[y[py].second]){
         ++py;
      }
      if(px < (int)x.size() && (py == (int)y.size() || x[px].first > y[py].first + 1)){
         f[x[px].second] = 1;
         z.push_back(x[px++]);
      }else if(py < (int)y.size()){
         f[y[py].second] = 1;
         z.push_back({y[py].first + 1 , y[py++].second});
      }
   }
   for(auto [D , x] : z){
      f[x] = 0;
   }
   return z;
}
int main(){
   cin >> n >> m >> q;
   for(int i = 1;i <= m;i ++){
      int u , v;
      cin >> u >> v;
      g[v].push_back(u);
   }
   for(int u = 1;u <= n;u ++){
      v[u].push_back({0 , u});
      for(int x : g[u]){
         v[u] = merge(v[u] , v[x]);
      }
   }
   while(q--){
      int t , y;
      cin >> t >> y;
      vector<int> o(y);
      for(int i = 0;i < y;i ++){
         cin >> o[i];
         e[o[i]] = 1;
      }
      if(y < B){
         int ans = -1;
         for(auto [D , x] : v[t]){
            if(!e[x]){
               ans = D;
               break;
            }
         }
         cout << ans << endl;
      }else{
         for(int u = 1;u <= n;u ++){
            d[u] = 0;
         }
         for(int i = 0;i < y;i ++){
            d[o[i]] = -1e9;
         }
         for(int u = 1;u <= n;u ++){
            for(int v : g[u]){
               d[u] = max(d[u] , d[v] + 1);
            }
         }
         cout << max(-1 , d[t]) << endl;
      }
      for(int i = 0;i < y;i ++){
         e[o[i]] = 0;
      }
   }
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:24:45: warning: operation on 'py' may be undefined [-Wsequence-point]
   24 |          z.push_back({y[py].first + 1 , y[py++].second});
      |                                           ~~^~

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