Submission #747586

#	Time	Username	Problem	Language	Result	Execution time	Memory
747586		math_rabbit_1028	Thousands Islands (IOI22_islands)	C++17	70.75 / 100	263 ms	27984 KiB

islands

#include "islands.h"
 
#include <bits/stdc++.h>
using namespace std;
 
bool ans = false;
vector<int> res;
 
int n, m;
vector< pair<int, int> > adj[101010], rev[101010];
int out[101010], in[101010], remain[202020];
 
set< pair<int, int> > outset;
 
int ch[202020], ch2[202020];
vector<int> path1, path2, cycle, path3, cycle2;
int junc;
void DFS(int v) {
  int cnt = 0;
  for (int i = 0; i < adj[v].size(); i++) {
    if (remain[adj[v][i].second] == 0) continue;
    if (ch[adj[v][i].first] == 0) {
      cnt++;
    }
  }
  if (cnt >= 2) {
    ans = true;
    junc = v;
    return;
  }
  for (int i = 0; i < adj[v].size(); i++) {
    if (remain[adj[v][i].second] == 0) continue;
    if (ch[adj[v][i].first] == 0) {
      ch[adj[v][i].first] = 1;
      path1.push_back(adj[v][i].second);
      DFS(adj[v][i].first);
    }
  }
}
 
int st = -1;
void path(int v) { 
  for (int i = 0; i < adj[v].size(); i++) {
    if (remain[adj[v][i].second] == 0) continue;
    if (ch[adj[v][i].first] == 0) {
      ch[adj[v][i].first] = 1;
      ch2[adj[v][i].first] = 1;
      path2.push_back(adj[v][i].second);
      path(adj[v][i].first);
      if (st >= 0) return;
    }
    else if (ch2[adj[v][i].first] == 1) {
      path2.push_back(adj[v][i].second);
      st = adj[v][i].first;
      return;
    }
  }
  path2.pop_back();
}
 
bool isconnect = false;
int iscycle[101010];
void check(int v) {
  if (iscycle[v] == 1) {
    st = v;
    isconnect = true;
    return;
  }
  for (int i = 0; i < adj[v].size(); i++) {
    if (remain[adj[v][i].second] == 0) continue;
    if (ch[adj[v][i].first] == 0) {
      ch[adj[v][i].first] = 1;
      path3.push_back(adj[v][i].second);
      check(adj[v][i].first);
      if (isconnect) return;
    }
  }
  path3.pop_back();
}
 
