Submission #1140161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140161		kfhjad	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2105 ms	249872 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], ys[MX];
vector<pair<int, int>> longest[MX]; // len, node
int best[MX];

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);
}

void dfs(int node)
{
    visited[node] = true;
    best[node] = -1;
    for (int u : rAdj[node])
    {
        if (!visited[u])
            dfs(u);
            
        if (best[u] != -1)
            best[node] = max(best[node], best[u] + 1);
    }
    
    if (!ys[node])
        best[node] = max(best[node], 0);
}

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, ys[i] = 1;
        
        if (y < SQ)
        {
            int mx = -1;
            for (auto& [u, len] : longest[t])
                if (!ys[u])
                {
                    mx = len;
                    break;
                }
            
            cout << mx << '\n';
        }
        else
        {
            for (int i = 1; i <= t; ++i)
                visited[i] = 0;
            
            dfs(t);
            cout << best[t] << '\n';
        }
        
        for (int i : temp)
            ys[i] = 0;
    }
	
    return 0;
}                              /*****************************=
                            -+**********************************= 
                        :-*****************************************+:
                    ..:*************+=+*******************************=.
                 ..-==*****************+=-+*****************************+.
               ..-=***********************+--+****************************= 
               :+**************#*#**********+--+***************************-  .=--=.  
             .+*********************#*********+--****************************++++----:        
            -+***********************##*********--+********************************+--=.      
           =****=**********************#*********+-=***************************#*****+--=     
         .=****+***********************************-=*********************#*****##*****=-=.   
        :=*****=************************************=-*****************#******#####*****=-=.  
       .=**+***=**************************#**********==***********##*******#**######*****+-=. 
       +***=***+***************************#**********-+*****####********#*****#####******+-=:
      =+**=****+****************#**********************-*####*********##***#*#######*******+-=.
     .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. 
     =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= 
    .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-==
    -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*.
    =*###+######+############################################=..+=-+.########%##%##%##########*-+* 
    +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#.
   .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+
  .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+##
  .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*##
  .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%=  #%%############=###-
  .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+   #%%###########*=###+
  :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####-
   .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+     %%######%#####=*####.
    #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%-      %%######%#####=#####.
    -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%#        #%######%####*=###%#
     *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%*         #%######%####+*###%#
         *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%#          +%######%####=####%#.
          =.=###%%%%%:.............:............#*%%####*#*=====%@%%%           :%#####%%####+######:
           .=%##%%%%%*.............:............#*%%####+#+======%#%*        .:-=%%%%%%%%###+#####+#-
            .%%##%%%-*-..............::::.......#+%%####+#=====-...#:  :*%%%%%%%%%%%%%%%%###*#####=#=
            .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+
             *-#%#%%-  -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#*
             =*.%%%%=   .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*#
              #..%%%#.    -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*#
              +- :%%%#+     =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:.
              .#. =%% .*=     -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+.
               .*  *%-         .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#.
                .=. ##         ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%:
                  ..=*-    .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-.
                           #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:.
                           *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=:
                           :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:
                           .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:
                           .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@-
                           ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%:
                             .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%::
                             .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-::
                             .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=:
                             -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+:
                             %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+-
                             *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#-
                             :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%-
                              :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%*
                               :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*%
                                 :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+
                                -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*%
                                -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+
                               -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%-
                              -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/

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