Submission #1205724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205724		minhpk	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	24 ms	48196 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,q;
vector <int> z[1000005];
vector<pair<int,int>> lps[1000005];
int val[1000005];
int time1[100005];
int block;
int cur=0;
bool cmp(pair<int,int> a,pair<int,int> b){
    return a.second>b.second;
}
int del[1000005];
bool vis[1000005];
int max1=-1;

void bfs(int i,int dem){
    queue<pair<int,int>> q;
    q.push({i,0});
    vis[i]=true;
    while (q.size()){
         pair<int,int> pos=q.front();
         q.pop();
         int val=pos.second;
         int pos1=pos.first;
         if (del[pos1]!=cur){
             max1=max(max1,val);
         }
         for (auto p:z[pos1]){
              if (vis[p]){
                continue;
              }
              vis[p]=true;
              q.push({p,val+1});
         }
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> q;
    block=321;
    for (int i=1;i<=b;i++){
         int x,y;
         cin >> x >> y;
         z[y].push_back(x);
    }

    for (int i=1;i<=a;i++){
         del[i]=1e16;
         vector <int> v;
         val[i]=0;
         time1[i]=i;
         v.push_back(i);
         for (auto p:z[i]){
             for (auto p1:lps[p]){
                  if (time1[p1.first]!=i){
                      time1[p1.first]=i;
                      val[p1.first]=p1.second+1;
                      v.push_back(p1.first);
                  }else{
                      val[p1.first]=max(val[p1.first],p1.second+1);
                  }
             }
         }
         for (auto p:v){
              lps[i].push_back({p,val[p]});
         }
         sort(lps[i].begin(),lps[i].end(),cmp);
         int k=lps[i].size();
         while (k>block){
               lps[i].pop_back();
               k--;
         }
    }

   // for (int i=1;i<=a;i++){
   //      cout << lps[i][0].second << " ";
   // }
   // cout << "\n";
    while (q--){
        cur=q;
        int t,x;
        cin >> t >> x;
        for (int i=1;i<=x;i++){
             int y;
             cin >> y;
             del[y]=cur;
        }
        if (x>block-1){
            for (int i=1;i<=a;i++){
                 vis[i]=false;
            }
            max1=-1;
            bfs(t,0);
            cout << max1 << "\n";
        }else{
            int ans=-1;
            for (auto p:lps[t]){
                 if (del[p.first]!=cur){
                     ans=p.second;
                     break;
                 }
            }
            cout << ans << "\n";
        }
    }


    return 0;
}

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