제출 #1227212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227212		brinton	Thousands Islands (IOI22_islands)	C++20	8.40 / 100	43 ms	8264 KiB

islands

#include "islands.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
  auto co = [](int id){
    if(id%2 == 0) return id+1;
    else return id-1;
  };

  vector<set<pair<int,int>>> edges(N);// nxt,id
  for(int i = 0;i < M;i+=2){
    edges[U[i]].insert({V[i],i});
  }
  vector<bool> vis(N,false);
  set<int> anc;

  vector<pair<int,int>> nxt_edges(N);// nxt,id
  vector<int> ans;
  function<void(int)> dfs = [&](int cur){
    vis[cur] = true;
    anc.insert(cur);
    for(auto [nxt,id]:edges[cur]){
      if(anc.count(nxt)) {
        // find the answer
        vector<int> before_loop;
        int croot = 0;
        while(croot != nxt){
          before_loop.push_back(nxt_edges[croot].second);
          croot = nxt_edges[croot].first;
        }
        vector<int> in_loop;
        do{
          in_loop.push_back(nxt_edges[croot].second);
          croot = nxt_edges[croot].first;
        }while(croot != nxt);
        for(auto &i:before_loop) ans.push_back(i);
        for(auto &i:in_loop) ans.push_back(i);
        for(auto &i:in_loop) ans.push_back(co(i));
        reverse(before_loop.begin(),before_loop.end());
        reverse(in_loop.begin(),in_loop.end());
        for(auto &i:in_loop) ans.push_back(i);
        for(auto &i:in_loop) ans.push_back(co(i));
        for(auto &i:before_loop) ans.push_back(i);
        return;
      }
      if(vis[nxt]) continue;
      nxt_edges[cur] = {nxt,id};
      dfs(nxt);
      if(!ans.empty()) return;
    }
    anc.erase(cur);
  };
  dfs(0);
  if(ans.empty()) return false;
  return ans;
}

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