Submission #1081771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081771		KALARRY	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2032 ms	10056 KiB

bitaro

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int S = 200;

int N,M,Q,cur_dp[100005];
vector<pair<int,int>> dp[100005];
vector<int> adj_rev[100005];
bool visited[100005],prohibited[100005];
vector<pair<int,int>> temp;
bool did[100005];

void dfs(int v)
{
    if(visited[v])
        return;
    visited[v] = true;
    temp.push_back({-1,0});
    temp.push_back({0,v});
    for(auto u : adj_rev[v])
    {
        dfs(u);
        for(auto x : dp[u])
            if(x.first != -1)
                temp.push_back({x.first+1,x.second});
    }
    sort(temp.begin(),temp.end(),greater<pair<int,int>>());
    for(auto x : temp)
    {
        if(dp[v].size()==S)
            break;
        if(!did[x.second])
        {
            did[x.second] = true;
            dp[v].push_back(x);
        }
    }
    for(auto x : dp[v])
        did[x.second] = false;
    temp.clear();
    
}

void dfs2(int v)
{
    if(visited[v])
        return;
    visited[v] = true;
    if(!prohibited[v])
        cur_dp[v] = 0;
    for(auto u : adj_rev[v])
    {
        dfs2(u);
        if(cur_dp[u] != -1)
            cur_dp[v] = max(cur_dp[v],cur_dp[u] + 1);
    }
}

int main()
{
    scanf("%d%d%d",&N,&M,&Q);
    for(int a,b,i = 1 ; i <= M ; i++)
    {
        scanf("%d%d",&a,&b);
        adj_rev[b].push_back(a);
    }
    for(int i = 1 ; i <= N ; i++)
        dfs(i);
    for(int t,y,i = 1 ; i <= Q ; i++)
    {
        vector<int> busy;
        scanf("%d%d",&t,&y);
        for(int a,j = 1 ; j <= y ; j++)
        {
            scanf("%d",&a);
            busy.push_back(a);
            prohibited[a] = true;
        }
        if(busy.size() <= S)
        {
            int ans = -1;
            for(auto x : dp[t])
                if(!prohibited[x.second])
                    ans = max(ans,x.first);
            printf("%d\n",ans);
        }
        else
        {
            for(int j = 1 ; j <= N ; j++)
            {
                cur_dp[j] = -1;
                visited[j] = false;
            }
            dfs2(t);
            printf("%d\n",cur_dp[t]);
        }
        for(auto a : busy)
            prohibited[a] = false;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:33:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         if(dp[v].size()==S)
      |            ~~~~~~~~~~~~^~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:82:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |         if(busy.size() <= S)
      |            ~~~~~~~~~~~~^~~~
bitaro.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d%d",&N,&M,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d%d",&t,&y);
      |         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~

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