Submission #628592

#	Time	Username	Problem	Language	Result	Execution time	Memory
628592		c28dnv9q3	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	111 ms	14872 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> U, V;
int N, M;
vector<vector<int>> adj;
map<pair<int,int>,int> cm;

vector<int> path_to(int target) {
  vector<bool> vis(N);
  vector<int> prev(N);
  queue<int> q;
  q.push(0);
  vis[0] = true;
  prev[0] = -1;
  while (!q.empty()) {
    int x = q.front(); q.pop();
    if (x == target) {
      vector<int> sol;
      while (x != -1) {
        sol.push_back(x);
        x = prev[x];
      }
      reverse(sol.begin(), sol.end());
      return sol;
    }
    for (auto c : adj[x]) {
      if (!vis[V[c]]) {
        vis[V[c]] = true;
        prev[V[c]] = x;
        q.push(V[c]);
      }
    }
  }

  return {};
}

variant<bool, vector<int>> find_journey(
    int N, int M, vector<int> U, vector<int> V) {
  ::U = U;
  ::V = V;
  ::N = N;
  ::M = M;
  adj.resize(N);
  for (int i = 0; i < M; i++)
    adj[U[i]].push_back(i);
  for (int i = 0; i < M; i++)
    cm[{U[i], V[i]}] = i;
  if (adj[0].size() >= 2) {
    int c0 = adj[0][0];
    int c1 = adj[0][1];
    int t0 = V[c0];
    int t1 = V[c1];
    int c2 = cm[{t0,0}];
    int c3 = cm[{t1,0}];
    return vector<int>{c0,c1,c2,c3,c1,c0,c3,c2};
  }
  
  for (int i = 1; i < N; i++) {
    if (adj[i].size() < 3) continue;
    auto p = path_to(i);
    if (p.empty()) continue;
    vector<int> ret;
    for (int j = 0; j < p.size() - 1; j++)
      ret.push_back(cm[{p[j], p[j+1]}]);

    int from = p[p.size()-2];
    int t0 = i;
    int ts[2];
    for (int j=0, k=0; k < adj[i].size() && j < 2; k++) {
      if (adj[i][k] == from) continue;
      ts[j++] = adj[i][k];
    }
    int t1 = ts[0];
    int t2 = ts[1];
    int c0 = cm[{t0,t1}];
    int c1 = cm[{t1,t0}];
    int c2 = cm[{t0,t2}];
    int c3 = cm[{t2,t0}];
    vector<int> t{
      c0, c1, c2, c3, 
      c1, c0, c3, c2
    };
    ret.insert(ret.end(), t.begin(), t.end());

    for (int j = p.size()-2; j >= 0; j--)
      ret.push_back(cm[{p[j], p[j+1]}]);
    return ret;
  }
  return false;
}

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:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int j = 0; j < p.size() - 1; j++)
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int j=0, k=0; k < adj[i].size() && j < 2; k++) {
      |                        ~~^~~~~~~~~~~~~~~

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