Submission #824310

#	Time	Username	Problem	Language	Result	Execution time	Memory
824310		vjudge1	Thousands Islands (IOI22_islands)	C++17	24 / 100	36 ms	10800 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
struct edge {
    int to, f, ind, rev;
};
vector<edge> adj[200100];
bool vis[1000], ons[1000];
vector<edge> stk;
vector<int> ans;
bool inc;
int cy;
bool dfs(int n, int p) {
    if(ons[n]) {
        cy = n;
        inc = 1;
        vector<int> a, b;
        int i = 0;
        while(stk[i].f!=n)
            i++;
        while(i<stk.size())
            a.push_back(stk[i].ind), b.push_back(stk[i].rev), i++;
        for(auto i: b)
            ans.push_back(i);
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        for(auto i: a)
            ans.push_back(i);
        for(auto i: b)
            ans.push_back(i);
        return 1;
    }
    if(vis[n]) return 0;
    vis[n] = ons[n] = 1;
    for(auto i: adj[n]) {
        ans.push_back(i.ind);
        stk.push_back(i);
        if(dfs(i.to, n)) {
            if(!inc)
                ans.push_back(i.ind);
            if(cy==n)
                inc=0;
            return 1;
        }
        stk.pop_back();
        ans.pop_back();
    }
    return ons[n] = 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    for(int i = 0; i < M; i+=2)
        adj[U[i]].push_back({V[i], U[i], i, i+1});
    if(dfs(0,-1)) {
        return ans;
    } else {
        return false;
    }
}

Compilation message (stderr)

islands.cpp: In function 'bool dfs(int, int)':
islands.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         while(i<stk.size())
      |               ~^~~~~~~~~~~

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