int other_st = -1;
void other_path(int v) { 
  for (int i = 0; i < adj[v].size(); i++) {
    if (remain[adj[v][i].second] == 0) continue;
    if (ch[adj[v][i].first] == 0) {
      ch[adj[v][i].first] = 1;
      path3.push_back(adj[v][i].second);
      other_path(adj[v][i].first);
      if (other_st >= 0) return;
    }
    else {
      path3.push_back(adj[v][i].second);
      other_st = adj[v][i].first;
      return;
    }
  }
  path3.pop_back();
}
 
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
  n = N; m = M;
  for (int i = 0; i < m; i++) {
    adj[U[i]].push_back({V[i], i});
    rev[V[i]].push_back({U[i], i});
    out[U[i]]++;
    in[V[i]]++;
    remain[i] = 1;
  }
 
  for (int i = 0; i < n; i++) outset.insert({out[i], i});
  while (!outset.empty() && outset.begin()->first == 0) {
    int v = outset.begin()->second;
    outset.erase(outset.begin());
    for (int i = 0; i < rev[v].size(); i++) {
      if (remain[rev[v][i].second] == 0) continue;
      remain[rev[v][i].second] = 0;
      outset.erase(outset.find(make_pair(out[rev[v][i].first], rev[v][i].first)));
      out[rev[v][i].first]--;
      outset.insert(make_pair(out[rev[v][i].first], rev[v][i].first));
    }
  }
 
  if (out[0] <= 1) {
    for (int i = 0; i < rev[0].size(); i++) {
      if (remain[rev[0][i].second] == 0) continue;
      remain[rev[0][i].second] = 0;
      outset.erase(outset.find(make_pair(out[rev[0][i].first], rev[0][i].first)));
      out[rev[0][i].first]--;
      outset.insert(make_pair(out[rev[0][i].first], rev[0][i].first));
    }
  }
  
  while (!outset.empty() && outset.begin()->first == 0) {
    int v = outset.begin()->second; 
    outset.erase(outset.begin());
    for (int i = 0; i < rev[v].size(); i++) {
      if (remain[rev[v][i].second] == 0) continue;
      remain[rev[v][i].second] = 0;
      outset.erase(outset.find(make_pair(out[rev[v][i].first], rev[v][i].first)));
      out[rev[v][i].first]--;
      outset.insert(make_pair(out[rev[v][i].first], rev[v][i].first));
    }
  }
 
  //for (int i = 0; i < m; i++) cout << remain[i] << "\n";
  //cout << "\n";
 
  ch[0] = 1;
  DFS(0);
  //for (int i = 0; i < n; i++) cout << ch[i] << " ";
  //cout << "\n";
 
  if (ans) {
    int idx = 0;
    for (int i = 0; i < path1.size(); i++) res.push_back(path1[i]);
    //res.push_back(-1);
    while (ch[adj[junc][idx].first] == 1 || remain[adj[junc][idx].second] == 0) idx++;
    int first = adj[junc][idx].first;
    ch[first] = 1;
    ch2[first] = 1;
    ch2[junc] = 1;
    path2.push_back(adj[junc][idx].second);
    path(first);
 
    int rev = -1, v = junc;
    for (int i = 0; i < path2.size(); i++) {
      if (v == st) {
        rev = i;
        break;
      }
      v = V[path2[i]];
    }
    for (int i = rev; i < path2.size(); i++) {
      cycle.push_back(path2[i]);
      iscycle[V[path2[i]]] = 1;
    }
    for (int i = 0; i < cycle.size(); i++) path2.pop_back();
    for (int i = 0; i < path2.size(); i++) res.push_back(path2[i]);
      //res.push_back(-1);
    for (int i = 0; i < cycle.size(); i++) res.push_back(cycle[i]);
      //res.push_back(-1);
    for (int i = path2.size() - 1; i >= 0; i--) res.push_back(path2[i]);
      //res.push_back(-1);
 
    //for (int i = 0; i < n; i++) cout << ch[i] << " ";
    //cout << "\n";
    //for (int i = 0; i < n; i++) cout << iscycle[i] << " ";
    //cout << "\n";
 
    for (int i = 0; i < n; i++) ch[i] = 0;
    st = -1;
    path1.clear();
    ch[0] = 1;
    DFS(0);
 
    idx++;
    while (ch[adj[junc][idx].first] == 1 || remain[adj[junc][idx].second] == 0) idx++;
    int second = adj[junc][idx].first;
    ch[second] = 1;
    path3.push_back(adj[junc][idx].second);
    check(second);
    if (isconnect) {
      int k = 0;
      for (int i = 0; i < cycle.size(); i++) if (V[cycle[i]] == st) k = i;
      for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]);
        //res.push_back(-1);
      for (int i = k; i >= 0; i--) res.push_back(cycle[i]);
        //res.push_back(-1);
      for (int i = cycle.size() - 1; i > k; i--) res.push_back(cycle[i]);
        //res.push_back(-1);
      for (int i = path3.size() - 1; i >= 0; i--) res.push_back(path3[i]);
        //res.push_back(-1);
    }
    else {
      for (int i = 0; i < n; i++) ch[i] = 0;
      st = -1;
      path1.clear();
      ch[0] = 1;
      DFS(0);
      ch[second] = 1;
      path3.push_back(adj[junc][idx].second);
      other_path(second);
      
      rev = -1; v = junc;
      for (int i = 0; i < path3.size(); i++) {
        if (v == other_st) {
          rev = i;
          break;
        }
        v = V[path3[i]];
      }
      for (int i = rev; i < path3.size(); i++) {
        cycle2.push_back(path3[i]);
      }
      for (int i = 0; i < cycle2.size(); i++) path3.pop_back();
      for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]);
        //res.push_back(-1);
      for (int i = 0; i < cycle2.size(); i++) res.push_back(cycle2[i]);
        //res.push_back(-1);
      for (int i = path3.size() - 1; i >= 0; i--) res.push_back(path3[i]);
        //res.push_back(-1);
 
      for (int i = 0; i < path2.size(); i++) res.push_back(path2[i]);
        //res.push_back(-1);
      for (int i = cycle.size() - 1; i >= 0; i--) res.push_back(cycle[i]);
        //res.push_back(-1);
      for (int i = path2.size() - 1; i >= 0; i--) res.push_back(path2[i]);
        //res.push_back(-1);
 
      for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]);
        //res.push_back(-1);
      for (int i = cycle2.size() - 1; i >= 0; i--) res.push_back(cycle2[i]);
        //res.push_back(-1);
      for (int i = path3.size() - 1; i >= 0; i--) res.push_back(path3[i]);
        //res.push_back(-1);
 
    }
    for (int i = path1.size() - 1; i >= 0; i--) res.push_back(path1[i]);
    return res;
  }
  else return ans;
}

