Submission #830777

#	Time	Username	Problem	Language	Result	Execution time	Memory
830777		tolbi	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	32 ms	10988 KiB

islands

#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#include "islands.h"
variant<bool, vector<int>> solve(int n, int m, vector<int> u, vector<int> v, vector<int> _indis) {
    if (n==1) return false;
    vector<int> stak;
    vector<vector<pair<int,int>>> arr(n);
    vector<vector<pair<int,int>>> revarr(n);
    for (int i = 0; i < m; i++){
        arr[u[i]].push_back({v[i],_indis[i]});
        revarr[v[i]].push_back({u[i],_indis[i]});
    }
    function<void(int)> dfs;
    vector<bool> vis(n,false);
    vector<int> stk;
    dfs = [&](int node)->void{
        if (vis[node]) return;
        vis[node]=true;
        for (int i = 0; i < arr[node].size(); i++){
            dfs(arr[node][i].first);
        }
        stk.push_back(node);
    };
    dfs(0);
    vector<vector<int>> scc;
    vector<int> com(n);
    dfs = [&](int node)->void{
        if (vis[node]) return;
        vis[node]=true;
        com[node]=scc.size()-1;
        scc.back().push_back(node);
        for (int i = 0; i < revarr[node].size(); i++){
            dfs(revarr[node][i].first);
        }
    };
    fill(vis.begin(), vis.end(), false);
    while (stk.size()){
        int node = stk.back();
        stk.pop_back();
        if (vis[node]) continue;
        scc.push_back(vector<int>(0));
        dfs(node);
    }
    vector<int> szs(scc.size(),0);
    vector<vector<int>> dag(scc.size());
    vector<int> topo;
    vector<int> gelsz(scc.size());
    for (int i = 0; i < m; i++){
        if (com[u[i]]==com[v[i]]){
            if (arr[0].size()<=1 && v[i]==0){
                continue;
            }
            szs[com[u[i]]]++;
        }
        else {
            dag[com[u[i]]].push_back(com[v[i]]);
            gelsz[com[v[i]]]++;
        }
    }
    bool gor = false;
    for (int i = 0; i < scc.size(); ++i)
    {
        if (szs[i]==scc[i].size()*(scc[i].size()-1)/2){
            if (gor) return true;
            gor=true;
        }
        if (szs[i]>scc[i].size()*(scc[i].size()-1)/2) return true;
    }
    vector<int> dp(n,0);
    dp[0]=1;
    stk.push_back(0);
    while (stk.size()){
        int node = stk.back();
        if (dp[node]>1 && szs[node]>=scc[node].size()) return true;
        stk.pop_back();
        for (int i = 0; i < dag[node].size(); i++){
            gelsz[dag[node][i]]--;
            dp[dag[node][i]]+=dp[node];
            if (!gelsz[dag[node][i]]) stk.push_back(dag[node][i]);
        }
    }
    return false;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    int crr = 0;
    vector<int> ind(N,-1);
    vector<int> indarr;
    vector<vector<int>> arr(N);
    for (int i = 0; i < M; ++i)
    {
        arr[U[i]].push_back(V[i]);
    }
    auto dfs = [&](int node, auto dfs)->void{
        if (ind[node]!=-1) return;
        ind[node]=crr++;
        for (int i = 0; i < arr[node].size(); i++){
            dfs(arr[node][i],dfs);
        }
    };
    dfs(0,dfs);
    vector<int> asu;
    vector<int> asv;
    for (int i = 0; i < M; i++){
        if (ind[U[i]]==-1 || ind[V[i]]==-1) continue;
        asu.push_back(ind[U[i]]);
        asv.push_back(ind[V[i]]);
        indarr.push_back(i);
    }
    return solve(crr,asu.size(),asu,asv,indarr);
}

Compilation message (stderr)

islands.cpp: In lambda function:
islands.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
islands.cpp: In lambda function:
islands.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i = 0; i < revarr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > solve(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
islands.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < scc.size(); ++i)
      |                     ~~^~~~~~~~~~~~
islands.cpp:64:19: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if (szs[i]==scc[i].size()*(scc[i].size()-1)/2){
islands.cpp:68:19: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (szs[i]>scc[i].size()*(scc[i].size()-1)/2) return true;
islands.cpp:75:36: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         if (dp[node]>1 && szs[node]>=scc[node].size()) return true;
islands.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i < dag[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
islands.cpp: In instantiation of 'find_journey(int, int, std::vector<int>, std::vector<int>)::<lambda(int, auto:23)> [with auto:23 = find_journey(int, int, std::vector<int>, std::vector<int>)::<lambda(int, auto:23)>]':
islands.cpp:101:14:   required from here
islands.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45