Submission #172392

#	Time	Username	Problem	Language	Result	Execution time	Memory
172392		mhy908	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2037 ms	104916 KiB

bitaro

#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;
unordered_set<int> y[100010];
int indeg[100010];
int topol[100010], l, r;
pii dp[100010][110];
int ans[100010];
const int buc=100;
int dp2[100010];
int get_dp(int num, int qnum){
    for(int i=1; i<=n; i++){
        if(y[qnum].count(topol[i]))dp2[topol[i]]=-inf;
        else dp2[topol[i]]=0;
        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;
        unordered_set<int> ch;
        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.count(vc[j].S))continue;
            ch.insert(vc[j].S);
            dp[topol[i]][++num]=vc[j];
        }
    }
    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].insert(a);
        }
        for(int j=1; j<=buc; j++){
            if(dp[num][j].S==0){
                ans[i]=-1;
                break;
            }
            if(y[i].count(dp[num][j].S)==0){
                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);
    }
    for(int i=1; i<=q; i++){
        printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:65: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:33:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bitaro.cpp: In function 'int main()':
bitaro.cpp:36: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:39: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:73: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:76: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: 0 / 7
• Subtask 3: 0 / 86