제출 #1200936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200936		Warinchai	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1131 ms	428976 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
vector<int>qr[200005];
vector<int>adj[200005];
vector<int>rv[200005];
int vis[200005];
int ar[200005];
int cant[200005];
int n,m,q;
int mx[200005];
int root=320;
int inf=1e6;
int big(int x,vector<int>&v){
    //cerr<<x<<":\n";
    for(int i=1;i<=n;i++)mx[i]=-inf,cant[i]=0;
    for(auto x:v)cant[x]=1;
    mx[x]=0;
    int ans=-1;
    for(int i=x;i>=1;i--){
        //cerr<<mx[i]<<" ";
        if(!cant[i])ans=max(ans,mx[i]);
        for(auto v:rv[i])mx[v]=max(mx[v],mx[i]+1);
    }
    for(auto x:v)cant[x]=0;
    //cerr<<"\n";
    return ans;
}
vector<pair<int,int>>tans[100005];
vector<pair<int,int>> merge(vector<pair<int,int>>a,vector<pair<int,int>>b){
    vector<pair<int,int>>c;
    vector<int>del;
    int i=0,j=0;
    //cerr<<"in merge\n";
    while(i<a.size()||j<b.size()){
        if(i==a.size()){
            for(;j<b.size();j++)if(!vis[b[j].second])c.push_back(b[j]),vis[b[j].second]++,del.push_back(b[j].second);
            break;
        }
        if(j==b.size()){
            for(;i<a.size();i++)if(!vis[a[i].second])c.push_back(a[i]),vis[a[i].second]++,del.push_back(a[i].second);
            break;
        }
        if(a[i]>b[j]){
            if(!vis[a[i].second])c.push_back(a[i]),vis[a[i].second]++,del.push_back(a[i].second);
            i++;
        }
        else{
            if(!vis[b[j].second])c.push_back(b[j]),vis[b[j].second]++,del.push_back(b[j].second);
            j++;
        }
    }
    while(c.size()>root+1)c.pop_back();
    for(auto x:del)vis[x]=0;
    return c;
}

void upd(int x){
    for(auto &p:tans[x])p.first++;
    tans[x].push_back({0,x});
    //cerr<<"tans "<<x<<"\n";
    //for(auto v:tans[x])cerr<<v.first<<" "<<v.second<<"\n";
    //cerr<<"upd work\n";
    for(auto v:adj[x]){
        tans[v]=merge(tans[v],tans[x]);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int s,e;cin>>s>>e;
        adj[s].push_back(e);
        rv[e].push_back(s);
    }
    for(int i=0;i<q;i++){
        int t,y;cin>>t>>y;
        ar[i]=t;
        for(int j=0;j<y;j++){
            int x;cin>>x;
            qr[i].push_back(x);
        }
    }
    //cerr<<"work\n";
    for(int i=1;i<=n;i++)upd(i);
    //cerr<<"work\n";
    for(int i=0;i<q;i++){
        if(qr[i].size()>root){
            cout<<big(ar[i],qr[i])<<"\n";
        }else{
            int ans=-1;
            for(auto x:qr[i])cant[x]=1;
            for(auto x:tans[ar[i]]){
                if(!cant[x.second]){
                    ans=x.first;
                    break;
                }
            }
            for(auto x:qr[i])cant[x]=0;
            cout<<ans<<"\n";
        }
    }
}

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