Submission #1205745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205745		minhpk	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1484 ms	454148 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
int a,b,q;
vector <int> z[1000005];
vector<pair<int,int>> lps[1000005];
int val[1000005];
int time1[1000005];
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 cnt[1000005];
int max1=-1;

void bfs(int i,int dem){
   for (int j=1;j<=a;j++){
        cnt[j]=0;
        if (del[j]==cur){
            cnt[j]=-1e9;    
        }
   }
  // for (int j=1;j<=i;j++){
  //     cout << cnt[j] << " ";
  // }
   for (int j=1;j<=i;j++){
        for (auto p:z[j]){
            cnt[j]=max(cnt[j],cnt[p]+1);
        }
   }
   if (cnt[i]>=0){
       max1=cnt[i];
   }
}

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){
            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;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:52:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   52 |          del[i]=1e16;
      |                 ^~~~

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