Submission #1227174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227174		brinton	수천개의 섬 (IOI22_islands)	C++20	1.75 / 100	17 ms	4676 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>
using namespace std;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
  vector<vector<pair<int,int>>> edges(N);
  for(int i = 0;i < M;i++){
    edges[U[i]].push_back({V[i],i});
  }
  if(edges[0].size() < 2) return false;
  vector<int> ans;
  vector<bool> vis(N,false);
  auto co = [](int id){
    if(id%2 == 0) return id+1;
    else return id-1;
  };
  function<void(int)> dfs = [&](int cur){
    vis[cur] = true;
    if(cur == 0){
      vis[edges[cur][0].first] = true;
    }
    for(auto [nxt,id]:edges[cur]){
      if(vis[nxt]) continue;
      ans.push_back(id);
      dfs(nxt);
      ans.push_back(co(id));
    }
    if(cur == 0){
      auto [nxt,id] = edges[cur][0];
      ans.push_back(id);
      dfs(nxt);
      ans.push_back(co(id));
    }
  };
  dfs(0);
  for(int i = 0;i < N;i++) if(!vis[i]) return false;
  
  int csz = ans.size();
  for(int i = 0;i < csz;i++) ans.push_back(co(ans[i]));
  return ans;
  // return ans;
}

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