Submission #1365770

#TimeUsernameProblemLanguageResultExecution timeMemory
1365770kiloxxBitaro’s Party (JOI18_bitaro)C++17
0 / 100
4 ms5708 KiB
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n,m,q;
vector<int> adj[maxn];
vector<pair<int,int>> path[maxn];
int S = 130;
bool used[maxn];
void init(){
     cin >> n >> m >> q;
     for (int i=0;i<m;i++){
          int u,v; cin >> u >> v;
          adj[u].push_back(v);
     }
     for (int i=1;i<=n;i++) path[i].push_back({0,i});
     for (int i=1;i<=n;i++){
          for (int j:adj[i]){
               for (auto [dist,k]: path[i]){
                    path[j].push_back({dist+1,k});
               }
               sort(path[j].begin(),path[j].end(),greater<pair<int,int>>());
               vector<pair<int,int>> v;
               for (int k=0;k<path[j].size();k++){
                    if (used[path[j][k].second]) continue;
                    v.push_back(path[j][k]);
                    used[path[j][k].second] = true;
                    if (v.size()==S) break;
               }
               for (auto k:v){
                    used[k.second] = false;
               }
               path[j] = v;
          }

     }
}
bool busy[maxn];
int cnt = 0;
int getDist(int u){
     vector<int> dp(n+1,-1);
     for (int i=1;i<=n;i++){
          if (!busy[i]) dp[i] = max(dp[i],0);
          for (int j:adj[i]){
               dp[j] = max(dp[j],dp[i]+1);
          }
     }
     return dp[u];
}

void process(){
     while (q--){
          int u,cntBusy; cin >> u >> cntBusy;
          vector<int> busyNode(cntBusy);
          for (int i=0;i<cntBusy;i++){
               cin >> busyNode[i];
               busy[busyNode[i]] = true;
          }
          if (cntBusy >= S){
               cout << getDist(u) << '\n';
          }
          else {
               int ans = -1;
               for (auto [dist,v]:path[u]){
                    if (!busy[v]){
                         ans = dist;
                         break;
                    }
               }
               cout << ans << '\n';
          }
          for (int i:busyNode) busy[i] = false;
     }
}


int main(){
     ios::sync_with_stdio(NULL);
     cin.tie(NULL); cout.tie(NULL);
     init();
     process();
     return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...