Submission #1074367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074367		fv3	Thousands Islands (IOI22_islands)	C++17	22.75 / 100	1103 ms	2097152 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> res;
bool ok;

void DFS(int index, int back)
{
  if (adj[index].size() > 2)
  {
    ok = true;
    int s_out, s_in;
    for (int i = 0; i < adj[index].size(); i++)
    {
      if (adj[index][i].second == back) continue;
      s_out = adj[index][i].second;
      s_in = adj[index][i].second^1;
      break;
    }
    int e_out, e_in;
    for (int i = 0; i < adj[index].size(); i++)
    {
      if (adj[index][i].second == back || adj[index][i].second == s_out) continue;
      e_out = adj[index][i].second;
      e_in = adj[index][i].second^1;
      break;
    }
    res.insert(res.end(), {s_out, s_in, e_out, e_in, s_in, s_out, e_in, e_out});
    for (int i = res.size() - 9; i >= 0; i--)
      res.push_back(res[i]);
    return;
  }

  for (auto node : adj[index])
  {
    if (node.second == back) continue;
    res.push_back(node.second);
    DFS(node.first, node.second^1);
    break;
  }
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) 
{
  adj = vector<vector<pair<int, int>>>(N);
  res = vector<int>();
  for (int i = 0; i < M; i++)
  {
    adj[U[i]].push_back({V[i], i});
  }

  if (adj[0].size() > 1)
  {
    int s_out = adj[0][0].second;
    int s_in = s_out^1;

    int e_out = adj[0][1].second;
    int e_in = e_out^1;

    return vector<int>({s_out, s_in, e_out, e_in, s_in, s_out, e_in, e_out});
  }

  ok = false;
  DFS(0, -1);

  if (ok)
    return res;
  return false;
}

Compilation message (stderr)

islands.cpp: In function 'void DFS(int, int)':
islands.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < adj[index].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
islands.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < adj[index].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
islands.cpp:25:40: warning: 's_out' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |       if (adj[index][i].second == back || adj[index][i].second == s_out) continue;
islands.cpp:30:79: warning: 's_in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     res.insert(res.end(), {s_out, s_in, e_out, e_in, s_in, s_out, e_in, e_out});
      |                                                                               ^
islands.cpp:30:79: warning: 'e_in' may be used uninitialized in this function [-Wmaybe-uninitialized]
islands.cpp:30:79: warning: 'e_out' may be used uninitialized in this function [-Wmaybe-uninitialized]

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