제출 #1057804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057804		mychecksedad	수천개의 섬 (IOI22_islands)	C++17	1.75 / 100	84 ms	25172 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;
bool dfs(int v, int par, vector<bool> &vis){
  vis[v] = 1;
  // euler.pb(v);
  for(auto U: g[v]){
    int u = U.ss;
    if(u == 0 && par != 0){
      euler.pb(U.ff);
      return 1;
    }
    if(!vis[u]){
      euler.pb(U.ff);
      bool ok = dfs(u, v, vis);
      if(ok) return 1;
      euler.pop_back();
    }

  }
  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);
  map<pii, vi> A;
  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);
  }
  for(int i = 1; i < n; ++i){
    if(A[{0, i}].size() > 1 && A[{i, 0}].size() > 1){
      return vi{A[{0, i}][0], A[{i, 0}][0], A[{0, i}][1], A[{i, 0}][0], A[{0, i}][0]};
    }
  }
  // if(!(C[0].size() > 1 && C[1].size() > 0)) return false;
  vector<bool> vis(n);
  bool ok = dfs(0, 0, vis);
  if(!ok) return false;
  vi res;
  for(int i: euler){
    res.pb(i);
  }
  reverse(all(euler));
  for(int i: euler){
    res.pb(i^1);
  }

  // reverse(all(euler));
  for(int i: euler){
    res.pb(i);
  }

  reverse(all(euler));
  for(int i: euler){
    res.pb(i^1);
  }
  return res;
}

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