Submission #656152

#	Time	Username	Problem	Language	Result	Execution time	Memory
656152		nolimiya	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	821 ms	221368 KiB

bitaro

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//agha moosa mam baladim
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-funroll-loops")
using namespace std;
#define pi pair<int , int>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 2e5 + 4;
const long long mod = 1e9 + 7 ;
typedef long long ll;
int l,r,mid;
int n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm],gos[maxm];
ll pedaret[maxm];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<pi> st;
ll rp[maxm];
//ll rw[maxm][maxm];
map<ll,ll> mp;
const int sq = 518/2;
pi w[maxm][sq];
pi dp[sq*2+1];
void merge(int x, int y){
    ss=mm=0;
    while(mm<sq||ss<sq){
        if(ss==sq||(mm<sq&&w[y][mm].first>w[x][ss].first+1)) dp[ss+mm]=w[y][mm] , mm++;
        else dp[ss+mm]=w[x][ss] , dp[ss+mm].first++ , ss++;
    }
    //cout<<66;
    mid = 0;
    for(int i=0; i<2*sq&&mid<sq; i++){
        if(dp[i].second!=-1&&!vis[dp[i].second]) w[y][mid++]=dp[i] , vis[dp[i].second]=1;// , mid+=dp[i];
    }
    //cout<<67;
    for(int i=0; i<2*sq; i++) if(dp[i].second!=-1) vis[dp[i].second]=0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int q;
    cin >>n>>m>>q;
    for(int i=0; i<m; i++){
        cin >>l>>r,l--,r--;
        g[r].push_back(l);
    }
    for(int i=0; i<n; i++){
        for (int j=0; j<sq; j++) w[i][j] = {-1,-1};
        w[i][0]=pi{0,i};
        for(auto x:g[i]) merge(x,i);
    }
    //cout<<65;
    while(q--){
        cin>>l>>r;
        l--;
        vector<int> vec(r);
        for(int i=0; i<r; i++){
            cin>>vec[i];
            vec[i]--;
            gos[vec[i]]=1;
        }
        vec.shrink_to_fit();
        mid=-1;
        if(r>=sq){
            for(int i=0; i<=l; i++){
                if(gos[i]) pedaret[i]=-1;
                else pedaret[i]=0;
                for(auto x:g[i]){
                    if(pedaret[x]!=-1) pedaret[i]=max(pedaret[i],pedaret[x]+1);
                    //cout<<pedaret[i]<<" "<<pedaret[x]<<endl;
                }
            }
            mid=pedaret[l];
        }
        else{
            for(int i=0; i<sq; i++) if(!gos[w[l][i].second]){ 
                mid=max(mid,w[l][i].first);
                //cout<<i<<" "<<mid<<endl;
            }
        }
        for(auto x:vec) gos[x]=0;
        cout<<mid<<'\n';
    }
}

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