제출 #1365768

#제출 시각아이디문제언어결과실행 시간메모리
1365768kiloxxBitaro’s Party (JOI18_bitaro)C++17
0 / 100
4 ms5700 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]){
               vector<pair<int,int>> v;
               for (auto [dist,k]: path[i]){
                    v.push_back({dist+1,k});
               }
               sort(v.begin(),v.end(),greater<pair<int,int>>());
               int cnt = 0;
               for (int i=0;i<v.size();i++){
                    if (used[v[i].second]) continue;
                    path[j].push_back(v[i]);
                    used[v[i].second] = true;
                    if (path[j].size()==S) break;
               }
               for (int i=0;i<=n;i++) used[i] = false;
          }

     }
}
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;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…