Submission #1024292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024292		boyliguanhan	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1463 ms	86260 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>bst[100100];
vector<int>adj[100100],radj[100100];
int towns;
bitset<100100>stuv;
int brute(int tw,vector<int>cant){
    vector<int>mx(towns+1,0);
    for(auto i:cant)
        mx[i]=-1e9;
    for(int i=1;i<towns;i++)
        for(auto x:adj[i])
            mx[x]=max(mx[x],mx[i]+1);
    return max(-1,mx[tw]);
}
int dob(vector<int>cant,int tw){
    int ans=-1;
    for(auto i:cant)
        stuv[i]=1;
    for(auto [x,k]:bst[tw]) 
        if(!stuv[k]){
            ans=x;break;}
    for(auto i:cant)
        stuv[i]=0;
    return ans;
}
map<int,int>whynot;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }
    towns=n;
    for(int i=1;i<=n;i++){
        whynot[i]=0;
        for(auto k:radj[i])
            for(auto[y,x]:bst[k])
                whynot[x]=max(whynot[x],y+1);
        for(auto[x,y]:whynot)
            bst[i].push_back({y,x});
        sort(bst[i].rbegin(),bst[i].rend());
        while(bst[i].size()>50) bst[i].pop_back();
        whynot.clear();
    }
    while(q--){
        int twn,bus;
        cin>>twn>>bus;
        vector<int>v(bus);
        for(auto&i:v)
            cin>>i;
        if(bus>=50)
            cout<<brute(twn,v)<<'\n';
        else cout<<dob(v,twn)<<'\n';
    }
}

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