제출 #1196169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196169		hyakup	Thousands Islands (IOI22_islands)	C++20	0 / 100	1157 ms	2162688 KiB

islands

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

vector<vector<int>> adj;
vector<int> pai, marc, rep, ans;

map<int, map<int, int>> mp;
bool done = false;

void dfs( int cur, int pai ){
  int f1 = -1, f2 = -1;
  for( int viz : adj[cur] ) if( viz != pai ){
    if( f1 == -1 ) f1 = viz;
    else f2 = viz;
  }

  if( f2 != -1 ){
    int tam = ans.size();
    ans.push_back(mp[cur][f1]);
    ans.push_back(mp[f1][cur]);
    ans.push_back(mp[cur][f2]);
    ans.push_back(mp[f2][cur]);

    ans.push_back(mp[f1][cur]);
    ans.push_back(mp[cur][f1]);
    ans.push_back(mp[f2][cur]);
    ans.push_back(mp[cur][f2]);

    for( int i = tam - 1; i >= 0; i-- ) ans.push_back(ans[i]);
    done = true;
    return;
  }
  if( f2 == -1 ){
    ans.push_back(mp[cur][f1]);
    dfs( f1, cur);
    ans.pop_back();
  }

}

variant<bool, vector<int>> find_journey( int n, int m, vector<int> a, vector<int> b ){


  adj.resize(n);
  marc.resize(n);
  pai.resize(n);
  rep.resize(n);
  iota( rep.begin(), rep.end(), 0 );
  for( int i = 0; i < m; i++ ){
    adj[a[i]].push_back(b[i]);
    mp[a[i]][b[i]] = i;
  }


  dfs( 0,-1 );


  if( !done ) return false;
  return ans;

}

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