Compilation message (stderr)

islands.cpp: In function 'void DFS(int)':
islands.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int i = 0; i < adj[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
islands.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i = 0; i < adj[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
islands.cpp: In function 'void path(int)':
islands.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 0; i < adj[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
islands.cpp: In function 'void check(int)':
islands.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int i = 0; i < adj[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
islands.cpp: In function 'void other_path(int)':
islands.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int i = 0; i < adj[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
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:115: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]
  115 |     for (int i = 0; i < rev[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
islands.cpp:125: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]
  125 |     for (int i = 0; i < rev[0].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
islands.cpp:137: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]
  137 |     for (int i = 0; i < rev[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
islands.cpp:156:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for (int i = 0; i < path1.size(); i++) res.push_back(path1[i]);
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for (int i = 0; i < path2.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:174:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for (int i = rev; i < path2.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~
islands.cpp:178:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for (int i = 0; i < cycle.size(); i++) path2.pop_back();
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:179:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for (int i = 0; i < path2.size(); i++) res.push_back(path2[i]);
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:181:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for (int i = 0; i < cycle.size(); i++) res.push_back(cycle[i]);
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:205:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |       for (int i = 0; i < cycle.size(); i++) if (V[cycle[i]] == st) k = i;
      |                       ~~^~~~~~~~~~~~~~
islands.cpp:206:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |       for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]);
      |                       ~~^~~~~~~~~~~~~~
islands.cpp:226:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |       for (int i = 0; i < path3.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~
islands.cpp:233:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |       for (int i = rev; i < path3.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
islands.cpp:236:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |       for (int i = 0; i < cycle2.size(); i++) path3.pop_back();
      |                       ~~^~~~~~~~~~~~~~~
islands.cpp:237:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |       for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]);
      |                       ~~^~~~~~~~~~~~~~
islands.cpp:239:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |       for (int i = 0; i < cycle2.size(); i++) res.push_back(cycle2[i]);
      |                       ~~^~~~~~~~~~~~~~~
islands.cpp:244:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  244 |       for (int i = 0; i < path2.size(); i++) res.push_back(path2[i]);
      |                       ~~^~~~~~~~~~~~~~
islands.cpp:251:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |       for (int i = 0; i < path3.size(); i++) res.push_back(path3[i]);
      |                       ~~^~~~~~~~~~~~~~

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