제출 #1182354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182354		PagodePaiva	수천개의 섬 (IOI22_islands)	C++20	1.75 / 100	74 ms	39240 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
#include <variant>
#include <vector>
#define arestas aresta

using namespace std;

const int N = 1010;
set <int> g[N];
int mark[N], pai[N];
vector <int> ans;
vector <int> aresta[N][N];

bool dfs(int v, int p){
    mark[v] = 1;
    pai[v] = p;
    for(auto x : g[v]){
        if(x != p and mark[x]){
            return true;
            vector <int> ciclo;
            int xx = v;
            while(xx != x){
                ciclo.push_back(xx);
                xx = pai[xx];
            }
            ciclo.push_back(x);
            vector <int> path;
            xx = x;
            while(xx != 0){
                path.push_back(xx);
                xx = pai[xx];
            }
            path.push_back(0);
            reverse(path.begin(), path.end());
            //exit(0);
            for(int i = 0;i+1 < path.size();i++){
                ans.push_back(arestas[path[i]][path[i+1]][0]);
            }
            reverse(ciclo.begin(), ciclo.end());
            int t = ciclo.size();
            for(int i = 0;i < ciclo.size();i++){
                ans.push_back(arestas[ciclo[i]][ciclo[(i+1)%t]][0]);
            }
            for(int i = 0;i < ciclo.size();i++){
                ans.push_back(arestas[ciclo[i]][ciclo[(i+1)%t]][1]);
            }
            for(int i = ciclo.size()-1;i > 0;i--){
                i++;
                ans.push_back(arestas[ciclo[((i-1)%t+t)%t]][ciclo[i%t]][0]);
                i--;
            }
            for(int i = ciclo.size()-1;i > 0;i--){
                i++;
                ans.push_back(arestas[ciclo[((i-1)%t+t)%t]][ciclo[i%t]][1]);
                i--;
            }
            t = path.size();
            for(int i = t-2;i > 0;i--){
                ans.push_back(arestas[path[i]][path[i+1]][0]);
            }
            //exit(0);
            return true;
        } 
        else if(x == p) continue;
        if(dfs(x, v)) return true;
    }
    return false;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    int n = N;
    for(int i = 0;i < M;i++){
        g[U[i]].insert(V[i]);
        aresta[U[i]][V[i]].push_back(i);
    } 
    if(dfs(0, 0)) return ans;
    return false;
}

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