Submission #830787

#	Time	Username	Problem	Language	Result	Execution time	Memory
830787		tolbi	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	29 ms	9196 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) {
    vector<bool> vis(n,false);
    vector<int> ansarr;
    vector<vector<pair<int,int>>> arr(n);
    for (int i = 0; i < m; ++i)
    {
        arr[u[i]].push_back({v[i],_indis[i]});
    }
    auto dfs = [&](int node, auto dfs)->bool{
        if (vis[node]) {
            return true;
        }
        vis[node]=true;
        ansarr.push_back(node);
        for (int i = 0; i < arr[node].size(); i++){
            if (dfs(arr[node][i].first,dfs)) return true;
        }
        ansarr.pop_back();
        return false;
    };
    if (!dfs(0,dfs)) return false;
    fill(vis.begin(), vis.end(), false);
    for (int i = 0; i < n; ++i)
    {
        reverse(arr[i].begin(), arr[i].end());
    }
    vector<int> ansarr2;
    swap(ansarr,ansarr2);
    if (!dfs(0,dfs)) return false;
    if (ansarr==ansarr2){
        return false;
    }
    return true;
}
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 instantiation of 'solve(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(int, auto:23)> [with auto:23 = solve(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(int, auto:23)>]':
islands.cpp:25:19:   required from here
islands.cpp:19: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]
   19 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
islands.cpp: In instantiation of 'find_journey(int, int, std::vector<int>, std::vector<int>)::<lambda(int, auto:24)> [with auto:24 = find_journey(int, int, std::vector<int>, std::vector<int>)::<lambda(int, auto:24)>]':
islands.cpp:55:14:   required from here
islands.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         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