제출 #1319466

#제출 시각아이디문제언어결과실행 시간메모리
1319466Ahmed_SolymanBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1119 ms416792 KiB
#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
const int N=1e5+5,B=316;
vector<int>adj[N];
vector<pair<int,int>>vec[N];
int dp[N];
bool vis[N];
int temp[N];
bool deleted[N];
bool g[N];
vector<int>dist[N];
void dfs(int node){
    vis[node]=1;
    for(auto i:adj[node])
        if(!vis[i])
            dfs(i);
    vector<int>k;
    for(auto i:adj[node])
        for(auto j:vec[i])
            temp[j.first]=max(temp[j.first],j.second+1),k.push_back(j.first);
    k.push_back(node);
    int mx=0;
    for(auto i:k){
        if(!g[i]){
            g[i]=1;
            dist[temp[i]].push_back(i);
            mx=max(mx,temp[i]);
        }
    }
    for(int i=mx;i>=0;i--){
        for(auto j:dist[i]){
            if(vec[node].size()==B)break;
            vec[node].push_back({j,i});
        }
        if(vec[node].size()==B)break;
    }
    for(auto i:k){
        g[i]=0;
        dist[temp[i]].clear();
        temp[i]=0;
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    fast
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfs(i);
    while(q--){
        int t,y;
        cin>>t>>y;
        vector<int>c;
        for(int i=0;i<y;i++){
            int x;
            cin>>x;
            if(x<=t)c.push_back(x),deleted[x]=1;
        }
        y=c.size();
        if(y<B){
            int ans=-1;
            for(auto i:vec[t]){
                if(!deleted[i.first]){
                    ans=i.second;
                    break;
                }
            }
            cout<<ans<<endl;
        }
        else{
            fil(dp,-1);
            for(int i=1;i<=t;i++){
                if(!deleted[i])dp[i]=0;
                for(auto j:adj[i])
                    dp[i]=max(dp[i],(dp[j]>0?dp[j]+1:deleted[j]?deleted[i]*-1:1));
            }
            cout<<dp[t]<<endl;
        }
        for(auto i:c)deleted[i]=0;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...