Submission #543028

#	Time	Username	Problem	Language	Result	Execution time	Memory
543028		__Variatto	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2049 ms	10792 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, S=350;/////////////
int n, m, q, a, b, y, t;
int c[MAX], ile[MAX], maxi[MAX];
vector<int>g[MAX], top, g2[MAX];
bool zly[MAX];
void topo(){
    for(int i=1; i<=n; i++)
        if(!ile[i])
            top.pb(i);
    for(int i=0; i<top.size(); i++){
        int v=top[i];
        for(auto s:g[v]){
            ile[s]--;
            if(!ile[s]) top.pb(s);
        }
    }
}
void duzo(){
    for(auto a: top){
        if(zly[a]) maxi[a]=-1;
        else maxi[a]=0;
        for(auto s:g2[a])
            if(maxi[s]!=-1)
                maxi[a]=max(maxi[s]+1, maxi[a]);
        if(a==t) break;
    }
    cout<<maxi[t]<<"\n";
}
vector<pair<int,int>>all[MAX];
void malo(){
    for(auto [f,s]: all[t]){
        if(!zly[s]){
            cout<<f<<"\n";
            return;
        }
    }
    cout<<-1<<"\n";
}
int licznik[MAX];
bool bylo[MAX];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1; i<=m; i++){
        cin>>a>>b;
        g[a].pb(b), g2[b].pb(a);
        ile[b]++;
    }
    topo();
    for(auto a:top){
        for(auto s:g2[a])
            licznik[s]=0;
        for(int i=0; i<=S; i++){
            pair<int,int>maxi={0,0};
            for(auto s:g2[a])
                if(licznik[s]<all[s].size())
                    maxi=max(maxi, {all[s][licznik[s]].fi, s});
            if(maxi.se==0) break;
            if(bylo[all[maxi.se][licznik[maxi.se]].se])
                i--;
            else{
                all[a].pb({all[maxi.se][licznik[maxi.se]].fi+1, all[maxi.se][licznik[maxi.se]].se});
                bylo[all[maxi.se][licznik[maxi.se]].se]=true;
            }
            licznik[maxi.se]++;
        }
        for(auto x: all[a])
            bylo[x.se]=false;
        all[a].pb({0, a});
    }
    while(q--){
        cin>>t>>y;
        for(int i=1; i<=y; i++){
            cin>>c[i];
            zly[c[i]]=true;
        }
        if(y>S) duzo();
        else malo();
        for(int i=1; i<=y; i++)
            zly[c[i]]=false;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void topo()':
bitaro.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0; i<top.size(); i++){
      |                  ~^~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:63:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 if(licznik[s]<all[s].size())
      |                    ~~~~~~~~~~^~~~~~~~~~~~~~

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