Submission #730425

#	Time	Username	Problem	Language	Result	Execution time	Memory
730425		caganyanmaz	Thousands Islands (IOI22_islands)	C++17	24 / 100	48 ms	5704 KiB

islands

#include <bits/stdc++.h>
#define pb push_back
#define pp pop_back
using namespace std;

vector<array<int, 2>> edges;
vector<vector<int>> g;
vector<bool> visited;
vector<bool> remember;
vector<int> path;
vector<int> res;

bool dfs(int node)
{
        if (visited[node])
        {
                for (int i : path)
                        res.pb(i);
                int i;
                for (i = 0; i < path.size() && edges[path[i]][0] != node; i++);
                assert(i < path.size());
                for (int j = i; j < path.size(); j++)
                        res.pb(path[j]+1);
                for (int j = path.size()-1; j >= i; j--)
                        res.pb(path[j]);
                for (int j = path.size()-1; j >= i; j--)
                        res.pb(path[j]+1);
                for (int j = i-1; j >= 0; j--)
                        res.pb(path[j]);
                return true;
        }
        visited[node] = true;
        for (int edge : g[node])
        {
                if (remember[edges[edge][1]])
                        continue;
                path.pb(edge);
                if(dfs(edges[edge][1]))
                        return true;
                path.pop_back();
        }
        visited[node] = false;
        remember[node] = true;
        return false;
}

variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v)
{
        res.clear();
        path.clear();
        edges = vector<array<int, 2>>(m);
        g = vector<vector<int>>(n);
        visited = vector<bool>(n);
        remember = vector<bool>(n);
        for (int i = 0; i < m; i+=2)
        {
                edges[i][0] = u[i], edges[i][1] = v[i];
                g[u[i]].pb(i);
        }
        if(dfs(0))
                return res;
        return false;
}

Compilation message (stderr)

islands.cpp: In function 'bool dfs(int)':
islands.cpp:20:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |                 for (i = 0; i < path.size() && edges[path[i]][0] != node; i++);
      |                             ~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from islands.cpp:1:
islands.cpp:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                 assert(i < path.size());
      |                        ~~^~~~~~~~~~~~~
islands.cpp:22:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |                 for (int j = i; j < path.size(); j++)
      |                                 ~~^~~~~~~~~~~~~

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