Submission #886288

#	Time	Username	Problem	Language	Result	Execution time	Memory
886288		amirhoseinfar1385	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	988 ms	351408 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+5,maxm=200000+5,sq=sqrt(100000+5);
int n,m,q;
vector<int>adj[maxn];
int fp[maxn];
deque<pair<int,int>>res[maxn];

void merge(int u,int v){
	for(auto x:res[u]){
		fp[x.first]=1;
	}
	for(auto x:res[v]){
		fp[x.first]=1;
	}
	deque<pair<int,int>>fake;
	int cnt=0;
	int ii=res[u].size()-1,jj=res[v].size()-1;
    while(cnt<=sq&&!(ii<0&&jj<0)){
        pair<int,int>x;
        if(ii<0){
            x=res[v][jj];
            jj--;
        }
        else if(jj<0){
            x=res[u][ii];
            x.second++;
            ii--;
        }
        else if(res[u][ii].second+1>res[v][jj].second){
            x=res[u][ii];
            x.second++;
            ii--;
        }
        else{
            x=res[v][jj];
            jj--;
        }
        if(fp[x.first]==0){
            continue;
        }
        cnt++;
        fp[x.first]=0;
        fake.push_front(x);
    }
    res[v].swap(fake);
}

void pre(){
	for(int i=1;i<=n;i++){
		res[i].push_back(make_pair(i,0));
		for(auto x:adj[i]){
			merge(x,i);
		}
	}
}
int sqq[sq+2];

int solvel(int u,int v,int t){
	int alliq[v];
	for(int i=0;i<v;i++){
		cin>>alliq[i];
	    for(int j=0;j<(int)res[u].size();j++){
	        if(res[u][j].first==alliq[i]){
	            sqq[j]=t;
	            break;
	        }
	    }
	}
	int jj=res[u].size()-1;
	while(true){
	    if(jj==-1){
	        return -1;
	    }
	    if(sqq[jj]==t){
	        jj--;
	        continue;
	    }
	    return res[u][jj].second;
	}
}

int solveh(int u,int v){
    int all[v+1];
    for(int i=0;i<v;i++){
        cin>>all[i];
    }
    all[v]=n+2;
    int j=0;
    vector<int>dp(n+1,-1);
    for(int i=1;i<=u;i++){
        if(i==all[j]){
            j++;
        }
        else{
            dp[i]=0;
        }
        for(auto x:adj[i]){
            if(dp[x]!=-1){
                dp[i]=max(dp[x]+1,dp[i]);
            }
        }
    }
    return dp[u];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		adj[v].push_back(u);
	}
	pre();
	for(int i=0;i<q;i++){
		int u,v;
		cin>>u>>v;
		if(v<sq){
			cout<<solvel(u,v,i+1)<<"\n";
		}
		else{
			cout<<solveh(u,v)<<"\n";
		}
	}
}

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