Submission #172413

#	Time	Username	Problem	Language	Result	Execution time	Memory
172413		mhy908	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1990 ms	91416 KiB

bitaro

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int n, m, q;
vector<int> link[100010];
vector<int> rlink[100010];
vector<pii> noq;
vector<int> y[100010];
int indeg[100010];
int topol[100010], l, r;
pii dp[100010][90];
int ans[100010];
const int buc=50;
int dp2[100010];
bool ch[100010];
int get_dp(int num, int qnum){
    memset(dp2, 0, sizeof(dp2));
    for(auto i:y[qnum])dp2[i]=-inf;
    for(int i=1; i<=n; i++){
        for(auto j:rlink[topol[i]]){
            dp2[topol[i]]=max(dp2[topol[i]], dp2[j]+1);
        }
        if(topol[i]==num)return dp2[num];
    }
}
int main()
{
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        link[a].pb(b);
        rlink[b].pb(a);
        indeg[b]++;
    }
    for(int i=1; i<=n; i++){
        if(!indeg[i])topol[++r]=i;
    }
    for(l=1; l<=r; l++){
        for(auto i:link[topol[l]]){
            indeg[i]--;
            if(!indeg[i])topol[++r]=i;
        }
    }
    for(int i=1; i<=n; i++){
        vector<pii> vc;
        vector<int> temp;
        vc.pb(mp(0, topol[i]));
        for(auto j:rlink[topol[i]]){
            for(int k=1; dp[j][k].S; k++){
                vc.pb(mp(dp[j][k].F+1, dp[j][k].S));
            }
        }
        sort(all(vc), greater<pii>());
        vc.erase(unique(all(vc)), vc.end());
        int num=0;
        for(int j=0; num<=buc&&j<vc.size(); j++){
            if(ch[vc[j].S])continue;
            ch[vc[j].S]=true;
            temp.pb(vc[j].S);
            dp[topol[i]][++num]=vc[j];
        }
        for(auto j:temp)ch[j]=false;
    }
    for(int i=1; i<=q; i++){
        int num, sz;
        scanf("%d %d", &num, &sz);
        for(int j=1; j<=sz; j++){
            int a;
            scanf("%d", &a);
            y[i].pb(a);
        }
        sort(all(y[i]));
        for(int j=1; j<=buc; j++){
            if(dp[num][j].S==0){
                ans[i]=-1;
                break;
            }
            if(!binary_search(all(y[i]), dp[num][j].S)){
                ans[i]=dp[num][j].F;
                break;
            }
            if(j==buc)noq.pb(mp(i, num));
        }
    }
    for(auto i:noq){
        ans[i.F]=get_dp(i.S, i.F);
        if(ans[i.F]<0)ans[i.F]=-1;
    }
    for(int i=1; i<=q; i++){
        printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:69:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; num<=buc&&j<vc.size(); j++){
                                ~^~~~~~~~~~
bitaro.cpp: In function 'int get_dp(int, int)':
bitaro.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bitaro.cpp: In function 'int main()':
bitaro.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &num, &sz);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a);
             ~~~~~^~~~~~~~~~

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