Submission #206242

#	Time	Username	Problem	Language	Result	Execution time	Memory
206242		achibasadzishvili	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1603 ms	115764 KiB

bitaro

#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll n,m,q,sq=100,d[100002],fix[100002],ans[100002];
vector<ll>rev[100002],k[100002],ge[100002];
vector<pair<ll,ll> >best[100002],f;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    
    for(int i=1; i<=m; i++){
        ll x,y;
        cin >> x >> y;
        rev[y].pb(x);
    }
    
    for(int ind=1; ind<=q; ind++){
        ans[ind] = -1;
        ll x,sz;
        cin >> x >> sz;
        for(int j=0; j<sz; j++){
            ll y;
            cin >> y;
            k[ind].pb(y);
        }
        if(sz >= sq){
            for(int i=1; i<=n; i++){
                d[i] = -1;
                fix[i] = 0;
            }
            d[x] = 0;
            for(int i=x; i>=1; i--)
                if(d[i] != -1)
                for(int j=0; j<rev[i].size(); j++)
                    d[rev[i][j]] = max(d[rev[i][j]] , d[i] + 1);
            for(int i=0; i<k[ind].size(); i++)
                fix[k[ind][i]] = 1;
            for(int i=1; i<=x; i++)
                if(!fix[i])ans[ind] = max(ans[ind] , d[i]);
        }
        else ge[x].pb(ind);
    }
    
    for(int x=1; x<=n; x++){
        f.clear();
        f.pb(mp(0 , x));
        fix[x] = 0;
        for(int i=0; i<rev[x].size(); i++){
            ll to = rev[x][i];
            for(int j=0; j<best[to].size(); j++){
                f.pb(mp(best[to][j].f + 1 , best[to][j].s));
                fix[best[to][j].s] = 0;
            }
        }
        sort(f.begin() , f.end());
        reverse(f.begin() , f.end());
        for(int i=0; i<f.size(); i++){
            if(fix[f[i].s])continue;
            fix[f[i].s] = 1;
            best[x].pb(f[i]);
            if(best[x].size() > sq)break;
        }
        for(int id=0; id<ge[x].size(); id++){
            ll ind = ge[x][id];
            for(int i=0; i<best[x].size(); i++)
                fix[best[x][i].s] = 0;
            for(int i=0; i<k[ind].size(); i++)
                fix[k[ind][i]] = 1;
            for(int i=0; i<best[x].size(); i++)
                if(!fix[best[x][i].s])
                    ans[ind] = best[x][i].f;
        }
    }
    
    
    for(int i=1; i<=q; i++)
        cout << ans[i] << '\n';
    
    
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:38:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0; j<rev[i].size(); j++)
                              ~^~~~~~~~~~~~~~
bitaro.cpp:40:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<k[ind].size(); i++)
                          ~^~~~~~~~~~~~~~
bitaro.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<rev[x].size(); i++){
                      ~^~~~~~~~~~~~~~
bitaro.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<best[to].size(); j++){
                          ~^~~~~~~~~~~~~~~~
bitaro.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<f.size(); i++){
                      ~^~~~~~~~~
bitaro.cpp:65:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(best[x].size() > sq)break;
                ~~~~~~~~~~~~~~~^~~~
bitaro.cpp:67:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int id=0; id<ge[x].size(); id++){
                       ~~^~~~~~~~~~~~~
bitaro.cpp:69:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<best[x].size(); i++)
                          ~^~~~~~~~~~~~~~~
bitaro.cpp:71:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<k[ind].size(); i++)
                          ~^~~~~~~~~~~~~~
bitaro.cpp:73:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<best[x].size(); i++)
                          ~^~~~~~~~~~~~~~~

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