제출 #1204539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204539		HappyCapybara	수천개의 섬 (IOI22_islands)	C++20	0 / 100	1108 ms	1051200 KiB

islands

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

vector<int> p, c, t;
vector<vector<int>> g;

void dfs(int cur, int par){
  if (!c.empty()) return;
  if (p[cur] != -1) return;
  p[cur] = par;
  for (int next : g[cur]){
    if (p[next] == par) continue;
    if (p[next] != -1){
      while (cur != next){
        c.push_back(cur);
        cur = p[cur];
      }
      c.push_back(cur);
      while (cur != 0){
        t.push_back(cur);
        cur = p[cur];
      }
      t.push_back(cur);
      reverse(c.begin(), c.end());
      reverse(t.begin(), t.end());
      return;
    }
  }
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
  g.resize(N);
  vector<vector<int>> v(N, vector<int>(N));
  for (int i=0; i<M; i+=2){
    g[U[i]].push_back(i);
    g[V[i]].push_back(i);
    v[U[i]][V[i]] = i;
    v[V[i]][U[i]] = i+1;
  }
  p.resize(N, -1);
  dfs(0, 0);
  if (c.empty()) return true;
  vector<int> res;
  for (int i=0; i<t.size()-1; i++) res.push_back(v[t[i]][t[i+1]]);
  for (int i=0; i<c.size(); i++) res.push_back(v[c[i]][c[(i+1)%c.size()]]);
  for (int i=c.size(); i>=1; i--) res.push_back(v[c[i%c.size()]][c[i-1]]);
  for (int i=c.size(); i>=1; i--) res.push_back(v[c[i-1]][c[i%c.size()]]);
  for (int i=0; i<c.size(); i++) res.push_back(v[c[(i+1)%c.size()]][c[i]]);
  for (int i=(int)t.size()-1; i>=1; i--) res.push_back(v[t[i-1]][t[i]]);
  return res;
}

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