Submission #730415

#	Time	Username	Problem	Language	Result	Execution time	Memory
730415		caganyanmaz	Thousands Islands (IOI22_islands)	C++17	26 / 100	41 ms	6144 KiB

islands

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


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

void add(int next_node, int node)
{
        int next_edge;
        for (next_edge = 0; next_edge < g[next_node].size() && edges[g[next_node][next_edge]][1] != node; next_edge++);
        assert(next_edge < g[next_node].size());
        result.pb(g[next_node][next_edge]);
        reverse(g[next_node].begin(), g[next_node].end());
}

bool dfs(int node)
{
        if (g[node].size() > 2 || (g[node].size() > 1 && node == 0))
        {
                for (int i : path)
                        result.pb(i);
                if (node != 0)
                        for (int i = g[node].size()-1; i >= 0; i--)
                                if (edges[g[node][i]][1] == edges[path.back()][0])
                                        g[node].erase(next(g[node].begin(), i));
                for (int i = 0; i < 2; i++)
                {
                        result.pb(g[node][i]);
                        add(edges[g[node][i]][1], node);
                }
                int a = result[result.size()-3], b = result[result.size()-4], c=result[result.size()-1], d=result[result.size()-2];
                result.pb(a), result.pb(b), result.pb(c), result.pb(d);
                for (int i = path.size()-1; i >= 0; i--)
                        result.pb(path[i]);
                return true;
        }
        visited[node] = true;
        for (int edge : g[node])
        {
                if (visited[edges[edge][1]])
                        continue;
                path.pb(edge);
                if(dfs(edges[edge][1]))
                        return true;
        }
        path.pp();
        return false;
}



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

Compilation message (stderr)

islands.cpp: In function 'void add(int, int)':
islands.cpp:16:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (next_edge = 0; next_edge < g[next_node].size() && edges[g[next_node][next_edge]][1] != node; next_edge++);
      |                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
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:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         assert(next_edge < g[next_node].size());
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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