Submission #1155392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155392		AlgorithmWarrior	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	745 ms	411104 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e5+5;
int const SQRT=316;
int const INF=1e9;
int n,m,q;
vector<int>in[MAX];
struct path{
    int nod,cnt;
};
vector<path>precalc[MAX];

void read(){
    cin>>n>>m>>q;
    int i;
    for(i=1;i<=m;++i){
        int s,e;
        cin>>s>>e;
        in[e].push_back(s);
    }
}

bool folosit[MAX];

void merge_(vector<path>&dest,vector<path>v1,vector<path>v2){
    dest.clear();
    int id1=0,id2=0;
    while(id1<(int)v1.size() && id2<(int)v2.size()){
        if(v1[id1].cnt>=v2[id2].cnt){
            if(!folosit[v1[id1].nod]){
                folosit[v1[id1].nod]=1;
                dest.push_back(v1[id1]);
            }
            ++id1;
        }
        else{
            if(!folosit[v2[id2].nod]){
                folosit[v2[id2].nod]=1;
                dest.push_back(v2[id2]);
            }
            ++id2;
        }
    }
    while(id1<(int)v1.size()){
        if(!folosit[v1[id1].nod]){
            folosit[v1[id1].nod]=1;
            dest.push_back(v1[id1]);
        }
        ++id1;
    }
    while(id2<(int)v2.size()){
        if(!folosit[v2[id2].nod]){
            folosit[v2[id2].nod]=1;
            dest.push_back(v2[id2]);
        }
        ++id2;
    }
    for(auto [nod,cnt] : dest)
        folosit[nod]=0;
    while((int)dest.size()>SQRT+1)
        dest.pop_back();
}

void do_precalc(){
    int i;
    for(i=1;i<=n;++i){
        for(auto vec : in[i]){
            vector<path>aux=precalc[vec];
            for(auto &[nod,cnt] : aux)
                ++cnt;
            merge_(precalc[i],precalc[i],aux);
        }
        if(precalc[i].size()<=SQRT)
            precalc[i].push_back({i,0});
    }
}

bool ocupat[MAX];

int query_mic(int party,vector<int>busy){
    for(auto nod : busy)
        ocupat[nod]=1;
    int answer=-1;
    for(auto [nod,cnt] : precalc[party])
        if(!ocupat[nod]){
            answer=cnt;
            break;
        }
    for(auto nod : busy)
        ocupat[nod]=0;
    return answer;
}

int dp[MAX];

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

int query_mare(int party,vector<int>busy){
    for(auto nod : busy)
        ocupat[nod]=1;
    int i;
    for(i=1;i<=party;++i){
        if(ocupat[i])
            dp[i]=-INF;
        else
            dp[i]=0;
        for(auto vec : in[i])
            maxself(dp[i],dp[vec]+1);
    }
    maxself(dp[party],-1);
    for(auto nod : busy)
        ocupat[nod]=0;
    return dp[party];
}

void process_queries(){
    while(q--){
        int party,sz;
        cin>>party>>sz;
        vector<int>busy;
        int i;
        for(i=1;i<=sz;++i){
            int ocup;
            cin>>ocup;
            busy.push_back(ocup);
        }
        if(sz<=SQRT)
            cout<<query_mic(party,busy)<<'\n';
        else
            cout<<query_mare(party,busy)<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    do_precalc();
    process_queries();
    return 0;
}

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