Submission #1060387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060387		doducanh	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	758 ms	148616 KiB

bitaro

///breaker
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
const int maxn=2e5+7;
int n,m,q;
int block_size=100;
vector<int>radj[maxn];
void sol()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        radj[v].push_back(u);
    }
    vector<vector<ii>>path_sizes(n+1);
    vector<int>from(n+1,-1);
    for(int i=1;i<=n;i++){
        path_sizes[i].push_back({0,i});
        vector<int>fromid;
        for(int j:radj[i]){
            for(auto [dist,idx]:path_sizes[j]){
                if(from[idx]!=-1){
                    from[idx]=max(from[idx],dist+1);
                }
                else{
                    fromid.push_back(idx);
                    from[idx]=dist+1;
                }
            }
        }
        for(int idx:fromid){
            path_sizes[i].push_back({from[idx],idx});
        }
        sort(path_sizes[i].rbegin(),path_sizes[i].rend());
        while(path_sizes[i].size()>block_size)path_sizes[i].pop_back();
        for(int idx:fromid){
            from[idx]=-1;
        }
    }
    vector<bool>cvst(n+1,0);
    while(q--){
        int t,v;
        cin>>t>>v;
        vector<int>c(v);
        for(int i=0;i<v;i++){
            cin>>c[i];
            cvst[c[i]]=1;
        }
        int ans=-1;
        if(v>=block_size){
            vector<int>dp(t+1,-1);
            dp[t]=0;
            for(int i=t;i>=1;i--){
                if(dp[i]==-1)continue;
                if(cvst[i]==0)ans=max(ans,dp[i]);
                for(int j:radj[i]){
                    dp[j]=max(dp[j],dp[i]+1);
                }
            }
        }
        else{
            for(auto [dist,idx]:path_sizes[t]){
                if(cvst[idx]==0){
                    ans=dist;
                    break;
                }
            }
        }
        cout<<ans<<"\n";
        for(int i=0;i<v;i++){
            cvst[c[i]]=0;
        }
    }
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

bitaro.cpp: In function 'void sol()':
bitaro.cpp:30:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |             for(auto [dist,idx]:path_sizes[j]){
      |                      ^
bitaro.cpp:44:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         while(path_sizes[i].size()>block_size)path_sizes[i].pop_back();
      |               ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
bitaro.cpp:71:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |             for(auto [dist,idx]:path_sizes[t]){
      |                      ^
bitaro.cpp: At global scope:
bitaro.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main()
      | ^~~~

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