Submission #1058508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058508		mychecksedad	Thousands Islands (IOI22_islands)	C++17	30.75 / 100	77 ms	25036 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define en cout << '\n'
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
const int N = 1e5+10;

int n, m;
vector<pair<int, int>> g[N];
vector<int> euler, cyc;
vector<bool> good, in_euler(N);
bool is_cyc = 0;
map<pii, vi> A;
vector<int> S;
bool second_case = 0;
bool dfs(int v, int par, vector<bool> &vis){
  vis[v] = 1;
  euler.pb(v);
  in_euler[v] = 1;
  // cout << v << ' ';
  for(auto U: g[v]){
    int u = U.ss;
    if(vis[u] && u != par && in_euler[u]){
      // cout << v << ' ' << u << endl;
      euler.pb(u);
      cyc.pb(u);
      cyc.pb(v);

      is_cyc = 1;
      return 1;
    }
    if(!vis[u] && A[{v, u}].size() > 1 && A[{u, v}].size() > 0){
      second_case = 1;
      // cout << "fuck" << endl;
      is_cyc = 0;
      S = vi{A[{v, u}][0], A[{u, v}][0], A[{v, u}][1], A[{v, u}][0], A[{u, v}][0], A[{v, u}][1]};
      return 1;
    }
    if(!vis[u]){
      bool ok = dfs(u, v, vis);
      // cout << u << ' ' << v << ' ' << ok << endl;
      if(is_cyc && ok) cyc.pb(v);
      if(ok && is_cyc){
        // assert(cyc.size());
        if(v == cyc[0])
        // cout << v << endl;
        is_cyc = 0;
      }
      // cout << ok << ' ' << v << '\n';
      if(ok) return 1;
    }
  }
  assert(euler.size()>0);
  euler.pop_back();
  in_euler[v] = 0;
  return 0;
}

std::variant<bool, std::vector<int>> find_journey(int nn, int mm, std::vector<int> U, std::vector<int> V) { n=nn, m=mm;
  vector<vi> C(nn);
  good.resize(n);
  for(int i = 0; i < mm; ++i){
    C[U[i]].pb(i);
    g[U[i]].pb({i, V[i]});
    A[{U[i], V[i]}].pb(i);
    // if(A[{U[i], V[i]}].size() > 1) good[U[i]] = good[V[i]] = 1;
  }
  for(int i = 1; i < n; ++i){
    if(A[{0, i}].size() > 1 && A[{i, 0}].size() > 0){
      return vi{A[{0, i}][0], A[{i, 0}][0], A[{0, i}][1], A[{0, i}][0], A[{i, 0}][0], A[{0, i}][1]};
    }
  }
  // if(!(C[0].size() > 1 && C[1].size() > 0)) return false;
  vector<bool> vis(n);
  // return false;
  bool ok = dfs(0, 0, vis);
  if(!ok){
    return false;
  }
  vi res;
  // for(int v: euler) cout << v << endl;
  // for(int v: cyc) cout << v << endl;
  // cout << A[{0, 1}][0] << ' '; 
  // en;en;
  if(second_case){
    for(int i = 0; i + 1 < euler.size(); ++i){
      res.pb(A[{euler[i], euler[i + 1]}][0]);
      // cout << res.back() << ' ';
      // cout << euler[i] << ' ' << euler[i + 1] << '\n';
    }
    for(int x: S) res.pb(x);

    vector<int> res2;
    for(int i = 0; i + 1 < euler.size(); ++i){
      res2.pb(A[{euler[i], euler[i + 1]}][0]);
    }
    reverse(all(res2));
    for(int x: res2) res.pb(x);
    return res;
  }
  for(int i = 0; i + 1 < euler.size(); ++i){
    res.pb(A[{euler[i], euler[i + 1]}][0]);
  }

  // assert();
  reverse(all(cyc));
  // assert((A[{cyc[0], cyc[1]}].size() > 1));
  res.pb(A[{cyc[0], cyc[1]}][1]);
  res.pb(A[{cyc[0], cyc[1]}][0]);

  reverse(all(cyc));
  // assert(false);


  for(int i = 0; i + 2 < cyc.size(); ++i){
    res.pb(A[{cyc[i + 1], cyc[i]}][0]);
  }
  reverse(all(cyc));
  res.pb(A[{cyc[0], cyc[1]}][1]);
  // assert(false);

  vi res2;
  // for(int i = 0; i + 1 < cyc.size(); ++i){
  //   res2.pb(A[{cyc[i], cyc[i + 1]}][0]);
  // }
  
  // reverse(all(res2));
  // for(int x: res2) res.pb(x);
  

  // reverse(all(cyc));
  // res2.clear();
  // for(int i = 0; i + 1 < cyc.size(); ++i){
  //   res2.pb(A[{cyc[i], cyc[i + 1]}][0]);
  // }
  
  // reverse(all(res2));
  // for(int x: res2) res.pb(x);

  res2.clear();
  for(int i = 0; i + 1 < euler.size(); ++i){
    if(cyc[0] == euler[i]) break;
    res2.pb(A[{euler[i], euler[i + 1]}][0]);
  }
  reverse(all(res2));
  for(int x: res2) res.pb(x);
  return res;
}

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:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 0; i + 1 < euler.size(); ++i){
      |                    ~~~~~~^~~~~~~~~~~~~~
islands.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i = 0; i + 1 < euler.size(); ++i){
      |                    ~~~~~~^~~~~~~~~~~~~~
islands.cpp:106:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i = 0; i + 1 < euler.size(); ++i){
      |                  ~~~~~~^~~~~~~~~~~~~~
islands.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int i = 0; i + 2 < cyc.size(); ++i){
      |                  ~~~~~~^~~~~~~~~~~~
islands.cpp:146:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int i = 0; i + 1 < euler.size(); ++i){
      |                  ~~~~~~^~~~~~~~~~~~~~

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