Submission #1140167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140167		kfhjad	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1585 ms	246664 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int SQ = 100;
const int MX = 100001;
vector<int> adj[MX], rAdj[MX];
bool visited[MX], processed[MX], blocked[MX];
vector<pair<int, int>> longest[MX]; // len, node

void process(int node)
{
    if (processed[node])
        return;
    
    processed[node] = true;
    
    auto& x = longest[node];
    for (int u : rAdj[node])
    {
        process(u);

        for (auto& [v, len] : longest[u])
            x.push_back({v, len + 1});
        
        x.push_back({u, 1});
    }
    
    x.push_back({node, 0});
    
    sort(x.begin(), x.end(), [](auto& a, auto& b)
    {
        if (a.first != b.first)
            return a.first < b.first;

        return a.second > b.second;
    });
    
    x.erase(unique(x.begin(), x.end(), [](auto& a, auto& b) { return a.first == b.first; }), x.end());
    sort(x.begin(), x.end(), [](auto& a, auto& b) { return a.second > b.second; });
    
    if (x.size() > SQ)
        x.resize(SQ);
}

void dfs2(int node)
{
    if (visited[node])
        return;

    visited[node] = true;
    process(node);
    
    for (int u : adj[node])
        dfs2(u);
}

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N, M, Q;
    cin >> N >> M >> Q;
    
    while (M--)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        rAdj[b].push_back(a);
    }
    
    for (int i = 1; i <= N; ++i)
        dfs2(i);
    
    while (Q--)
    {
        int t, y;
        cin >> t >> y;
        vector<int> temp(y);
        
        for (int& i : temp)
            cin >> i, blocked[i] = true;
        
        if (y < SQ)
        {
            int mx = -1;
            for (auto& [u, len] : longest[t])
                if (!blocked[u])
                {
                    mx = len;
                    break;
                }
            
            cout << mx << '\n';
        }
        else
        {
            vector<int> dp(t + 1, -1);
            for (int i = 1; i <= t; ++i)
            {
                for (int u : rAdj[i])
                    if (dp[u] != -1)                
                        dp[i] = max(dp[i], dp[u] + 1);
                
                if (!blocked[i])
                    dp[i] = max(dp[i], 0);
            }
            
            cout << dp[t] << '\n';
        }
        
        for (int i : temp)
            blocked[i] = false;
    }
	
    return 0;
}                              /*****************************=
                            -+**********************************= 
                        :-*****************************************+:
                    ..:*************+=+*******************************=.
                 ..-==*****************+=-+*****************************+.
               ..-=***********************+--+****************************= 
               :+**************#*#**********+--+***************************-  .=--=.  
             .+*********************#*********+--****************************++++----:        
            -+***********************##*********--+********************************+--=.      
           =****=**********************#*********+-=***************************#*****+--=     
         .=****+***********************************-=*********************#*****##*****=-=.   
        :=*****=************************************=-*****************#******#####*****=-=.  
       .=**+***=**************************#**********==***********##*******#**######*****+-=. 
       +***=***+***************************#**********-+*****####********#*****#####******+-=:
      =+**=****+****************#**********************-*####*********##***#*#######*******+-=.
     .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. 
     =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= 
    .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-==
    -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*.
    =*###+######+############################################=..+=-+.########%##%##%##########*-+* 
    +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#.
   .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+
  .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+##
  .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*##
  .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%=  #%%############=###-
  .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+   #%%###########*=###+
  :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####-
   .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+     %%######%#####=*####.
    #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%-      %%######%#####=#####.
    -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%#        #%######%####*=###%#
     *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%*         #%######%####+*###%#
         *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%#          +%######%####=####%#.
          =.=###%%%%%:.............:............#*%%####*#*=====%@%%%           :%#####%%####+######:
           .=%##%%%%%*.............:............#*%%####+#+======%#%*        .:-=%%%%%%%%###+#####+#-
            .%%##%%%-*-..............::::.......#+%%####+#=====-...#:  :*%%%%%%%%%%%%%%%%###*#####=#=
            .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+
             *-#%#%%-  -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#*
             =*.%%%%=   .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*#
              #..%%%#.    -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*#
              +- :%%%#+     =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:.
              .#. =%% .*=     -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+.
               .*  *%-         .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#.
                .=. ##         ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%:
                  ..=*-    .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-.
                           #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:.
                           *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=:
                           :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:
                           .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:
                           .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@-
                           ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%:
                             .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%::
                             .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-::
                             .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=:
                             -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+:
                             %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+-
                             *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#-
                             :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%-
                              :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%*
                               :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*%
                                 :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+
                                -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*%
                                -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+
                               -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%-
                              -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/

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