제출 #543013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543013		__Variatto	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1780 ms	173116 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=30;/////////////
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";
}
set<pair<int,int>>all[MAX];
void malo(){
    for(auto [f,s]: all[t]){
        if(!zly[s]){
            cout<<-f<<"\n";
            return;
        }
    }
    cout<<-1<<"\n";
}
int wyst[MAX];
vector<int> odw;
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){
        all[a].insert({0, a});
        odw.clear();
        odw.pb(a), wyst[a]=0;
        for(auto s:g2[a]){
            for(auto [f, s]:all[s]){
                odw.pb(s);
                all[a].insert({-(-f+1), s});
                if(wyst[s]!=-1 && wyst[s]<f)
                    all[a].erase(all[a].lower_bound({-wyst[s], s}));
                wyst[s]=-f+1;
                if(all[a].size()>S+3){
                    auto it=all[a].end();
                    it--;
                    all[a].erase(it);
                }
            }
        }
        for(auto s:odw) wyst[s]=-1;
    }
    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;
    }
}

컴파일 시 표준 에러 (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++){
      |                  ~^~~~~~~~~~~

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