Submission #706400

#	Time	Username	Problem	Language	Result	Execution time	Memory
706400		danikoynov	Thousands Islands (IOI22_islands)	C++17	55 / 100	38 ms	6156 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 1010;
int edge_index[maxn][maxn], deg[maxn];
vector < int > g[maxn];
vector < pair < int, int > > graph[maxn];

int used[maxn];
vector < int > cycle;
bool dfs(int v)
{
    used[v] = 1;
    for (pair < int, int > nb : graph[v])
    {
        int u = nb.first;
        if (used[u] == 1)
        {
            cycle.push_back(u);
            return true;
        }
        if (!used[u])
        {
            if (dfs(u) == true)
            {
                cycle.push_back(u);
                return true;
            }
        }
    }
    used[v] = 2;
    return false;
}

std::variant<bool, std::vector<int>> find_journey(
                                      int N, int M, std::vector<int> U, std::vector<int> V)
{

    bool spec = true, double_spec = true;;
    for (int i = 0; i < M; i += 2)
    {
        if (V[i] != U[i + 1] || U[i] != V[i + 1])
            spec = false;
        if (V[i] != V[i + 1] || U[i] != U[i + 1])
            double_spec = false;
    }
    if (N == 2)
    {

        int cnt0 = 0, cnt1 = 0;
        vector < int > idx0, idx1;
        for (int i = 0; i < M; i ++)
        {
            if (U[i] == 0)
                cnt0 ++, idx0.push_back(i);
            else
                cnt1 ++, idx1.push_back(i);
        }

        if (cnt0 >= 2 && cnt1 >= 1)
        {
            vector < int > path;
            path.push_back(idx0[0]);
            path.push_back(idx1[0]);
            path.push_back(idx0[1]);
            path.push_back(idx0[0]);
            path.push_back(idx1[0]);
            path.push_back(idx0[1]);
            return path;
        }
        return false;
    }
    else if (spec)
    {
        for (int i = 0; i < M; i ++)
        {
            deg[U[i]] ++;
            g[U[i]].push_back(i);
        }
        vector < int > bef, path;
        int ver = 0, last = -1;
        while(true)
        {
            if (deg[ver] == 0)
                return false;

            if (deg[ver] == 1)
            {
                bef.push_back(g[ver][0]);

                int new_ver = V[g[ver][0]];
                int pt = 0;
                while(V[g[new_ver][pt]] != ver)
                    pt ++;
                    ///cout << "here " << ver << " " << new_ver << " " << V[g[new_ver][pt]] << endl;
                g[new_ver].erase(g[new_ver].begin() + pt);
                deg[new_ver] --;
                ver = new_ver;
                continue;
            }
            path.push_back(g[ver][0]);
            path.push_back((g[ver][0] ^ 1));
            path.push_back((g[ver][1]));
            path.push_back((g[ver][1] ^ 1));
            path.push_back((g[ver][0] ^ 1));
            path.push_back(g[ver][0]);
            path.push_back((g[ver][1] ^ 1));
            path.push_back((g[ver][1]));
            break;
        }
        vector < int > fin = bef;
        for (int v : path)
            fin.push_back(v);
        reverse(bef.begin(), bef.end());
        for (int v : bef)
            fin.push_back(v);
        return fin;
    }
    if (double_spec)
    {
        for (int i = 0; i < M; i ++)
        {
            graph[U[i]].push_back({V[i], i});
        }

        bool tf = dfs(0);
        if (!tf)
            return false;
        cycle.push_back(0);
        reverse(cycle.begin(), cycle.end());
        int cycle_ver = cycle.back();
        vector < int > bef;
        int i;
        for (i = 0; i < cycle.size(); i ++)
        {
            if (cycle[i] == cycle_ver)
                break;
            int pt = 0;
            while(graph[cycle[i]][pt].first != cycle[i + 1])
                pt ++;
            bef.push_back(graph[cycle[i]][pt].second);
        }
        vector < int > cycle_path[2];

        for (i; i < cycle.size() - 1; i ++)
        {
                        int pt = 0;
            while(graph[cycle[i]][pt].first != cycle[i + 1])
                pt ++;

            cycle_path[0].push_back(graph[cycle[i]][pt].second);
            cycle_path[1].push_back((graph[cycle[i]][pt].second ^ 1));
        }

        vector < int > fin;
        for (int v : bef)
            fin.push_back(v);
        for (int v : cycle_path[0])
            fin.push_back(v);
        for (int v : cycle_path[1])
            fin.push_back(v);
        reverse(cycle_path[0].begin(), cycle_path[0].end());
        reverse(cycle_path[1].begin(), cycle_path[1].end());
        reverse(bef.begin(), bef.end());
        for (int v : cycle_path[0])
            fin.push_back(v);
        for (int v : cycle_path[1])
            fin.push_back(v);
        for (int v : bef)
            fin.push_back(v);
        return fin;
    }
    else
    {
        for (int i = 0; i < M; i ++)
            edge_index[U[i]][V[i]] = i;

        vector < int > path;
        path.push_back(edge_index[0][1]);
        path.push_back(edge_index[1][0]);
        path.push_back(edge_index[0][2]);
        path.push_back(edge_index[2][0]);

        path.push_back(edge_index[1][0]);
        path.push_back(edge_index[0][1]);
        path.push_back(edge_index[2][0]);
        path.push_back(edge_index[0][2]);
        return path;
    }
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:86:22: warning: unused variable 'last' [-Wunused-variable]
   86 |         int ver = 0, last = -1;
      |                      ^~~~
islands.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for (i = 0; i < cycle.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:150:14: warning: statement has no effect [-Wunused-value]
  150 |         for (i; i < cycle.size() - 1; i ++)
      |              ^
islands.cpp:150:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for (i; i < cycle.size() - 1; i ++)
      |                 ~~^~~~~~~~~~~~~~~~~~

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