Submission #1140126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140126		kfhjad	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	8 ms	8264 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

set<int> ys;

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 true;
        
        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 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.count(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);
    // cout << longest[5].size() << endl;
    // for (auto [v, len] : longest[5])
        // cout << v << ' ' << len << endl;
    
    while (Q--)
    {
        int t, y, x;
        cin >> t >> y;
        ys.clear();
        
        for (int i = 0; i < y; ++i)
        {
            cin >> x;
            ys.insert(x);
        }
        
        if (y < SQ)
        {
            int mx = -1;
            for (auto& [u, len] : longest[t])
            {
                if (!ys.count(u))
                {
                    mx = len;
                    break;
                }
            }
            
            cout << mx << '\n';
        }
        else
        {
            memset(visited, 0, sizeof visited);
            dfs(t);
            cout << best[t] << '\n';
        }
    }
	
    return 0;
}                              /*****************************=
                            -+**********************************= 
                        :-*****************************************+:
                    ..:*************+=+*******************************=.
                 ..-==*****************+=-+*****************************+.
               ..-=***********************+--+****************************= 
               :+**************#*#**********+--+***************************-  .=--=.  
             .+*********************#*********+--****************************++++----:        
            -+***********************##*********--+********************************+--=.      
           =****=**********************#*********+-=***************************#*****+--=     
         .=****+***********************************-=*********************#*****##*****=-=.   
        :=*****=************************************=-*****************#******#####*****=-=.  
       .=**+***=**************************#**********==***********##*******#**######*****+-=. 
       +***=***+***************************#**********-+*****####********#*****#####******+-=:
      =+**=****+****************#**********************-*####*********##***#*#######*******+-=.
     .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. 
     =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= 
    .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-==
    -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*.
    =*###+######+############################################=..+=-+.########%##%##%##########*-+* 
    +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#.
   .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+
  .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+##
  .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*##
  .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%=  #%%############=###-
  .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+   #%%###########*=###+
  :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####-
   .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+     %%######%#####=*####.
    #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%-      %%######%#####=#####.
    -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%#        #%######%####*=###%#
     *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%*         #%######%####+*###%#
         *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%#          +%######%####=####%#.
          =.=###%%%%%:.............:............#*%%####*#*=====%@%%%           :%#####%%####+######:
           .=%##%%%%%*.............:............#*%%####+#+======%#%*        .:-=%%%%%%%%###+#####+#-
            .%%##%%%-*-..............::::.......#+%%####+#=====-...#:  :*%%%%%%%%%%%%%%%%###*#####=#=
            .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+
             *-#%#%%-  -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#*
             =*.%%%%=   .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*#
              #..%%%#.    -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*#
              +- :%%%#+     =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:.
              .#. =%% .*=     -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+.
               .*  *%-         .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#.
                .=. ##         ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%:
                  ..=*-    .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-.
                           #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:.
                           *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=:
                           :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:
                           .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:
                           .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@-
                           ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%:
                             .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%::
                             .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-::
                             .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=:
                             -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+:
                             %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+-
                             *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#-
                             :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%-
                              :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%*
                               :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*%
                                 :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+
                                -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*%
                                -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+
                               -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%-
                              -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/

Compilation message (stderr)

bitaro.cpp: In function 'int dfs(int)':
bitaro.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
   76 | }
      | ^

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